luogu P2574 XOR的艺术 (线段树)luogu P2574 XOR的艺术 (线段树)

luogu P2574 XOR的艺术 (线段树)

算是比较简单的线段树.
当区间修改时.(1 xor 1 = 0,0 xor 1 = 1)所以就是区间元素个数减去以前的(1)的个数就是现在(1)的个数.

复制代码#include <iostream> #include <cstdio> #define lson now << 1 #define rson now << 1 | 1 const int maxN = 2e5 + 7; struct Node { int l,r,Xor,sum; }tree[maxN << 2]; void updata(int now) { tree[now].sum = tree[lson].sum + tree[rson].sum; return; } void build(int l,int r,int now) { tree[now].l = l;tree[now].r = r; if(l == r) { int a; scanf("%1d",&a); tree[now].sum = a ? 1 : 0; return; } int mid = (l + r) >> 1; build(l,mid,lson); build(mid + 1,r,rson); updata(now); return; } void work(int now) { tree[now].sum = tree[now].r - tree[now].l + 1 - tree[now].sum; tree[now].Xor ^= 1; return; } void pushdown(int now) { if(!tree[now].Xor) return; work(lson); work(rson); tree[now].Xor = 0; return; } void modify(int l,int r,int now) { if(tree[now].l >= l && tree[now].r <= r) { work(now); return; } int mid = (tree[now].l + tree[now].r) >> 1; pushdown(now); if(mid >= l) modify(l,r,lson); if(mid < r) modify(l,r,rson); updata(now); return; } int query(int l,int r,int now) { if(tree[now].l >= l && tree[now].r <= r) return tree[now].sum; int mid = (tree[now].l + tree[now].r) >> 1,sum = 0; pushdown(now); if(mid >= l) sum += query(l,r,lson); if(mid < r) sum += query(l,r,rson); return sum; } int main() { int n,m; scanf("%d%d",&n,&m); build(1,n,1); int type,l,r; while(m --) { scanf("%d%d%d",&type,&l,&r); if(type) printf("%dn", query(l,r,1)); else modify(l,r,1); } return 0; }

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
#include <iostream>
#include <cstdio>
#define lson now << 1
#define rson now << 1 | 1
const int maxN = 2e5 + 7;


struct Node {
    int l,r,Xor,sum;
}tree[maxN << 2];

void updata(int now) {
    tree[now].sum = tree[lson].sum + tree[rson].sum;
    return;
}

void build(int l,int r,int now) {
    tree[now].l = l;tree[now].r = r;
    if(l == r) {
        int a;
        scanf("%1d",&a);
        tree[now].sum = a ? 1 : 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,lson);
    build(mid + 1,r,rson);
    updata(now);
    return;
}

void work(int now) {
    tree[now].sum = tree[now].r - tree[now].l + 1 - tree[now].sum;
    tree[now].Xor ^= 1;
    return;
}

void pushdown(int now) {
    if(!tree[now].Xor) return;
    work(lson);
    work(rson);
    tree[now].Xor = 0;
    return;
}

void modify(int l,int r,int now) {
    if(tree[now].l >= l && tree[now].r <= r)  {
        work(now);
        return;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    pushdown(now);
    if(mid >= l) modify(l,r,lson);
    if(mid < r) modify(l,r,rson);
    updata(now);
    return;
}

int query(int l,int r,int now) {
    if(tree[now].l >= l && tree[now].r <= r) 
        return tree[now].sum;
    int mid = (tree[now].l + tree[now].r) >> 1,sum = 0;
    pushdown(now);
    if(mid >= l) sum += query(l,r,lson); 
    if(mid < r) sum += query(l,r,rson);
    return sum;
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    int type,l,r;
    while(m --) {
        scanf("%d%d%d",&type,&l,&r);
        if(type) printf("%dn", query(l,r,1));
        else modify(l,r,1);
    }
    return 0;
}