洛谷P2574 XOR的艺术

题目描述

AKN 觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下

1. 拥有一个伤害串，是一个长度为 nn 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符，即下标从 11 开始。

2. 给定一个范围 [l,~r][l, r]，伤害为伤害串的这个范围内中字符 1 的个数

3. 会修改伤害串中的数值，修改的方法是把 [l,~r][l, r] 中所有原来的字符 0 变成 1，将 1 变成 0。

AKN 想知道一些时刻的伤害，请你帮助他求出这个伤害。

输入格式

输入的第一行有两个用空格隔开的整数，分别表示伤害串的长度 nn，和操作的个数 mm。

输入第二行是一个长度为 nn 的字符串 SS，代表伤害串。

第 33 到第 (m + 2)(m+2) 行，每行有三个用空格隔开的整数 op, l, rop,l,r。代表第 ii 次操作的方式和区间，规则是：

• 若 op = 0op=0，则表示将伤害串的 [l,~r][l, r] 区间内的 0 变成 1，1 变成 0。
• 若 op = 1op=1，则表示询问伤害串的 [l,~r][l, r] 区间内有多少个字符 1。

输出格式

对于每次询问，输出一行一个整数，代表区间内 1 的个数。

输入输出样例

输入 #1复制

10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6

输出 #1复制

3
6
1

说明/提示

样例输入输出 11 解释

原伤害串为 1011101001。

对于第一次操作，改变 [2,~4][2, 4] 的字符，伤害串变为 1100101001。

对于第二次操作，查询 [1,~5][1, 5] 内 1 的个数，共有 33 个。

对于第三次操作，改变 [3,~7][3, 7] 的字符，伤害串变为 1111010001。

对于第四次操作，查询 [1,~10][1, 10] 内 1 的个数，共有 66 个。

对于第五次操作，改变 [1,~4][1, 4] 的字符，伤害串变为 0000010001。

对于第六次操作，查询 [2,~6][2, 6] 内 1 的个数，共有 11 个。

数据范围与约定

对于 10\%10% 的数据，保证 n, m \leq 10n,m≤10。

另有 30\%30% 的数据，保证 n, m \leq 2 \times 10^3n,m≤2×103。

对于 100\%100% 的数据，保证 2 \leq n, m \leq 2 \times 10^52≤n,m≤2×105，0 \leq op \leq 10≤op≤1，1 \leq l \leq r \leq n1≤l≤r≤n，SS 中只含字符 0 和字符 1。

上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
struct tree{
    int l,r,sum,n;
    bool lazy;
} t[4*N];
int n,m,A[N];
void build(int x,int l,int r){
    t[x].l=l; t[x].r=r;
    t[x].n=r-l+1;
    if(t[x].n==1){
        t[x].sum=A[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    t[x].sum=t[x*2].sum+t[x*2+1].sum;
    return;
}
void change(int x,int l,int r){
    if(t[x].l==l&&t[x].r==r){
        t[x].lazy=!t[x].lazy;
        t[x].sum=t[x].n-t[x].sum;
        return;
    }
    if(t[x].lazy){
        t[x].lazy=false;
        t[x*2].lazy=!t[x*2].lazy;
        t[x*2+1].lazy=!t[x*2+1].lazy;
        t[x*2].sum=t[x*2].n-t[x*2].sum;
        t[x*2+1].sum=t[x*2+1].n-t[x*2+1].sum;
    }
    int mid=(t[x].l+t[x].r)>>1;
    if(r<=mid) change(x*2,l,r);
    else if(mid<l) change(x*2+1,l,r);
    else{ change(x*2,l,mid); change(x*2+1,mid+1,r); }
    t[x].sum=t[x*2].sum+t[x*2+1].sum;
    return;
}
int query(int x,int l,int r){
    if(t[x].l==l&&t[x].r==r) return t[x].sum;
    if(t[x].lazy){
        t[x].lazy=false;
        t[x*2].lazy=!t[x*2].lazy;
        t[x*2+1].lazy=!t[x*2+1].lazy;
        t[x*2].sum=t[x*2].n-t[x*2].sum;
        t[x*2+1].sum=t[x*2+1].n-t[x*2+1].sum;
    }
    int ans;
    int mid=(t[x].l+t[x].r)>>1;
    if (r<=mid) ans=query(2*x,l,r);
    else if (mid<l) ans=query(2*x+1,l,r);
    else ans=(query(2*x,l,mid)+query(2*x+1,mid+1,r));
    if(t[x].lazy) ans=(r-l+1)-ans;
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int a=1;a<=n;++a) scanf("%1d",&A[a]);
    build(1,1,n);
    int opt,l,r;
    for(int a=1;a<=m;++a){
        scanf("%d%d%d",&opt,&l,&r);
        if(!opt) change(1,l,r);
        else printf("%d\n",query(1,l,r));
    }
    return 0;
}