题目分析:
- tr[nod].ls表示区间最左边的数
- tr[nod].rs表示区间最右边的数
- tr[nod].L表示从左往右能延伸的最大长度,tr[nod].R为从右往左
- tr[nod].ans表示当前区间的最长子串
Code:
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define lson l,mid,nod<<1
#define rson mid+1,r,nod<<1|1
#define maxn 20010
int n,m;
struct node {
int len;
int L,R,ans;
int ls,rs;
}tr[maxn<<2];
inline int read_() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
inline void pushup_(int nod) {
tr[nod].L=tr[nod<<1].L;
tr[nod].R=tr[nod<<1|1].R;
tr[nod].ans=max(tr[nod<<1].L,tr[nod<<1].ans);
tr[nod].ans=max(tr[nod].ans,max(tr[nod<<1|1].R,tr[nod<<1|1].ans));
tr[nod].ls=tr[nod<<1].ls;
tr[nod].rs=tr[nod<<1|1].rs;
if(tr[nod<<1].rs^tr[nod<<1|1].ls) {
tr[nod].ans=max(tr[nod].ans,tr[nod<<1].R+tr[nod<<1|1].L);
if(tr[nod<<1].L==tr[nod<<1].len) {
tr[nod].L+=tr[nod<<1|1].L;
}
if(tr[nod<<1|1].R==tr[nod<<1|1].len) {
tr[nod].R+=tr[nod<<1].R;
}
}
}
void build_(int l,int r,int nod) {
tr[nod].len=r-l+1;
if(l==r) {
tr[nod].L=tr[nod].R=tr[nod].ans=1;
tr[nod].ls=tr[nod].rs=1;
return;
}
build_(lson);
build_(rson);
pushup_(nod);
}
void update_(int l,int r,int nod,int k) {
if(l==r&&l==k) {
tr[nod].ans=tr[nod].L=tr[nod].R=1;
tr[nod].ls^=1;
tr[nod].rs^=1;
return;
}
if(k<=mid) update_(lson,k);
else update_(rson,k);
pushup_(nod);
}
void readda_() {
n=read_();m=read_();
build_(1,n,1);
int x;
while(m--) {
x=read_();
update_(1,n,1,x);
printf("%d\n",tr[1].ans);
}
}
int main() {
freopen("a.txt","r",stdin);
readda_();
return 0;
}