第十四届中北大学ACM程序设计竞赛 J.ZBT的游戏

问题描述

第14届中北大学程序设计竞赛来了，集训队新买了一大堆气球，气球一共有K种颜色(1<=K<=256)，气球的颜色从1-K编号。

ZBT童心未泯，他发明了一种摆放气球的游戏，规则如下。

一排有N个桌子，每张桌子上只有一个气球插孔，即每张桌子最多只能放一个气球。编号分别为1-N（1<=N<=100000）,每张桌子一开始是空的。现在对这张桌子要进行M次操作(1<=M<=100000),操作的种类一共有2种。

操作1:

操作指令格式: CHANGE L R C

操作含义:在编号为L至编号为R的桌子分别放置颜色为C的气球（如果这些桌子上曾经有气球，则取下原来的气球。因为每张桌子上只能放置一个气球）

操作2:

操作指令格式: QUERY L R

操作含义:输出编号为L到编号为R的桌子上的气球颜色种类数

现在他要求你写程序来完成他的操作，程序的输入输出见输入、输出描述

输入描述

第1行是三个整数N和M以及K，用空格隔开，分别代表桌子的个数、要进行操作指令的个数、以及气球的颜色总数。

接下来M行，每行一个操作指令，格式如上，保证指令中的1<=L<=R<=N, 1<=C<=K

输出描述

如果操作指令中有查询操作(操作2)，那么对于每个操作2输出一行，该行中只有一个整数即为该查询操作的答案。

如果全部操作指令中都没有查询操作(操作2)，那么请输出” This is a boring game!”(不含引号)

样例输入

10 20 5

QUERY 6 8

CHANGE 5 8 5

CHANGE 2 3 5

CHANGE 9 10 1

QUERY 9 9

QUERY 8 10

CHANGE 2 4 4

CHANGE 9 9 2

QUERY 2 2

CHANGE 8 10 1

CHANGE 6 9 3

CHANGE 10 10 2

QUERY 3 5

QUERY 6 8

QUERY 2 5

QUERY 5 5

QUERY 3 9

QUERY 4 10

CHANGE 5 8 1

QUERY 7 8

样例输出

题意：维护颜色序列，支持以下操作

区间覆盖（颜色修改）
区间查询颜色种类

前置技能：

线段树基本操作（区间覆盖、区间查询）
状态压缩思想

显然，如果是单点修改的话，等同于洛谷P1903 [国家集训队]数颜色。有离线做法：CDQ+树状数组/带修莫队和在线做法：树套树等多种优雅解法（然而本人都不会）。

但是，因为本题有区间覆盖的操作，导致上述做法失效或转移复杂度过高。

所以该怎么做呢？

本题的操作都是区间操作，可以想到用线段树。观察到颜色种类只有256种，因此可以在每个线段树的结点上存储一个集合，表示这个结点代表的区间里出现颜色的种类。

维护时，区间覆盖还是打Lazytag。当某个区间被完全覆盖需要修改时，把集合中的元素清空，只存入当前修改的一种颜色。

每次递归并下传标记后，当前结点的颜色集合等于左右子节点的颜色集合的并集。

具体维护集合，可以用bitset或者用4个longlong类型变量（相当于手写bitset）。

这里每个结点开一个bitset<300> dat；

区间被完全覆盖，先把这个结点的颜色集合清空，即node[p].dat=0；然后集合里只有覆盖的这种颜色color，即node[p].dat[color]=1。

每次完成对左右儿子的修改后上传操作，当前结点的颜色集合等于左右子节点的颜色集合的并集，即node[p].dat=node[p<<1].dat|node[p<<1|1].dat 。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, k;

bitset<300> ans;//统计答案用

struct SegmentTree {

	int l, r, tag;

	bitset<300> dat;//相当于每个结点存储一个颜色集合

#define l(p) (node[p].l)

#define r(p) (node[p].r)

#define tag(p) (node[p].tag)

#define ls(p) (p<<1)

#define rs(p) (p<<1|1)

#define mid ((l(p)+r(p))>>1)

} node[N << 2];

void build(int p, int l, int r) {

	l(p) = l;

	r(p) = r;

	if(l == r) return;//初始没有颜色 都是0

	build(ls(p), l, mid);

	build(rs(p), mid + 1, r);

}

void update(int p, int v) {//结点p被颜色v完全覆盖

	tag(p) = v;

	node[p].dat = 0;//清空集合

	node[p].dat[v] = 1;//集合里只有颜色v

}

void pushdown(int p) {//下传结点p标记

	if(tag(p)) {

		update(ls(p), tag(p));//更新左右结点

		update(rs(p), tag(p));

		tag(p) = 0;//清空标记

	}

}

void change(int p, int L, int R, int v) {

	if(l(p) > R || r(p) < L) return;//修改区间与该节点表示区间没有交集

	if(L <= l(p) && r(p) <= R) return update(p, v);//该节点被完全覆盖

	pushdown(p);//下传标记

	change(ls(p), L, R, v);//修改左右儿子结点

	change(rs(p), L, R, v);

	node[p].dat = node[ls(p)].dat | node[rs(p)].dat;//当前颜色集合等于左右儿子的集合的并集

}

void query(int p, int L, int R) {//查询时同理

	if(l(p) > R || r(p) < L) return;

	if(L <= l(p) && r(p) <= R) {

		ans = ans | node[p].dat;//这里ans是全局变量

		return;

	}

	pushdown(p);

	query(ls(p), L, R);

	query(rs(p), L, R);

	node[p].dat = node[ls(p)].dat | node[rs(p)].dat;

}

int main() {

	scanf("%d%d%d", &n, &m, &k);

	build(1, 1, n);

	char op[10];

	int l, r, c;

	bool flag = false;

	while(m--) {

		scanf("%s%d%d", op, &l, &r);

		if(op[0] == 'C') {

			scanf("%d", &c);

			change(1, l, r, c);

		} else if(op[0] == 'Q') {

			flag = true;

			ans = 0;//清空ans

			query(1, l, r);

			int res = ans.count();//ans.count()返回ans中有几位是1

			printf("%d\n", res);

		}

	}

	if(!flag) puts("This is a boring game!");

	return 0;

}

秒客网