OI

【线段树】XOR的艺术

P2574再练一道线段树的题。

题意是长度为n的01字串，询问区间1的个数，区间更新为将区间中的数xor 1。

于是就很清楚了，由于xor 1即将区间中0,1互换，因此线段树节点存区间0的个数和1的个数，线段树维护区间和。又由于xor 1两次即不变，lazytag的操作只需要取反即可。

题目是XOR的艺术，为了照应，也尝试了一下一些细节的位运算写法（

根rt,左子树rt<<1,右子树rt<<1|1（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#define MAX 200005
struct node{
    int zero,one;
    int lazy;
};
struct node segtree[MAX*4];

char ch[MAX];

void swap(int *a,int *b){
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

void build(int rt,int st,int ed){
    segtree[rt].lazy=0;
    if(st==ed){
        if(ch[st-1]=='1'){
            segtree[rt].zero=0;
            segtree[rt].one=1;
        }
        else{
            segtree[rt].zero=1;
            segtree[rt].one=0;
        }
        return;
    }
    int mid=(st+ed)>>1;
    build(rt<<1,st,mid);
    build(rt<<1|1,mid+1,ed);
    segtree[rt].zero=segtree[rt<<1].zero+segtree[rt<<1|1].zero;
    segtree[rt].one=segtree[rt<<1].one+segtree[rt<<1|1].one;
}

void push(int rt){
    if(segtree[rt].lazy){
        segtree[rt<<1].lazy^=1;
        segtree[rt<<1|1].lazy^=1;
        swap(&segtree[rt<<1].zero,&segtree[rt<<1].one);
        swap(&segtree[rt<<1|1].zero,&segtree[rt<<1|1].one);
        segtree[rt].lazy=0;
    }
}

int query(int rt,int nst,int ned,int qst,int qed){
    if(qst>ned||qed<nst)return 0;
    if(qst<=nst&&qed>=ned)return segtree[rt].one;
    int mid=(nst+ned)>>1;
    push(rt);
    return query(rt<<1,nst,mid,qst,qed)+query(rt<<1|1,mid+1,ned,qst,qed);
}

void update(int rt,int nst,int ned,int ust,int ued){
    if(ust>ned||ued<nst)return;
    if(ust<=nst&&ued>=ned){
        segtree[rt].lazy^=1;
        swap(&segtree[rt].one,&segtree[rt].zero);
        return;
    }
    int mid=(nst+ned)>>1;
    push(rt);
    update(rt<<1,nst,mid,ust,ued);
    update(rt<<1|1,mid+1,ned,ust,ued);
    segtree[rt].zero=segtree[rt<<1].zero+segtree[rt<<1|1].zero;
    segtree[rt].one=segtree[rt<<1].one+segtree[rt<<1|1].one;
}

int main(){
    int n,m,i,type,x,y;
    scanf("%d%d",&n,&m);
    scanf("%s",ch);
    
    build(1,1,n);
    
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&type,&x,&y);
        if(type){
            printf("%d\n",query(1,1,n,x,y));
        }
        else{
            update(1,1,n,x,y);
        }
    }
    return 0;
}