P6492 [COCI2010-2011#6] STEP（线段树维护最长子串）

#include<bits/stdc++.h>
using namespace std;
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<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}

const int maxn=2e5+100;
int n,q;
int c[maxn<<2],pre[maxn<<2],suf[maxn<<2],ll[maxn<<2],rr[maxn<<2];
void pushup (int i,int l,int r) {
	c[i]=max(c[i<<1],c[i<<1|1]);
	ll[i]=ll[i<<1];
	rr[i]=rr[i<<1|1];
	pre[i]=pre[i<<1];
	suf[i]=suf[i<<1|1];
	int mid=(l+r)>>1;
	if (pre[i<<1]==mid-l+1&&ll[i<<1|1]!=rr[i<<1]) {
		pre[i]+=pre[i<<1|1];
	}
	if (suf[i<<1|1]==r-mid&&ll[i<<1|1]!=rr[i<<1])  {
		suf[i]+=suf[i<<1];
	}
	if (ll[i<<1|1]!=rr[i<<1]) c[i]=max(c[i],suf[i<<1]+pre[i<<1|1]);
	c[i]=max(c[i],pre[i]);
	c[i]=max(c[i],suf[i]);
}
void build (int i,int l,int r) {
	if (l==r) {
		c[i]=pre[i]=suf[i]=1;
		ll[i]=rr[i]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	pushup(i,l,r);
}
void up (int i,int l,int r,int p) {
	if (l==p&&r==p) {
		ll[i]^=1;
		rr[i]^=1;
		return;
	}
	int mid=(l+r)>>1;
	if (p<=mid) up(i<<1,l,mid,p);
	if (p>mid) up(i<<1|1,mid+1,r,p);
	pushup(i,l,r);
}
int main () {
	n=read();
	q=read();
	build(1,1,n);
	while (q--) {
		int x=read();
		up(1,1,n,x);
		printf("%d
",c[1]);
	}
}