首页 > 其他分享 >【题解】C - STEP

【题解】C - STEP

时间:2024-10-06 20:23:57浏览次数:7  
标签:int 题解 修改 STEP il 长度 ri define

目录

题目内容

原题:洛谷P6492

Description

给定一个长度为 \(n\) 的字符序列 \(a\),初始时序列中全部都是字符L
有 \(q\) 次修改,每次给定一个 \(x\),若 \(a_x\) 为L,则将 \(a_x\) 修改成R,否则将 \(a_x\) 修改成L
对于一个只含字符LR的字符串 \(s\),若其中不存在连续的LR,则称 \(s\) 满足要求。
每次修改后,请输出当前序列 \(a\) 中最长的满足要求的连续子串的长度。

Input

第一行有两个整数,分别表示序列的长度 \(n\) 和修改操作的次数 \(q\)。
接下来 \(q\) 行,每行一个整数,表示本次修改的位置 \(x\)。

Output

对于每次修改操作,输出一行一个整数表示修改 \(a\) 中最长的满足要求的子串的长度。

数据规模与约定

对于全部的测试点,保证 \(1\le n,q\le2\times 10^5\),\(1\le x\le n\)。

做法一

思路

首先题目可以转化为给你一个01串,需要支持单点翻转、查找最长的01交替的串。修改很好维护,但是查询比较麻烦。对于这种查询内容不方便直接合并的题,考虑使用分块。具体地,对于每个块,维护一个全局最长串长度,以最左端为起点的最长串长度,以最右端为终点的最长串长度,最左端和最右端的值,为了方便再开一个标记该区间是否完全满足01交替的限制。修改时对其所在的块暴力重构,查询时从第一个块到最后一个块遍历,先取该区间的全局最长串长度,再考虑和前面一个串的结尾合并的长度。注意判断前后合并是否合法。复杂度 \(O(n\sqrt{n})\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,c;
struct Block_Array
{
	#define N 200002
	#define M 505
	int cnt,len,lt[M],rt[M],be[N],num[M],lnum[M],rnum[M];
	bool can[M],col[N];
	il void build(int x)//分块
	{
		len=sqrt(x);
		cnt=x/len;
		for(ri i=1;i<=cnt;i++)
		{
			lt[i]=rt[i-1]+1;
			rt[i]=rt[i-1]+len;
		}
		if(rt[cnt]!=x)
		{
			cnt++;
			lt[cnt]=rt[cnt-1]+1;
			rt[cnt]=x;
		}
		for(ri i=1;i<=cnt;i++)
		{
			for(ri j=lt[i];j<=rt[i];j++)
			{
				be[j]=i;
			}
			lnum[i]=rnum[i]=num[i]=1;
		}
	}
	il void add(int x)//暴力重构
	{
		ri y=be[x],rn=0;
		col[x]^=1;
		can[y]=false;
		num[y]=1;
		for(ri i=lt[y];i<rt[y];i++)//查找靠左最优区间的结尾
		{
			if(col[i]==col[i+1])
			{
				rn=i-lt[y]+1;
				break;
			}
		}
		if(!rn)//如果没找到就证明该块完全合法
		{
			can[y]=true;
			lnum[y]=rnum[y]=num[y]=rt[y]-lt[y]+1;
			return;
		}
		lnum[y]=rn;
		for(ri i=rt[y];i>lt[y];i--)//否则继续找靠右最优区间的开头
		{
			if(col[i]==col[i-1])
			{
				rnum[y]=rt[y]-i+1;
				break;
			}
		}
		rn=0;
		num[y]=max(lnum[y],rnum[y]);//这一句一定要加上
		for(ri i=lt[y];i<rt[y];i++)//在全局继续找
		{
			rn++;
			if(col[i]==col[i+1])
			{
				num[y]=max(num[y],rn);
				rn=0;
			}
		}
	}
	il int find()
	{
		ri rn=num[1],pre=rnum[1];
		register bool ed=col[rt[1]];//初始化
		for(ri i=2;i<=cnt;i++)
		{
			rn=max(rn,num[i]);//先取全局
			if(can[i])//分讨关于合并的情况
			{
				if(ed!=col[lt[i]])
				{
					pre+=num[i];
					rn=max(rn,pre);
				}
				else
				{
					pre=rt[i]-lt[i]+1;
				}
			}
			else
			{
				if(ed!=col[lt[i]])
				{
					pre+=lnum[i];
					rn=max(rn,pre);
				}
				pre=rnum[i];
			}
			ed=col[rt[i]];
		}
		return rn;
	}
	#undef N
	#undef M
}ba;
int main()
{
	scanf("%d%d",&a,&b);
	ba.build(a);
	while(b--)
	{
		scanf("%d",&c);
		ba.add(c);
		printf("%d\n",ba.find());
	}
	return 0;
}

做法2

思路

从分块算法中获得启发,发现这种东西可以用类似的方法在线段树上合并。维护的东西和分块基本一致。对于叶子结点的左右值直接赋值,长度直接赋值为1。单点修改相同。向上合并时先看看左右儿子在中间的值,可不可以合并,进行分讨。大体原理和分块的找答案时的处理相同。查询时直接输出线段树根处存的答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,c;
struct Segment_Tree//封装线段树
{
	#define N 800008
	int left[N],right[N],num[N],lnum[N],rnum[N];
	bool lid[N],rid[N],can[N];
	il int lft(int x)//左儿子
	{
		return x<<1;
	}
	il int iht(int x)//右儿子
	{
		return x<<1|1;
	}
	il void pushup(int x)//向上合并
	{
		lid[x]=lid[lft(x)];
		rid[x]=rid[iht(x)];
		num[x]=max(num[lft(x)],num[iht(x)]);//不要忘了这里
		if(rid[lft(x)]!=lid[iht(x)])//对能否合并的分讨
		{
			num[x]=max(num[x],rnum[lft(x)]+lnum[iht(x)]);
			if(can[lft(x)])
			{
				lnum[x]=num[lft(x)]+lnum[iht(x)];
			}
			else
			{
				lnum[x]=lnum[lft(x)];
			}
			if(can[iht(x)])
			{
				rnum[x]=num[iht(x)]+rnum[lft(x)];
			}
			else
			{
				rnum[x]=rnum[iht(x)];
			}
			can[x]=can[lft(x)]&can[iht(x)];//注意万能标记也要向上合并
		}
		else
		{
			lnum[x]=lnum[lft(x)];
			rnum[x]=rnum[iht(x)];
			can[x]=false;
		}
	}
	il void build(int x,int lt,int rt)//建树
	{
		left[x]=lt;
		right[x]=rt;
		if(lt==rt)
		{
			num[x]=lnum[x]=rnum[x]=1;
			can[x]=true;
			return;
		}
		ri me=(lt+rt)>>1;
		build(lft(x),lt,me);
		build(iht(x),me+1,rt);
		pushup(x);
	}
	il void add(int x,int pl)//单点修改
	{
		if(left[x]==right[x])
		{
			lid[x]^=1;
			rid[x]=lid[x];
			return;
		}
		ri me=(left[x]+right[x])>>1;
		if(pl<=me)
		{
			add(lft(x),pl);
		}
		else
		{
			add(iht(x),pl);
		}
		pushup(x);
	}
	il int find()//查询
	{
		return num[1];
	}
	#undef N
}st;
int main()
{
	scanf("%d%d",&a,&b);
	st.build(1,1,a);
	while(b--)
	{
		scanf("%d",&c);
		st.add(1,c);
		printf("%d\n",st.find());
	}
	return 0;
}

标签:int,题解,修改,STEP,il,长度,ri,define
From: https://www.cnblogs.com/ywhhdjser-97/p/18447314

相关文章

  • 常见问题解决 --- maven手动安装依赖jar包报错
    报错内容:执行命令mvninstall:install-file-DgroupId=com.beidouapp-DartifactId=SSDK-Dversion=4.0.2.0 -Dfile=C:\1\SSDK-Release-4.0.2.0.jar-Dpackaging=jar报错Unknownlifecyclephase“.ggstar“.Youmustspecifyavalidlifecyclephaseoragoal原因:在pow......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......
  • CCF-CSP认证资格考试题解系列——第4次第3题节日
    #include<iostream>usingnamespacestd;intm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};intis_run(intyear){ if(year%400==0||(year%4==0&&year%100))return1; return0;}intgetdays(intyear,intmonth){ if(month==2)returnm[month]+i......
  • ABC374 E 题解
    ABC374E题解E-SensorOptimizationDilemma2题目链接:AT|洛谷容易发现答案可以二分。于是我们把问题转化为了判定性问题:给定目标\(x\),能否在花费不超过预算的情况下,使得每个过程的产量都不低于\(x\)?进一步,由于各个过程的生产互不相关,所以我们要尽可能让每个过程的费......
  • P7078 [CSP-S2020] 贪吃蛇 题解
    P7078[CSP-S2020]贪吃蛇这题好啊题目传送门看到题之后觉得有点像砍蚯蚓的那道题看看题目可以证明,若一条蛇在吃完之后不是最弱的那一条蛇,那么他一定会选择吃,证明如下设蛇长为\(a_{1,\dots,n}\)且依次递增,那么很明显的因为​......
  • 鲁的智力 题解
    题意有\(n\)个人,\(m\)个学科,你第\(i\)门学科排在第\(a_i\)名,且每个人在每个学科得到的分数是一个\(0\)到\(1\)之间的一个实数,求你总分排名的最大、小值。题解先考虑排名最高的情况。我们可以每一科都这样构造:\[b_1=1\]\[b_2=1-\Deltax\]\[b_3=1-2\De......
  • 游览计划 题解
    题意给定一张无向图,选取四个点\(a\neb\nec\ned\),求\(f(a,b)+f(b,c)+f(c,d)\)的最大值,其中\(f(u,v)\)表示点\(u\)到点\(v\)的最短路长度。题解如果顺着枚举四个点\(a\)、\(b\)、\(c\)、\(d\),是一个\(n^4\)的复杂度,显然过不了。但是我们发现如果确定......
  • 洛谷 P3523 题解
    洛谷P3523[POI2011]DYN-Dynamite分析二分答案,问题转化为:对于给定的\(K\),选择尽可能少的节点,使得所有关键节点都被「覆盖」。对于一个关键节点,「覆盖」的定义为:存在一个被选择的点与这个关键节点的距离不大于\(K\)。方便起见,我们指定\(1\)号节点是这棵树的根节点。我们......
  • [题解]ABC374 A~E
    A-Takahashisan2直接判断字符串是否以san结尾即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ strings; cin>>s; intn=s.size(); if(s[n-1]=='n'&&s[n-2]=='a'&&s[n-3]=='s')cout<<&......
  • P11059 [入门赛 #27] 数字 (Hard Ver.)题解
    Solution先读题:在给定x的位数\(n\)和模数\(p\)后,要求构造一个\(x\)在满足\(x\modp\)的余数尽可能小的前提下使\(x\)的数字尽可能小。我们假设\(x\)的各位数字之和为\(m\),有\(1\lem\le9n\)。.(当\(x\)仅在最高位有1时\(m=1\),称为情况一,当x每位为9时\(m=9n\),称为情况二......