好久没写了,调试发现a数组出毛病了值被改了,求问
已经在多部机子上调试结果相同
(文件里已经加入调试代码)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=2e5+10;
int N,M,a[maxn];
struct node{int l,r,v,lazy;}f[maxn<<3];
void T(){
for(int i=1;i<=N<<2;i++){
printf("%d:%d %d %d\n",i,f[i].l,f[i].r,f[i].v);
}
}
int lenth(int t){return f[t].r-f[t].l+1;}
void pushup(int t){f[t].v=f[t<<1].v+f[t<<1|1].v;}
void pushdown(int t){
f[t<<1].lazy=f[t<<1|1].lazy=f[t].lazy&=1;
if(f[t].lazy==0||f[t].l==f[t].r) return;
f[t<<1].v=lenth(t<<1)-f[t<<1].v;
f[t<<1|1].v=lenth(t<<1|1)-f[t<<1|1].v;
f[t].lazy=0;
}
void build(int t,int l,int r){
printf("%d %d %d\n",t,l,r);
f[t].l=l,f[t].r=r;
if(l==r){f[t].v=a[l];return;}
int m=(l+r)/2;
build(t<<1,l,m);
build(t<<1|1,m+1,r);
pushup(t);
}
void change(int t,int ul,int ur){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur){f[t].lazy++;f[t].v=lenth(t)-f[t].v;return;}
pushdown(t);
int m=(l+r)>>1;
if(m>=ul) change(t<<1,ul,ur);
if(m<ur) change(t<<1|1,ul,ur);
pushup(t);
return;
}
int ask(int t,int ul,int ur){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur) return f[t].v;
pushdown(t);
int rt=0,m=(l+r)>>1;
if(m>=ul) rt+=ask(t<<1,ul,ur);
if(m<ur) rt+=ask(t<<1|1,ul,ur);
return rt;
}
int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++){
char c;scanf(" %c",&c);
if(c=='0') a[i]=0;
else a[i]=1;
}
for(int i=1;i<=N;i++) printf("%d\n",a[i]);
build(1,1,N);
while(M--){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
if(x) printf("%d\n",ask(1,y,z));
else change(1,y,z);
T();
}
return 0;
}
调试信息:
10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6
1
0
1
1
1
0
1
0
0
1
1 1 10
2 1 5
4 1 3
8 1 2
16 1 1
17 2 2
9 3 3
5 4 5
10 4 4
11 5 5
3 6 10
6 6 8
12 6 7
24 6 6
25 7 7
13 8 8
7 9 10
14 9 9
15 10 10
1:1 10 5
2:1 5 3
3:6 10 2
4:1 3 2
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 0
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
3
1:1 10 5
2:1 5 3
3:6 10 2
4:1 3 2
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 0
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
1:1 10 6
2:1 5 4
3:6 10 2
4:1 3 3
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
6
1:1 10 6
2:1 5 4
3:6 10 2
4:1 3 3
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 010 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6
1
0
1
1
1
0
1
0
0
1
1 1 10
2 1 5
4 1 3
8 1 2
16 1 1
17 2 2
9 3 3
5 4 5
10 4 4 -----------------------
11 5 5
3 6 10
6 6 8
12 6 7
24 6 6
25 7 7
13 8 8
7 9 10
14 9 9
15 10 10
1:1 10 5
2:1 5 3
3:6 10 2
4:1 3 2
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 0
10:4 4 0 --------------------------???
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
3
1:1 10 5
2:1 5 3
3:6 10 2
4:1 3 2
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 0
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
1:1 10 6
2:1 5 4
3:6 10 2
4:1 3 3
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
6
1:1 10 6
2:1 5 4
3:6 10 2
4:1 3 3
5:4 5 1
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 0
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
1:1 10 4
2:1 5 2
3:6 10 2
4:1 3 0
5:4 5 2
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 1
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
4
1:1 10 4
2:1 5 2
3:6 10 2
4:1 3 0
5:4 5 2
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 1
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
1:1 10 4
2:1 5 2
3:6 10 2
4:1 3 0
5:4 5 2
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 1
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0
4
1:1 10 4
2:1 5 2
3:6 10 2
4:1 3 0
5:4 5 2
6:6 8 1
7:9 10 1
8:1 2 2
9:3 3 1
10:4 4 1
11:5 5 1
12:6 7 1
13:8 8 0
14:9 9 0
15:10 10 1
16:1 1 1
17:2 2 1
18:0 0 0
19:0 0 0
20:0 0 0
21:0 0 0
22:0 0 0
23:0 0 0
24:6 6 0
25:7 7 1
26:0 0 0
27:0 0 0
28:0 0 0
29:0 0 0
30:0 0 0
31:0 0 0
32:0 0 0
33:0 0 0
34:0 0 0
35:0 0 0
36:0 0 0
37:0 0 0
38:0 0 0
39:0 0 0
40:0 0 0