1 //Accepted    14560 KB    1532 ms  2 //线段树 区间合并  3 /*  4 0 a b 把[a, b]区间内的所有数全变成0  5 1 a b 把[a, b]区间内的所有数全变成1  6 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0  7 3 a b 询问[a, b]区间内总共有多少个1  8 4 a b 询问[a, b]区间内最多有多少个连续的1  9 */ 10 #include <cstdio> 11 #include <cstring> 12 #include <iostream> 13 #include <queue> 14 #include <cmath> 15 #include <algorithm> 16 using namespace std; 17 /** 18   * This is a documentation comment block 19   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 20   * @authr songt 21   */ 22 const int imax_n = 100005; 23 struct node 24 { 25     int l,r; 26     int L1,R1;   //左右连续1 27     int L0,R0;   //左右连续0 28     int change;  //-1 无操作 2取反，0全0 1全1 29     int sum1,sum0;  //最大连续1,0 30     int all1,all0;  //所有1,0 31 }f[imax_n*3]; 32 int a[imax_n]; 33 int max(int a,int b) 34 { 35     return a>b?a:b; 36 } 37 int min(int a,int b) 38 { 39     return a<b?a:b; 40 } 41 int swap(int &a,int &b) 42 { 43     int t=a; 44     a=b; 45     b=t; 46 } 47 //由下向上合并 48 //f[t]的延迟标记是指延迟f[t]的两个孩子的操作,而f[t]已经完成该操作 49 void pushUp(int t) 50 { 51     //printf("pushUpt=%d\n",t); 52     int lLen=f[2*t].r-f[2*t].l+1; 53     int rLen=f[2*t+1].r-f[2*t+1].l+1; 54  55     f[t].L1=f[2*t].L1; 56     if (f[2*t].L1==lLen) f[t].L1+=f[2*t+1].L1;//左连续1的个数 57     f[t].R1=f[2*t+1].R1; 58     if (f[2*t+1].R1==rLen) f[t].R1+=f[2*t].R1;//右连续1的个数 59     f[t].sum1=max(f[2*t].sum1,f[2*t+1].sum1); 60     f[t].sum1=max(f[t].sum1,f[2*t].R1+f[2*t+1].L1);//最大连续1=max(左边，右边，中间合并) 61     f[t].all1=f[2*t].all1+f[2*t+1].all1;   //所有1 62  63     f[t].L0=f[2*t].L0; 64     if (f[2*t].L0==lLen) f[t].L0+=f[2*t+1].L0; 65     f[t].R0=f[2*t+1].R0; 66     if (f[2*t+1].R0==rLen) f[t].R0+=f[2*t].R0; 67     f[t].sum0=max(f[2*t].sum0,f[2*t+1].sum0); 68     f[t].sum0=max(f[t].sum0,f[2*t].R0+f[2*t+1].L0); 69     f[t].all0=f[2*t].all0+f[2*t+1].all0; 70 } 71 void pushDown(int t) 72 { 73     if (f[t].change!=-1) 74     { 75         //printf("pushDownt=%d\n",t); 76         int lLen=f[2*t].r-f[2*t].l+1; 77         int rLen=f[2*t+1].r-f[2*t+1].l+1; 78         if (f[t].change==0)  //set all 0 79         { 80             f[2*t].change=f[2*t+1].change=0; 81             f[t].change=-1; 82             f[2*t].L1=f[2*t].R1=f[2*t].sum1=f[2*t].all1=0; 83             f[2*t].L0=f[2*t].R0=f[2*t].sum0=f[2*t].all0=lLen; 84             f[2*t+1].L1=f[2*t+1].R1=f[2*t+1].sum1=f[2*t+1].all1=0; 85             f[2*t+1].L0=f[2*t+1].R0=f[2*t+1].sum0=f[2*t+1].all0=rLen; 86             return ; 87         } 88         if (f[t].change==1)  //set all 1 89         { 90             f[2*t].change=f[2*t+1].change=1; 91             f[t].change=-1; 92             f[2*t].L1=f[2*t].R1=f[2*t].sum1=f[2*t].all1=lLen; 93             f[2*t].L0=f[2*t].R0=f[2*t].sum0=f[2*t].all0=0; 94             f[2*t+1].L1=f[2*t+1].R1=f[2*t+1].sum1=f[2*t+1].all1=rLen; 95             f[2*t+1].L0=f[2*t+1].R0=f[2*t+1].sum0=f[2*t+1].all0=0; 96             return ; 97         } 98         if (f[t].change==2)  //0->1 1->0 99         {100             f[t].change=-1;101             if (f[2*t].change==-1)  //如果f[2*t]没有操作，则直接取反102             {103                 f[2*t].change=2;104             }105             else if (f[2*t].change==0)  //如果f[2*t]已经标记为置0，取反后为置1106             {107                 f[2*t].change=1;108             }109             else if (f[2*t].change==1)  //如果f[2*t]已经标记为置1，取反后为置0110             {111                 f[2*t].change=0;112             }113             else if (f[2*t].change==2)  //如果f[2*t]已经取反，再次取反相当于没操作114             {115                 f[2*t].change=-1;116             }117             swap(f[2*t].L0,f[2*t].L1); //f[2*t]进行取反操作，0,1的标记都要互换118             swap(f[2*t].R0,f[2*t].R1);119             swap(f[2*t].sum0,f[2*t].sum1);120             swap(f[2*t].all0,f[2*t].all1);121             //2*t+1 同 2*t122             if (f[2*t+1].change==-1)123             {124                 f[2*t+1].change=2;125             }126             else if (f[2*t+1].change==0)127             {128                 f[2*t+1].change=1;129             }130             else if (f[2*t+1].change==1)131             {132                 f[2*t+1].change=0;133             }134             else if (f[2*t+1].change==2)135             {136                 f[2*t+1].change=-1;137             }138             swap(f[2*t+1].L0,f[2*t+1].L1);139             swap(f[2*t+1].R0,f[2*t+1].R1);140             swap(f[2*t+1].sum0,f[2*t+1].sum1);141             swap(f[2*t+1].all0,f[2*t+1].all1);142         }143     }144 }145 void build(int t,int l,int r)146 {147     f[t].l=l;148     f[t].r=r;149     f[t].change=-1;150     if (l==r)151     {152         f[t].L1=f[t].R1=f[t].sum1=f[t].all1=a[l];153         f[t].L0=f[t].R0=f[t].sum0=f[t].all0=1-a[l];154         return ;155     }156     int mid=(f[t].l+f[t].r)/2;157     build(2*t,l,mid);158     build(2*t+1,mid+1,r);159     pushUp(t);160 }161 void update(int t,int l,int r,int op)162 {163     //printf("update l=%d r=%d\n",l,r);164     if (f[t].l==l && f[t].r==r)165     {166         //如果是2号操作，需要考虑原来的操作167         if (op==2)168         {169             if (f[t].change==-1) f[t].change=2;170             else if (f[t].change==0) f[t].change=1;171             else if (f[t].change==1) f[t].change=0;172             else if (f[t].change==2) f[t].change=-1;173         }174         else175         {176             //置0,1操作和原来的操作没关系177             f[t].change=op;178         }179         if (op==0)  //该区间置0180         {181             f[t].L1=f[t].R1=f[t].sum1=f[t].all1=0;182             f[t].L0=f[t].R0=f[t].sum0=f[t].all0=f[t].r-f[t].l+1;183         }184         else if (op==1) //该区间置1185         {186             f[t].L1=f[t].R1=f[t].sum1=f[t].all1=f[t].r-f[t].l+1;187             f[t].L0=f[t].R0=f[t].sum0=f[t].all0=0;188         }189         else if (op==2) //该区间取反190         {191             swap(f[t].L0,f[t].L1);192             swap(f[t].R0,f[t].R1);193             swap(f[t].sum0,f[t].sum1);194             swap(f[t].all0,f[t].all1);195         }196         return ;197     }198     pushDown(t); //如果操作的区间为当前区间的子区间，则要把当前区间的change传到子区间199     int mid=(f[t].l+f[t].r)/2;200     if (r<=mid) update(2*t,l,r,op);201     else202     {203         if (l>mid) update(2*t+1,l,r,op);204         else205         {206             update(2*t,l,mid,op);207             update(2*t+1,mid+1,r,op);208         }209     }210     pushUp(t);   //子区间修改完成后，要向父区间合并信息211 }212 //op==1 求所有1 op==0 求最大连续1213 int query(int t,int l,int r,int op)214 {215     if (f[t].l==l && f[t].r==r)216     {217         if (op==1) return f[t].all1;218         return f[t].sum1;219     }220     pushDown(t);221     int mid=(f[t].l+f[t].r)/2;222     if (r<=mid) return query(2*t,l,r,op);223     else224     {225         if (l>mid) return query(2*t+1,l,r,op);226         else227         {228             if (op==1) return query(2*t,l,mid,op)+query(2*t+1,mid+1,r,op);229             int ans,ans1,ans2;230             ans1=query(2*t,l,mid,op);231             ans2=query(2*t+1,mid+1,r,op);232             ans=max(ans1,ans2);233             ans=max(ans,min(f[2*t].R1,mid-l+1)+min(f[2*t+1].L1,r-mid));  //r-mid=r-(mid+1)+1234             return ans;235         }236     }237 }238 int n,Q;239 int op,x,y;240 void slove()241 {242     build(1,1,n);243     for (int i=1;i<=Q;i++)244     {245         scanf("%d%d%d",&op,&x,&y);246         x++;247         y++;248         if (op==0)249         {250             update(1,x,y,0);251         }252         else if (op==1)253         {254             update(1,x,y,1);255         }256         else if (op==2)257         {258             update(1,x,y,2);259         }260         else if (op==3)261         {262             int t=query(1,x,y,1);263             printf("%d\n",t);264         }265         else if (op==4)266         {267             int t=query(1,x,y,0);268             printf("%d\n",t);269         }270     }271 }272 int main()273 {274     while (scanf("%d%d",&n,&Q)!=EOF)275     {276         for (int i=1;i<=n;i++)277         scanf("%d",&a[i]);278         slove();279     }280     return 0;281 }