a549. NOI2008 Day2.2.糖果雨 - 高中生程式解題系統

內容

有一个美丽的童话：在天空的尽头有一个"糖果国"，这里大到摩天大厦，小

到小花小草都是用糖果建造而成的。更加神奇的是，天空中飘满了五颜六色的糖

果云，很快糖果雨密密麻麻从天而落，红色的是草莓糖，黄色的是柠檬糖，绿色

的是薄荷糖，黑色的是巧克力糖……这时糖果国的小朋友们便会拿出大大小小的

口袋来接天空中落下的糖果，拿回去与朋友们一起分享。

对糖果情有独钟的小Z 憧憬着能够来到这样一个童话的国度。所谓日有所

思，夜有所梦，这天晚上小Z 梦见自己来到了"糖果国"。他惊喜地发现，任何时

候天空中所有的云朵颜色都不相同，不同颜色的云朵在不断地落下相应颜色的糖

果。更加有趣的是所有的云朵都在做着匀速往返运动，不妨想象天空是有边界的，

而所有的云朵恰好在两个边界之间做着往返运动。每一个单位时间云朵向左或向

右运动一个单位，当云朵的左界碰到天空的左界，它会改变方向向右运动；当云

朵完全移出了天空的右界，它会改变方向向左运动。

我们不妨把天空想象为一个平面直角坐标系，而云朵则抽象为线段(线段可

能退化为点)：

(暂无图)

如上图，不妨设天空的左界为0，右界为len。图中共有5 片云朵，其中标

号为1 的云朵恰好改变方向向右运动，标号为2 的云朵恰好改变方向向左运动。

忽略云朵的纵坐标，它们在运动过程中不会相互影响。

小Z 发现天空中会不断出现一些云朵(某个时刻从某个初始位置开始朝某个

方向运动)，而有的云朵运动到一定时刻就会从天空中消失，而在运动的过程中

糖果在不断地下落。小Z 决定拿很多口袋来接糖果，口袋容量是无限的，但袋

口大小却是有限的。例如在时刻T 小Z 拿一个横坐标范围为[L, R]的口袋来接糖

果，如果[L, R]存在一个位置x，该位置有某种颜色的糖果落下，则认为该口袋可

接到此种颜色的糖果。极端情况下，袋口区间可能是一个点，譬如[0,0]、[1,1]，

但仍然可以接到相应位置的糖果。通常可以接到的糖果总数会很大，因而小Z

想知道每一次(即拿出口袋的一瞬间)他的口袋可以接到多少种不同颜色的糖果。

糖果下落的时间忽略不计。

輸入說明

输入的第一行有两个正整数n, len，分别表示事件总数以及天空的“边界”。

接下来n 行每行描述一个事件，所有的事件按照输入顺序依次发生。每行的

第一个数k（k = 1，2，3）分别表示事件的类型，分别对应三种事件：插入事件，

询问事件以及删除事件。输入格式如下：

事件类型	输入格式	说明
插入事件 (天空中出现了一片云朵)	1 Ti Ci Li Ri Di	时刻Ti，天空中出现了一片坐标范围为[Li, Ri]，颜色为Ci 的云朵，初始的时候云朵运动方向为向左(Di = -1)或向右(Di = 1)。满足 0 ≤ Li ≤ Ri ≤ len，Di = -1 或1。数据保证任何时刻空中不会出现两片颜色相同的云朵。
询问事件 (询问一个口袋可以接到多少种不同颜色的糖果)	2 Ti Li Ri	时刻Ti，小Z 用一个坐标范围为[Li, Ri]的大口袋去接糖果，询问可以接到多少种不同的糖果。满足0 ≤ Li ≤ Ri ≤ len。
删除事件 (天空中一片云朵消失了)	3 Ti Ci	时刻Ti，颜色为Ci 的云朵从天空消失中。数据保证当前天空中一定存在一片颜色为Ci 的云朵。

輸出說明

对于每一个询问事件，输出应包含相应的一行，为该次询问的答案，即口袋可以接到多少种不同的糖果。

範例輸入 #1

10 10
1 0 10 1 3 -1
2 1 0 0
2 11 0 10
2 11 0 9
1 11 13 4 7 1
2 13 9 9
2 13 10 10
3 100 13
3 1999999999 10
1 2000000000 10 0 1 1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 2.0s , <1K
公開測資點#1 (10%): 2.0s , <1M
公開測資點#2 (10%): 2.0s , <1M
公開測資點#3 (10%): 2.0s , <10M
公開測資點#4 (10%): 2.0s , <10M
公開測資點#5 (10%): 2.0s , <10M
公開測資點#6 (10%): 2.0s , <10M
公開測資點#7 (10%): 2.0s , <10M
公開測資點#8 (10%): 2.0s , <10M
公開測資點#9 (10%): 2.0s , <10M

提示：

共 10 个事件，包括3 个插入事件，5 个询问事件以及2 个删除事件。

【样例说明】

时刻0，天空中出现一片颜色为10 的云朵，初始位置为[1, 3]，方向向左。

时刻1，范围为[0, 0]的口袋可以接到颜色为10 的糖果(云朵位置为[0, 2])。

时刻11，范围为[0,10]的口袋可以接到颜色为10 的糖果(云朵位置为[10, 12])。

时刻11，范围为[0, 9]的口袋不能接到颜色为10 的糖果(云朵位置为[10, 12])。

时刻11, 天空中出现一片颜色为13 的云朵, 初始位置为[4, 7], 方向向右。

时刻13，范围为[9, 9]的口袋可以接到颜色为10(云朵的位置为[8, 10])和颜色

为13(云朵的位置为[6, 9])两种不同的糖果。

时刻13，范围为[10, 10]的口袋仅仅可以接到颜色为10 的一种糖果(云朵的位

置为[8, 10])，而不可以接到颜色为13 的糖果(云朵的位置为[6, 9]),。

时刻100, 颜色为13 的云朵从天空中消失。

时刻1999999999，颜色为10 的云朵从天空中消失。

时刻2000000000，天空中又出现一片颜色为10 的云朵，初始位置为[0, 1]，

方向向右。

【数据规模和约定】

对于所有的数据，0 ≤ Ti ≤ 2000000000，1 ≤ Ci ≤ 1000000。

数据保证{Ti}为非递减序列即T1 ≤ T2 ≤ … ≤ Tn-1 ≤ Tn。

对于所有的插入事件，令Pi = Ri – Li，即Pi 表示每片云朵的长度。

数据编号	n	len	Pi	数据编号	n	len	Pi
1	20	10	≤len	6	150000	1000	≤3
2	200	100	≤len	7	200000	1000	≤3
3	2000	1000	≤len	8	100000	1000	≤len
4	100000	10	≤len	9	150000	1000	≤len
5	100000	100	≤2	10	200000	1000	≤len

標籤:

出處:

NOI 2008 Day2 第二题 [管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」