洛谷P2574 XOR的艺术

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

拥有一个伤害串，是一个长度为
给定一个范围
会修改伤害串中的数值，修改的方法是把

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

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

输入第二行是一个长度为

第

若
若

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

样例输入输出

原伤害串为 1011101001。

对于第一次操作，改变

对于第二次操作，查询

对于第三次操作，改变

对于第四次操作，查询

对于第五次操作，改变

对于第六次操作，查询

数据范围与约定

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

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

对于 $100\%100% 的数据，保证 2 leq n, m leq 2 imes 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。$

$这题还是比较简单的，就是模板改一下就行，思路很好想只要把“L”和“R”看成“0”和“1”就行。$

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int max=200010;
string a;
int n,m,op,lf,rt;
struct Node
{
    int l,r,num1;
    int tag;
    Node *ls,*rs;
    inline void maketag(const int w)
    {
        tag^=w;
        num1=r-l+1-num1;
    }
    inline bool InRange(const int L,const int R)
    {
        return (L<=l&&r<=R);
    }
    inline bool OutofRange(const int L,const int R)
    {
        return (l>R)||(L>r);
    }
    inline void pushdown()
    {
        if(tag==0)
        return;
        ls->maketag(tag);
        rs->maketag(tag);
        tag=0;
    }
    inline void pushup()
    {
        num1=ls->num1+rs->num1;
    }
    Node(const int L,const int R)
    {
        l=L;
        r=R;
        tag=0;
        if(l==r)
        {
            num1=a[l-1]-'0';
            ls=NULL;
            rs=NULL;
        }
        else
        {
            int M=(l+r)>>1;
            ls=new Node(L,M);
            rs=new Node(M+1,R);
            pushup();
        }
    }
    inline void upd(const int L,const int R)
    {
        if(OutofRange(L,R))
        return;
        if(InRange(L,R))
        {
            maketag(1);    
        }    
        else if(!OutofRange(L,R))
        {
            pushdown();
            ls->upd(L,R);
            rs->upd(L,R);
            pushup();
        }
    }
    inline int qry(const int L, const int R)
    {
        if(InRange(L,R))
        {
            return num1;
        }
        else if(!OutofRange(L,R))
        {
            pushdown();
            return ls->qry(L,R)+rs->qry(L,R);
        }
        else return 0;
    }
    inline void check(const int L,const int R)
    {
        if(ls)
        ls->check(L,R);
        if(rs)
        rs->check(L,R);
        printf("%d %d
 %d %d
",l,r,num1,tag); 
    }
};
int main()
{
    scanf("%d%d",&n,&m);
    cin>>a;
    Node *rot=new Node(1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&lf,&rt);
        if(op==0)
        {
            rot->upd(lf,rt);
        }
        else if(op==1)
        {
        printf("%d
",rot->qry(lf,rt));
        }
    }
    return 0;
}

洛谷P2574 XOR的艺术

题目描述

输入格式

输出格式

输入输出样例

说明/提示

样例输入输出

数据范围与约定

洛谷P2574 XOR的艺术

题目描述

输入格式

输出格式

输入输出样例

说明/提示

样例输入输出 11 解释

数据范围与约定

样例输入输出