P2253 好一个一中腰鼓！

传送门：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
",max(tree[1].ms,max(tree[1].ls,tree[1].rs)));
82     }
83     return 0;
84 }