首页 > 代码库 > 大坑【持续更新......】

大坑【持续更新......】

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

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

 

 

2017.6.16 bzoj1858

1858: [Scoi2010]序列操作

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 2763  Solved: 1345
[Submit][Status][Discuss]

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

Day2

 
我大概可以肯定我是ask_mx写错了,然而就是调不对,如果某位大巨看出来我哪里写错了,一定告知,万分感激
  1 //bzoj1858
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  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<ll) return 0;
117     if(pl<=ll&&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<ll) return 0;
124     if(pl<=ll&&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<<pos<<endl;
139         return segtree[pos];
140     }
141     int mid=(ll+rr)>>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<<pos<<endl;
152         return segtree[pos];
153     }
154     int mid=(lll+rrr)>>1;
155     if(mid>=rr)return ask_mx(pos<<1,ll,rr);
156     else if(mid<ll)return ask_mx(pos<<1|1,ll,rr);
157     else return merge(ask_mx(pos<<1,ll,mid),ask_mx(pos<<1|1,mid+1,rr));
158 }
159 void change(int pl,int pr,int dd,int pos,int ll,int rr){
160     if(pl>rr||pr<ll) return;
161     if(pl<=ll&&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<ll) return;
178     if(pl<=ll&&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<<segtree[i].cov<<" "<<segtree[i].v<<" "<<segtree[i].l0<<" "<<segtree[i].l1<<" "<<segtree[i].max0<<" "<<segtree[i].max1<<" "<<segtree[i].r0<<" "<<segtree[i].r1<<" "<<segtree[i].rev<<" "<<segtree[i].sum0<<" "<<segtree[i].sum1<<endl;    
203         if(!od){
204             change(x,y,0,1,1,n);
205             continue;
206         }
207         if(od==1){
208             change(x,y,1,1,1,n);
209             continue;
210         }
211         if(od==2){
212             rv(x,y,1,1,n);
213             continue;
214         }
215         if(od==3){
216             printf("%d\n",ask_sum(x,y,1,1,n));
217             continue;
218         }
219         if(od==4){
220             printf("%d\n",ask_mx(1,x,y).max1);
221             continue;
222         }    
223     }
224     return 0;
225 }

 

大坑【持续更新......】