信息学奥赛一本通（C++版）第4部分 数据结构(提高篇)--＞第 3 章 线段树 1993：开关switch

本文主要是介绍信息学奥赛一本通（C++版）第4部分 数据结构(提高篇)--＞第 3 章 线段树 1993：开关switch，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1993：开关switch

时间限制: 1000 ms 内存限制: 131072 KB
提交数: 77 通过数: 24
【题目描述】

现有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）。
【输出】

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

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

【输出样例】

1
2

#include <cstdio>
#include <algorithm>

using namespace std;

#define ls(x) x << 1
#define rs(x) x << 1 | 1

const int N = 100000 + 20;

struct node
{
	int l , r;
	long long sum;long long add;
	long long xsum;
}tr[N * 4];

int n,m;
int op,l,r;


void push_down(int u)
{
    node &root = tr[u],&left = tr[ls(u)],&right = tr[rs(u)];
    if(root.add)
    {	
    	swap(left.sum,left.xsum);
    	swap(right.sum,right.xsum);
    	right.add ^= 1;
    	left.add ^= 1;
        root.add = 0;
    }
}

int query(int u, int l ,int r)
{
	if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
	push_down(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int res = 0;
	if(l <= mid) res += query(ls(u), l , r);
	if(r > mid) res += query(rs(u), l ,r);
	return res;
}

void push_up(int u)
{
	tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
	tr[u].xsum = tr[ls(u)].xsum + tr[rs(u)].xsum;
}

void build(int u, int l ,int r)
{
	if(l == r)
	{
		tr[u].l = l;
		tr[u].r = r;
		tr[u].sum = 0;
		tr[u].add = 0;
		tr[u].xsum = 1;
		return ;
	}
	else
	{
		int  mid = l + r >> 1;
		tr[u].l = l,tr[u].r = r;
		build(ls(u), l, mid),build(rs(u),mid + 1, r);
		push_up(u);		
	}
}
	
void modify(int u,int l ,int r)
{
	if(l <= tr[u].l && r>= tr[u].r)
	{
		swap(tr[u].sum,tr[u].xsum);
		tr[u].add^=1;
		return ;
	}
	push_down(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) modify(ls(u), l, r );
	if(r > mid) modify(rs(u), l, r);
	push_up(u);	
}


int main()
{
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i = 1; i <=m ; i++)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op == 1)
		{
			printf("%d\n",query(1,l,r));
		}
		if(op == 0)
		{
			modify(1,l,r);
		}
	}
	return 0;
}

这篇关于信息学奥赛一本通（C++版）第4部分 数据结构(提高篇)--＞第 3 章 线段树 1993：开关switch的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！