luogu P 2574 XORのアート(ラインツリー)

luogu P 2574 XORのアート(ラインツリー)

比較的簡単な線分樹である.区間が変更された場合.(1 xor 1=0,0 xor 1=1)だから区間要素の個数から以前の(1)を減算個数が現在(1)の個数である.

#include 
#include 
#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("%d
", query(l,r,1));
        else modify(l,r,1);
    }
    return 0;
}

転載先:https://www.cnblogs.com/tpgzy/p/9728207.html