挖个大坑，记下死活也调不对的题目

路过的大巨帮忙挑挑错，感激不尽

 

 

2017.6.16 bzoj1858

1858: [Scoi2010]序列操作

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 2763  Solved: 1345

[][][]

Description

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

Input

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0 < = op < = 4，0 < = a < = b）

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

Sample Input

10 10

0 0 0 1 1 0 1 0 1 1

1 0 2

3 0 5

2 2 2

4 0 4

0 3 6

2 3 7

4 2 8

1 0 5

0 5 6

3 3 9

Sample Output

5

2

6

5

HINT

 

对于30%的数据，1<=n, m<=1000 对于100%的数据，1< = n, m < = 100000

 

Source

 

我大概可以肯定我是ask_mx写错了，然而就是调不对，如果某位大巨看出来我哪里写错了，一定告知，万分感激

1 //bzoj1858  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 int n,m;  8 int dt[100010];  9 struct data{ 10     int l,r; 11     int l0,l1,r0,r1,sum0,sum1,max0,max1,rev,cov,v; 12 }segtree[400010]; 13 /*void up(int pos){ 14     segtree[pos].rev=0; 15     segtree[pos].cov=-1; 16     segtree[pos].l0=segtree[pos<<1].l0; 17     segtree[pos].l1=segtree[pos<<1].l1; 18     segtree[pos].r0=segtree[pos<<1|1].r0; 19     segtree[pos].r1=segtree[pos<<1|1].r1; 20     segtree[pos].max0=max(segtree[pos<<1].max0,segtree[pos<<1|1].max0); 21     segtree[pos].max0=max(segtree[pos<<1].r0+segtree[pos<<1|1].l0,segtree[pos].max0); 22     segtree[pos].max1=max(segtree[pos<<1].max1,segtree[pos<<1|1].max1); 23     segtree[pos].max1=max(segtree[pos<<1].r1+segtree[pos<<1|1].l1,segtree[pos].max1); 24     segtree[pos].sum0=segtree[pos<<1].sum0+segtree[pos<<1|1].sum0; 25     segtree[pos].sum1=segtree[pos<<1].sum1+segtree[pos<<1|1].sum1; 26     if(segtree[pos<<1].v==1) segtree[pos].l1=segtree[pos<<1].max1+segtree[pos<<1|1].l1; 27     else if(!segtree[pos<<1].v)segtree[pos].l0=segtree[pos<<1].max0+segtree[pos<<1|1].l0; 28     if(segtree[pos<<1|1].v==1) segtree[pos].r1=segtree[pos<<1|1].max1+segtree[pos<<1].r1; 29     else if(!segtree[pos<<1|1].v)segtree[pos].r0=segtree[pos<<1|1].max0+segtree[pos<<1].r0; 30     if(segtree[pos<<1].v==segtree[pos<<1|1].v) segtree[pos].v=segtree[pos<<1].v; 31     else segtree[pos].v=-1; 32     return; 33 }*/ 34 data merge(data aa,data bb){ 35     data tmp; 36     tmp.l=aa.l; 37     tmp.r=bb.r; 38     tmp.rev=0; 39     tmp.cov=-1; 40     tmp.l0=aa.l0; 41     tmp.l1=aa.l1; 42     tmp.r0=bb.r0; 43     tmp.r1=bb.r1; 44     tmp.max0=max(aa.max0,bb.max0); 45     tmp.max0=max(tmp.max0,aa.r0+bb.l0); 46     tmp.max1=max(aa.max1,bb.max1); 47     tmp.max1=max(tmp.max1,aa.r1+bb.l1); 48     tmp.sum0=aa.sum0+bb.sum0; 49     tmp.sum1=aa.sum1+bb.sum1; 50     if(aa.v==0) tmp.l0=aa.max0+bb.l0; 51     else if(aa.v==1) tmp.l1=aa.max1+bb.l1; 52     if(bb.v==0) tmp.r0=bb.max0+aa.r0; 53     else if(bb.v==1) tmp.r1=bb.max1+aa.r1; 54     if(aa.v==bb.v) tmp.v=aa.v; 55     else tmp.v=-1; 56     return tmp; 57 } 58 void up(int pos){ 59     segtree[pos]=merge(segtree[pos<<1],segtree[pos<<1|1]); 60 } 61 void color(int pos,int cc,int ll,int rr){ 62     segtree[pos].rev=0; 63     if(!cc){ 64         segtree[pos].sum0=segtree[pos].l0=segtree[pos].r0=segtree[pos].max0=rr-ll+1; 65         segtree[pos].sum1=segtree[pos].l1=segtree[pos].r1=segtree[pos].max1=0; 66     } 67     else{ 68         segtree[pos].sum0=segtree[pos].l0=segtree[pos].r0=segtree[pos].max0=0; 69         segtree[pos].sum1=segtree[pos].l1=segtree[pos].r1=segtree[pos].max1=rr-ll+1;     70     } 71     segtree[pos].v=cc; 72     return;     73 } 74 void reverse(int pos){ 75     swap(segtree[pos].l0,segtree[pos].l1); 76     swap(segtree[pos].r0,segtree[pos].r1); 77     swap(segtree[pos].sum0,segtree[pos].sum1); 78     swap(segtree[pos].max0,segtree[pos].max1); 79     if(segtree[pos].v!=-1) segtree[pos].v^=1; 80     return; 81 } 82 void down(int pos,int ll,int rr){ 83     if(ll==rr) return; 84     if(segtree[pos].cov!=-1){ 85         segtree[pos<<1].cov=segtree[pos<<1|1].cov=segtree[pos].cov; 86         int mid=(ll+rr)>>1;  87         color(pos<<1,segtree[pos].cov,ll,mid); 88         color(pos<<1|1,segtree[pos].cov,mid+1,rr); 89         segtree[pos].cov=-1; 90     } 91     if(segtree[pos].rev){ 92         segtree[pos<<1].rev^=1; 93         segtree[pos<<1|1].rev^=1; 94         reverse(pos<<1); 95         reverse(pos<<1|1); 96         segtree[pos].rev=0; 97     } 98     return; 99 }100 void build(int pos,int ll,int rr){101     segtree[pos].l=ll;102     segtree[pos].r=rr;103     segtree[pos].cov=-1; 104     if(ll==rr){105         segtree[pos].v=dt[ll];106         if(segtree[pos].v) segtree[pos].l1=segtree[pos].r1=segtree[pos].max1=segtree[pos].sum1=1;107         else segtree[pos].l0=segtree[pos].r0=segtree[pos].max0=segtree[pos].sum0=1;108         return;109     }110     int mid=(ll+rr)>>1;111     build(pos<<1,ll,mid);112     build(pos<<1|1,mid+1,rr);113     up(pos);114 }115 int ask_sum(int pl,int pr,int pos,int ll,int rr){116     if(pl>rr||pr
          
           =rr) return segtree[pos].sum1;118     int mid=(ll+rr)>>1;119     down(pos,ll,rr);120     return ask_sum(pl,pr,pos<<1,ll,mid)+ask_sum(pl,pr,pos<<1|1,mid+1,rr);121 }122 /*int ask_mx(int pl,int pr,int pos,int ll,int rr){123     if(pl>rr||pr
           
            =rr){125 int rt=segtree[pos].max1;126 up(pos);127 return rt;128 }129 int mid=(ll+rr)>>1;130 down(pos,ll,rr);131 if(pr<=mid) ask_mx(pl,pr,pos<<1,ll,mid);132 else if(pl>mid) ask_mx(pl,pr,pos<<1|1,mid+1,rr);133 else return ask_mx(pl,mid,pos<<1,ll,mid)+ask_mx(mid+1,pr,pos<<1|1,mid+1,rr);134 }*/135 /*data ask_mx(int pl,int pr,int pos,int ll,int rr){136 down(pos,ll,rr);137 if(pl<=ll&&pr>=rr) {138 cout<
            
             <
             
              >1;142 if(pr<=mid) return ask_mx(pl,pr,pos<<1,ll,mid);143 else if(pl>mid) return ask_mx(pl,pr,pos<<1|1,mid+1,rr);144 else return merge(ask_mx(pl,mid,pos<<1,ll,mid),ask_mx(mid+1,pr,pos<<1|1,mid+1,rr));145 }*/146 data ask_mx(int pos,int ll,int rr){147 148 int lll=segtree[pos].l,rrr=segtree[pos].r;149 down(pos,lll,rrr);150 if(lll==ll&&rr==rrr){151 cout<
              
               <
               
                >1;155 if(mid>=rr)return ask_mx(pos<<1,ll,rr);156 else if(mid
                
                 rr||pr
                 
                  =rr){162 color(pos,dd,pl,pr);163 segtree[pos].cov=dd;164 return;165 }166 int mid=(ll+rr)>>1;167 if(pr<=mid) change(pl,pr,dd,pos<<1,ll,mid);168 else if(pl>mid) change(pl,pr,dd,pos<<1|1,mid+1,rr);169 else{170 change(pl,mid,dd,pos<<1,ll,mid);171 change(mid+1,pr,dd,pos<<1|1,mid+1,rr);172 }173 up(pos);174 return;175 }176 void rv(int pl,int pr,int pos,int ll,int rr){177 if(pl>rr||pr
                  
                   =rr){179 reverse(pos);180 segtree[pos].rev=1;181 return;182 }183 int mid=(ll+rr)>>1;184 if(pr<=mid) rv(pl,pr,pos<<1,ll,mid);185 else if(pl>mid) rv(pl,pr,pos<<1|1,mid+1,rr);186 else{187 rv(pl,mid,pos<<1,ll,mid);188 rv(mid+1,pr,pos<<1|1,mid+1,rr);189 }190 up(pos);191 return;192 }193 int main(){194 scanf("%d%d",&n,&m);195 for(int i=1;i<=n;i++) scanf("%d",&dt[i]);196 build(1,1,n);197 int od,x,y;198 for(int i=1;i<=m;i++){199 scanf("%d%d%d",&od,&x,&y);200 x++;201 y++;202 //for(int ii=1;ii<=45;ii++) cout<
                   
                    <<" "<
                    
                     <<" "<
                     
                      <<" "<
                      
                       <<" "<
                       
                        <<" "<
                        
                         <<" "<
                         
                          <<" "<
                          
                           <<" "<
                           
                            <<" "<
                            
                             <<" "<
                             
                              <