- 题目内容
- Description
- Input
- Output
- 数据规模与约定
- 做法一
- 思路
- 代码
- 做法2
- 思路
- 代码
题目内容
原题：洛谷P6492
Description
给定一个长度为 \(n\) 的字符序列 \(a\)，初始时序列中全部都是字符L。
有 \(q\) 次修改，每次给定一个 \(x\)，若 \(a_x\) 为L，则将 \(a_x\) 修改成R，否则将 \(a_x\) 修改成L。
对于一个只含字符L，R的字符串 \(s\)，若其中不存在连续的L和R，则称 \(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 505int 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 800008int 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;
}
