Loading...

洛谷P2574 XOR的艺术

check评论:0 条 remove_red_eye浏览量:391 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-17

题意简述:

给定一个序列,每个点的值都是0或1
请你写一种数据结构,支持区间xor1以及区间求和

这个题一想就很简单啊qwq...

只要把线段树里的$lazy$标记改成异或就行

#include <bits/stdc++.h>
using namespace std;
int a[200010],sum[800010],addv[800010];
#define pushup(o) sum[o]=sum[o<<1]+sum[o<<1|1]
void build(int o,int lf,int rg)
{
    if(lf==rg)
    {
        sum[o]=a[lf];
        return ;
    }
    int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
void pushdown(int o,int lf,int rg)
{
    if(addv[o])
    {
        int mid=(lf+rg)>>1;
        sum[o<<1]=(mid-lf+1)-sum[o<<1];
        sum[o<<1|1]=(rg-mid)-sum[o<<1|1];
        addv[o<<1]^=1;
        addv[o<<1|1]^=1;
        addv[o]=0;
    }
}
void modify(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        sum[o]=(rg-lf+1)-sum[o];
        addv[o]^=1;
        return ;
    }
    pushdown(o,lf,rg);
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        modify(o<<1,lf,mid,l,r);
    }
    if(mid<r)
    {
        modify(o<<1|1,mid+1,rg,l,r);
    }
    pushup(o);
}
int query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    pushdown(o,lf,rg);
    int mid=(lf+rg)>>1;
    int ans=0;
    if(l<=mid)
    {
        ans+=query(o<<1,lf,mid,l,r);
    }
    if(mid<r)
    {
        ans+=query(o<<1|1,mid+1,rg,l,r);
    }
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    string aa;
    cin>>aa;
    for(int i=1;i<=n;i++)
    {
        a[i]=aa[i-1]-'0';
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==0)
        {
            modify(1,1,n,l,r);
        }
        else
        {
            printf("%d\n",query(1,1,n,l,r));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名