Loading...

洛谷P3870 [TJOI2009]开关

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

$NOIP$后康复训练

这题有毒...$O(n\sqrt n)$的分块跑得比$O(nlogn)$的线段树快四倍...

线段树裸题,没啥说的,变换相当于区间异或

#include <bits/stdc++.h>
using namespace std;
int sum[400040],xorv[400010];
#define pushup(o) sum[o]=sum[o<<1]+sum[o<<1|1]
void pushdown(int o,int lf,int rg)
{
    if(xorv[o])
    {
        xorv[o<<1]^=1;
        xorv[o<<1|1]^=1;
        int mid=(lf+rg)>>1;
        sum[o<<1]=(mid-lf+1)-sum[o<<1];
        sum[o<<1|1]=(rg-mid)-sum[o<<1|1];
        xorv[o]^=1;
    }
}
void modify(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        xorv[o]^=1;
        sum[o]=(rg-lf+1)-sum[o];
        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 ans=0,mid=(lf+rg)>>1;
    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;
    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));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名