刚刚学了,线段树,一道线段树入门题试试水
下面是题面

题目描述

AKN觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下
1、 拥有一个伤害串为长度为n的01串。
2、 给定一个范围[l,r],伤害为伤害串的这个范围内中1的个数
3、 会被随机修改伤害串中的数值,修改的方法是把[l,r]中的所有数xor上1
AKN想知道一些时刻的伤害,请你帮助他求出这个伤害

输入输出格式

  • 输入格式:

    第一行两个数n,m,表示长度为n的01串,有m个时刻
    第二行一个长度为n的01串,为初始伤害串
    第三行开始m行,每行三个数p,l,r
    若p为0,则表示当前时刻改变[l,r]的伤害串,改变规则如上
    若p为1,则表示当前时刻AKN想知道[l,r]的伤害
  • 输出格式:

    对于每次询问伤害,输出一个数值伤害,每次询问输出一行

    输入输出样例

  • 输入样例

    10 6
    1011101001
    0 2 4
    1 1 5
    0 3 7
    1 1 10
    0 1 4
    1 2 6
  • 输出样例

    3
    6
    1

读完题,题意就很明显了,明显是一道线段树的题,线段树的题嘛,关键一般就在pushup和pushdown上,既然是异或1,那么第二次异或也就相当于没有异或,同理奇数次异或则变,偶数次异或不变
下放代码

#include<iostream>
#include<cstdio>
#include<cctype>
#define ll long long
#define maxn 200005
#define gc() getchar() 
using namespace std;
int n,m;
char a[maxn];

inline ll read(){
    ll a=0;int f=1;char p=gc();
    while(!isdigit(p)){f|=(p=='-');p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return a*f;
}

#define lc p<<1     //左儿子
#define rc p<<1|1     //右儿子
struct ahaha{
    ll v,lz;    //v存答案,lz为懒惰标记
}t[maxn<<2];   //开四倍大小,防越界
inline void pushup(int p){    //pushup依旧简单
    t[p].v=t[lc].v+t[rc].v;
}
inline void pushdown(int p,int l,int r){
    if(!t[p].lz)return;
    int m=l+r>>1;
    t[lc].v=m-l+1-t[lc].v;   //0变1,1变0,也就是长度减去它本身
    t[rc].v=r-m-t[rc].v;
    t[lc].lz^=1;t[rc].lz^=1;
    t[p].lz=0;
}
void build(int p,int l,int r){
    if(l==r){t[p].v=(a[l]^48);return;}
    int m=l+r>>1;
    build(lc,l,m);build(rc,m+1,r);
    pushup(p);
}
void update(int p,int l,int r,int L,int R){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){t[p].v=r-l+1-t[p].v;t[p].lz^=1;return;}      //同理,异或后长度减本身
    int m=l+r>>1;pushdown(p,l,r);
    update(lc,l,m,L,R);update(rc,m+1,r,L,R);
    pushup(p);
}
ll query(int p,int l,int r,int L,int R){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return t[p].v;
    int m=l+r>>1;pushdown(p,l,r);
    return query(lc,l,m,L,R)+query(rc,m+1,r,L,R);
}

inline void solve_1(){
    int x=read(),y=read();
    update(1,1,n,x,y);
}
inline void solve_2(){
    int x=read(),y=read();
    printf("%lld\n",query(1,1,n,x,y));
}

int main(){
    n=read();m=read();
    scanf("%s",a + 1);
    build(1,1,n);
    for(int i=1;i<=m;++i){
        int zz=read();
        switch(zz){
            case 0:solve_1();break;
            case 1:solve_2();break;
        }
    }
    return 0;
}