传送门：https://www.luogu.com.cn/problem/P2253
题意：有n个数，初始都为0，接下来给你m个操作，具体就是将某一位的值取反（x=!x）。每次操作后，要求你输出最长01串的长度
之前看这个题不会做就搁置了，昨天刚好做了一个比这个简单一点的线段树区间合并，突然发现他们是有共同之处的，就来做了
这个题暴力是能过的23333，所以才是绿题
好了，说一下正解
给树的每一个节点维护以这个区间左端点为起点向右的01串长度 ls，以这个区间右端点为起点向左的01串长度 rs，中间的01串的长度（不是仨的最大值了）ms
然后color不能在线段树数组里维护，因为你在合并区间的时候不是要判断两个区间的界限是不是相等吗，这个时候你能获得的下标是的1~n的数（而不是树节点的编号！！！）再开个数组就好了
如果中间能联通且左儿子的ls==左儿子维护的区间长度 父亲的ls=左儿子维护的区间长度+右儿子的ls
如果不能联通 父亲的ls=左儿子的ls
rs同理
父亲的ms=max(左儿子的ms，右儿子的ms)
如果能联通 父亲的ms=max(刚刚更新的父亲的ms,左儿子的rs,右儿子的ls）
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lowbit(a) ((a)&-(a)) 5 #define clean(a,b) memset(a,b,sizeof(a)) 6 const int mod = 1e9 + 7; 7 const int inf=0x3f3f3f3f; 8 const int maxn = 2e4+9; 9 10 inline int read(){char c=getchar();int tot=1;while ((c<‘0‘|| c>‘9‘)&&c!=‘-‘) c=getchar();if (c==‘-‘){tot=-1;c=getchar();} 11 int sum=0;while (c>=‘0‘&&c<=‘9‘){sum=sum*10+c-‘0‘;c=getchar();}return sum*tot;} 12 13 int _; 14 ////////////////////////////////////////////////////////////////////////// 15 struct node 16 { 17 int l,r,ls,rs,ms; 18 }tree[maxn*4]; 19 int col[maxn]; 20 void build(int l,int r,int now) 21 { 22 tree[now].l=l; 23 tree[now].r=r; 24 tree[now].ls=tree[now].rs=tree[now].ms=1; 25 if(l==r) 26 { 27 return ; 28 } 29 int mid=(l+r)>>1; 30 build(l,mid,now<<1); 31 build(mid+1,r,now<<1|1); 32 } 33 void push_up(int now) 34 { 35 if((tree[now<<1].ls==(tree[now<<1].r-tree[now<<1].l+1))&&col[tree[now<<1].r]!=col[tree[now<<1|1].l]) 36 { 37 tree[now].ls=(tree[now<<1].r-tree[now<<1].l+1)+tree[now<<1|1].ls; 38 } 39 else 40 { 41 tree[now].ls=tree[now<<1].ls; 42 } 43 if((tree[now<<1|1].rs==(tree[now<<1|1].r-tree[now<<1|1].l+1))&&col[tree[now<<1].r]!=col[tree[now<<1|1].l]) 44 { 45 tree[now].rs=(tree[now<<1|1].r-tree[now<<1|1].l+1)+tree[now<<1].rs; 46 } 47 else 48 { 49 tree[now].rs=tree[now<<1|1].rs; 50 } 51 52 tree[now].ms=max(tree[now<<1].ms,tree[now<<1|1].ms);//要写在下面那个if的前面 53 54 if(col[tree[now<<1].r]!=col[tree[now<<1|1].l]) 55 { 56 tree[now].ms=max(tree[now].ms,tree[now<<1].rs+tree[now<<1|1].ls); 57 } 58 } 59 void update(int l,int r,int now,int pos) 60 { 61 if(tree[now].l==pos&&tree[now].r==pos) 62 { 63 col[pos]=!col[pos]; 64 return ; 65 } 66 int mid=(tree[now].l+tree[now].r)>>1; 67 if(pos<=mid) update(l,mid,now<<1,pos); 68 else update(mid+1,r,now<<1|1,pos); 69 push_up(now); 70 } 71 ////////////////////////////////////////////////////////////////////////// 72 int main() 73 { 74 int n=read(); 75 int m=read(); 76 build(1,n,1); 77 for(int i=1;i<=m;i++) 78 { 79 int x=read(); 80 update(1,n,1,x); 81 printf("%d\n",max(tree[1].ms,max(tree[1].ls,tree[1].rs))); 82 } 83 return 0; 84 }
原文：https://www.cnblogs.com/YangKun-/p/12770406.html