传送门
考虑在区间维护五个值: 一个是le 代表从左端点开始向右的最大01序列 一个是ri 代表从右端点开始向左的最大01序列 一个是all 代表整个区间最大的01序列(可以不含左，右端点) xl 代表区间左端点的值 xr 代表区间右端点的值 这样之后，每次push_up，判断左儿子的xr是否与右儿子的xl构成异或关系，如果是的话，就可以更新all,le,ri了。
#include<bits/stdc++.h> using namespace std; int n,m; const int N=20005; struct node { int l,r; int le,ri,all; int xl,xr; }tree[N*4]; inline void push_up(int x) { tree[x].xl=tree[2*x].xl,tree[x].xr=tree[2*x+1].xr; tree[x].le=tree[2*x].le,tree[x].ri=tree[2*x+1].ri; tree[x].all=max(tree[2*x].all,tree[2*x+1].all); if(tree[2*x].xr==tree[2*x+1].xl^1) { tree[x].all=max(tree[x].all,tree[2*x].ri+tree[2*x+1].le); if(tree[2*x].r-tree[2*x].l+1==tree[x].le) { tree[x].le+=tree[2*x+1].le; } if(tree[2*x+1].r-tree[2*x+1].l+1==tree[x].ri) { tree[x].ri+=tree[2*x].ri; } } } inline void build(int l,int r,int now) { tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].le=tree[now].ri=tree[now].all=1; tree[now].xl=tree[now].xr=0; return; } int m=(l+r)>>1; build(l,m,2*now); build(m+1,r,2*now+1); push_up(now); } inline void modify(int now,int x) { if(tree[now].l==tree[now].r) { tree[now].xl=tree[now].xr=tree[now].xl^1; return; } int m=(tree[now].l+tree[now].r)/2; if(x<=m) modify(2*now,x); else modify(2*now+1,x); push_up(now); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; build(1,n,1); for(int i=1;i<=m;i++) { int x; cin>>x; modify(1,x); cout<<tree[1].all<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9396170.html
