1 //Accepted 3911 750MS 9872K  2 //线段树 区间合并  3 #include <cstdio>  4 #include <cstring>  5 #include <iostream>  6 #include <queue>  7 #include <cmath>  8 #include <algorithm>  9 using namespace std; 10 /** 11   * This is a documentation comment block 12   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 13   * @authr songt 14   */ 15 const int imax_n = 100005; 16 struct node 17 { 18     int l,r; 19     int L1,R1; 20     int L0,R0; 21     int sum1,sum0; 22     int change; 23 }f[imax_n*3]; 24 int a[imax_n]; 25 int max(int a,int b) 26 { 27     return a>b?a:b; 28 } 29 int min(int a,int b) 30 { 31     return a<b?a:b; 32 } 33 //合并 34 // 35 void pushUp(int t) 36 { 37     int lLen=f[2*t].r-f[2*t].l+1; 38     int rLen=f[2*t+1].r-f[2*t+1].l+1; 39     f[t].L1=f[2*t].L1; 40     if (f[2*t].L1==lLen) f[t].L1+=f[2*t+1].L1; 41     f[t].R1=f[2*t+1].R1; 42     if (f[2*t+1].R1==rLen) f[t].R1+=f[2*t].R1; 43     f[t].L0=f[2*t].L0; 44     if (f[2*t].L0==lLen) f[t].L0+=f[2*t+1].L0; 45     f[t].R0=f[2*t+1].R0; 46     if (f[2*t+1].R0==rLen) f[t].R0+=f[2*t].R0; 47     f[t].sum1=max(f[2*t].sum1,f[2*t+1].sum1); 48     f[t].sum1=max(f[t].sum1,f[2*t].R1+f[2*t+1].L1); 49     f[t].sum0=max(f[2*t].sum0,f[2*t+1].sum0); 50     f[t].sum0=max(f[t].sum0,f[2*t].R0+f[2*t+1].L0); 51 } 52 void swap(int &a,int &b) 53 { 54     int t=a; 55     a=b; 56     b=t; 57 } 58 void pushDown(int t) 59 { 60     if (f[t].change==1) 61     { 62         f[2*t].change^=1; 63         f[2*t+1].change^=1; 64         f[t].change=0; 65         swap(f[2*t].L0,f[2*t].L1); 66         swap(f[2*t].R0,f[2*t].R1); 67         swap(f[2*t].sum0,f[2*t].sum1); 68  69         swap(f[2*t+1].L0,f[2*t+1].L1); 70         swap(f[2*t+1].R0,f[2*t+1].R1); 71         swap(f[2*t+1].sum0,f[2*t+1].sum1); 72     } 73 } 74 void build(int t,int l,int r) 75 { 76     f[t].l=l; 77     f[t].r=r; 78     f[t].change=0; 79     if (l==r) 80     { 81         if (a[l]==1) 82         { 83             f[t].L1=f[t].R1=1; 84             f[t].L0=f[t].R0=0; 85             f[t].sum1=1; 86             f[t].sum0=0; 87         } 88         else 89         { 90             f[t].L1=f[t].R1=0; 91             f[t].L0=f[t].R0=1; 92             f[t].sum1=0; 93             f[t].sum0=1; 94         } 95         return ; 96     } 97     int mid=(l+r)/2; 98     build(2*t,l,mid); 99     build(2*t+1,mid+1,r);100     pushUp(t);101 }102 void update(int t,int l,int r)103 {104     if (f[t].l==l && f[t].r==r)105     {106         f[t].change^=1;107         swap(f[t].L0,f[t].L1);108         swap(f[t].R0,f[t].R1);109         swap(f[t].sum0,f[t].sum1);110         return ;111     }112     pushDown(t);113     int mid=(f[t].l+f[t].r)/2;114     if (r<=mid) update(2*t,l,r);115     else116     {117         if (l>mid) update(2*t+1,l,r);118         else119         {120             update(2*t,l,mid);121             update(2*t+1,mid+1,r);122         }123     }124     pushUp(t);125 }126 int query(int t,int l,int r)127 {128     if (f[t].l==l && f[t].r==r)129     {130         return f[t].sum1;131     }132     pushDown(t);133     int mid=(f[t].l+f[t].r)/2;134     if (r<=mid) return query(2*t,l,r);135     else136     {137         if (l>mid) return query(2*t+1,l,r);138         else139         {140             int sum1=query(2*t,l,mid);141             int sum2=query(2*t+1,mid+1,r);142             int ans=max(sum1,sum2);143             //在左半区间的长度不应大于该段区间在左半区间的长度144             ans=max(ans,min(f[2*t].r-l+1,f[2*t].R1)+min(r-f[2*t+1].l+1,f[2*t+1].L1));145             return ans;146         }147     }148 }149 int n;150 int Q,k,x,y;151 void slove()152 {153     build(1,1,n);154     scanf("%d",&Q);155     for (int i=1;i<=Q;i++)156     {157         scanf("%d%d%d",&k,&x,&y);158         if (x>y) swap(x,y);159         if (k==0)160         {161             printf("%d\n",query(1,x,y));162         }163         else164         {165             update(1,x,y);166         }167     }168 }169 int main()170 {171     while (scanf("%d",&n)!=EOF)172     {173         for (int i=1;i<=n;i++)174         scanf("%d",&a[i]);175         slove();176     }177     return 0;178 }