a549. NOI2008 Day2.2.糖果雨
Tags :
Accepted rate : 10人/11人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:20

Content
有一个美丽的童话:在天空的尽头有一个"糖果国",这里大到摩天大厦,小
到小花小草都是用糖果建造而成的。更加神奇的是,天空中飘满了五颜六色的糖
果云,很快糖果雨密密麻麻从天而落,红色的是草莓糖,黄色的是柠檬糖,绿色
的是薄荷糖,黑色的是巧克力糖……这时糖果国的小朋友们便会拿出大大小小的
口袋来接天空中落下的糖果,拿回去与朋友们一起分享。
对糖果情有独钟的小Z 憧憬着能够来到这样一个童话的国度。所谓日有所
思,夜有所梦,这天晚上小Z 梦见自己来到了"糖果国"。他惊喜地发现,任何时
候天空中所有的云朵颜色都不相同,不同颜色的云朵在不断地落下相应颜色的糖
果。更加有趣的是所有的云朵都在做着匀速往返运动,不妨想象天空是有边界的,
而所有的云朵恰好在两个边界之间做着往返运动。每一个单位时间云朵向左或向
右运动一个单位,当云朵的左界碰到天空的左界,它会改变方向向右运动;当云
朵完全移出了天空的右界,它会改变方向向左运动。
我们不妨把天空想象为一个平面直角坐标系,而云朵则抽象为线段(线段可
能退化为点):
(暂无图) 
如上图,不妨设天空的左界为0,右界为len。图中共有5 片云朵,其中标
号为1 的云朵恰好改变方向向右运动,标号为2 的云朵恰好改变方向向左运动。
忽略云朵的纵坐标,它们在运动过程中不会相互影响。
小Z 发现天空中会不断出现一些云朵(某个时刻从某个初始位置开始朝某个
方向运动),而有的云朵运动到一定时刻就会从天空中消失,而在运动的过程中
糖果在不断地下落。小Z 决定拿很多口袋来接糖果,口袋容量是无限的,但袋
口大小却是有限的。例如在时刻T 小Z 拿一个横坐标范围为[L, R]的口袋来接糖
果,如果[L, R]存在一个位置x,该位置有某种颜色的糖果落下,则认为该口袋可
接到此种颜色的糖果。极端情况下,袋口区间可能是一个点,譬如[0,0]、[1,1],
但仍然可以接到相应位置的糖果。通常可以接到的糖果总数会很大,因而小Z
想知道每一次(即拿出口袋的一瞬间)他的口袋可以接到多少种不同颜色的糖果。
糖果下落的时间忽略不计。 
Input
输入的第一行有两个正整数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 的云朵。

Output
对于每一个询问事件,输出应包含相应的一行,为该次询问的答案,即口袋可以接到多少种不同的糖果。
Sample Input #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
Sample Output #1
1
1
0
2
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
Hint :
共 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

Tags:
出處:
NOI2008Day2第二题 [管理者: liouzhou_101 (王启圣) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」