线段树区间取反-白红宇的个人博客

线段树区间取反

发布日期：2022-02-22 18:04:13 浏览次数：7 分类：技术文章

本文共 1796 字，大约阅读时间需要 5 分钟。

题目描述

现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，......，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：第一种操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开），第二种操作是指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

输入输出格式

输入格式：

第一行有两个整数N和M，分别表示灯的数目和操作的数目。接下来有M行，每行有三个整数，依次为：c, a, b。其中c表示操作的种类，当c的值为0时，表示是第一种操作。当c的值为1时表示是第二种操作。a和b则分别表示了操作区间的左右边界（1 ≤ a ≤ b ≤ N）。

输出格式：

每当遇到第二种操作时，输出一行，包含一个整数：此时在查询的区间中打开的灯的数目。

输入输出样例

输入样例#1

4 50 1 20 2 41 2 30 2 41 1 4

输出样例#1

#include
       
        #include
        
         using namespace std;#define ls(x) (x<<1)#define rs(x) (ls(x)|1)const int maxn=1e5+5;struct FFF{    int l,r;    int op;	int cl;	bool rev;    int mid(){return l+r>>1;}    int len(){return r-l+1;}}t[maxn<<2];int n,m;void up(int o){	t[o].op=t[ls(o)].op+t[rs(o)].op;	t[o].cl=t[ls(o)].cl+t[rs(o)].cl;}void build(int l=1,int r=n,int o=1){    t[o].l=l;t[o].r=r;	t[o].op=0;    if(l==r){        t[o].cl=1;        return;    }    int mid=l+r>>1;    build(l,mid,ls(o));    build(mid+1,r,rs(o));    up(o);}void down(int o){    if(t[o].rev){		for(int i=0;i<=1;++i){			t[ls(o)|i].rev^=1;			swap(t[ls(o)|i].op,t[ls(o)|i].cl);		}		t[o].rev=0;	}}void add(int l,int r,int o=1){    if(l<=t[o].l&&t[o].r<=r){        t[o].rev^=1;		swap(t[o].op,t[o].cl);        return;    }    int mid=t[o].mid();    down(o);    if(l<=mid)add(l,r,ls(o));    if(r>mid)add(l,r,rs(o));    up(o);}int getsum(int l,int r,int o=1){    if(l<=t[o].l&&t[o].r<=r){        return t[o].op;    }    int ans=0;    int mid=t[o].mid();    down(o);    if(l<=mid)ans+=getsum(l,r,ls(o));    if(r>mid)ans+=getsum(l,r,rs(o));    return ans;}signed main(){    cin>>n>>m;	build();	while(m--){		int op,l,r;		cin>>op>>l>>r;		if(op==0){			add(l,r);		}		if(op==1){			cout<
         
          <

转载于:https://www.cnblogs.com/eric-walker/p/9425376.html

转载地址：https://blog.csdn.net/dengxingrao0615/article/details/102231340 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：链表实现队列（指针）

下一篇：又是线段树（维护方差）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目描述

输入输出格式

输入输出样例

发表评论

最新留言

关于作者

推荐文章