Luogu: P2574 XOR的艺术 [线段树]

题目

题目在这里

题目给出一串01组成的字符串，有多种操作，可以对指定的区间的01进行翻转，也可以询问指定区间的01串中有多少个1。这道题也挺基本，相对上一个题来说只是多了一个维护标记的操作。

代码

#include <cstdio>

using namespace std;
#define lc k<<1
#define rc k<<1|1
const int maxn = 3e5+5;
int f[maxn<<2], a[maxn];
bool v[maxn<<2];
inline void build_tree(int k, int l, int r) {
    
    v[k] = 0;
    if(l == r) {
     f[k] = a[l]; return; }
    int m = (l+r) >> 1;
    build_tree(lc, l, m);
    build_tree(rc, m+1, r);
    f[k] = f[lc]+f[rc];
}

inline void push_down(int k, int l, int r) {
    
    int m = (l+r) >> 1;
    if(v[k]) {
    
        v[lc] ^= 1;
        v[rc] ^= 1;
        v[k] = 0;
        f[lc] = (m-l+1)-f[lc];
        f[rc] = (r-m)-f[rc];
    }
}

inline void update(int k, int l, int r, int x, int y) {
    
    push_down(k, l, r);
    if(l == x && r == y) {
    
        v[k] ^= 1;
        f[k] = r-l+1-f[k];
        return;
    }
    int m = (l+r) >> 1;
    if(y <= m) {
    
        update(lc, l, m, x, y);
    } else if(x > m) {
    
        update(rc, m+1, r, x, y);
    } else {
    
        update(lc, l, m, x, m);
        update(rc, m+1, r, m+1, y);
    }
    f[k] = f[lc] + f[rc];
}

inline int query(int k, int l, int r, int x, int y) {
    
    if(l == x && r == y) {
     return f[k]; }
    push_down(k, l, r);
    /* if(v[k]) { v[lc] ^= 1; v[rc] ^= 1; v[k] = 0; } */
    int m = (l+r) >> 1;
    int ans;
    if(y <= m)
        ans = query(lc, l, m, x, y);
    else if(x > m)
        ans = query(rc, m+1, r, x, y);
    else ans = query(lc, l, m, x, m) + query(rc, m+1, r, m+1, y);
    f[k] = f[lc] + f[rc];
    return ans;
}

int n, m;
int main(void)
{
    
    /* freopen("in.txt", "r", stdin); */
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
    
        scanf(" %1d", &a[i]);
    }
    build_tree(1, 1, n);
    int op, x, y;
    while(m--) {
    
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1) {
    
            printf("%d\n", query(1, 1, n, x, y));
        } else {
    
            update(1, 1, n, x, y);
        }
    }
    return 0;
}