#6258. 「CodePlus 2017 12 月赛」火锅盛宴

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

SkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天,他们聚在一起,享受一场火锅盛宴。

在这场火锅盛宴中,有一个麻辣浓汤锅底的火锅和 n 种食物,每种食物数量都是无限的。我们用 1 n 将这些食材编号。

每种食物煮熟所需要的时间不同,第 i 种食物煮熟需要 s_i 单位时间。这表示如果你在第 T 个时刻将一个食物 i 下到火锅里,那么它会在第 T+s_i 个时刻被煮熟,并且此后一直会延续被煮熟的状态,直到它被拿走为止。

Yazid 和 YJQQQAQ 的口味不同:YJQQQAQ 觉得所有食物的好吃程度都是相同的;而 Yazid 则觉得没有两种食材的好吃程度是相同的,并且,巧合的是,编号越小的食物 Yazid 越喜欢吃。可怜的 S kyDec由于不能吃辣,所以只能帮 Yazid 和 YJQQQAQ 煮食物。

整个火锅盛宴持续 10^9 单位时间。在整个盛宴中,三位好朋友除了谈笑风生之外,最重要的事当然就是吃东西了。在任意整数时刻,都有可能发生下列 4 种事件中的任意一种,我们用 0 3 之间的整数 op 描述事件类型:

  • 0 id:表示 SkyDec 往火锅里下了一个编号为 id 的食物。
  • 1:Yazid在锅内搜寻熟了的最喜欢吃的食物,并拿走一个这种食物。特别地,如果锅里没有熟了的食物,那么 Yazid 会很愤怒。
  • 2 id:YJQQQAQ 在锅内搜寻编号为 id 的食物:如果锅里不存在该种食物,则 YJQQQAQ 会很愤怒;如果锅里存在熟了的该食物,则 YJQQQAQ 会取走一个并食用;如果锅里只有未煮熟的该种食物,那么 YJQQQAQ 会希望知道最接近煮熟的该种食物(即锅内存在时间最长的该种食物)还需要多少时间被煮熟。
  • 3 l r:馋涎欲滴的 SkyDec 想知道,锅里编号在 [l,r] 之间的熟了的食物总共有多少个。

整个火锅晚宴中共发生了 Q 个事件,且没有任意两个事件在同一时刻发生。

他们的好朋友 Flvze 想知道这场火锅晚宴中发生的所有事,所以请你告诉她。

输入格式

从标准输入读入数据。

本题包含多组数据,输入的第一行为一个正整数 T ,表示数据组数。接下来依次描述每组数据,对于每组数据:

第一行一个正整数 n ,表示食物的种类数。

第二行 n 个用空格隔开的正整数 s_1,s_2,\dots,s_n ,描述每种食物煮熟需要的时间。

第三行一个正整数 Q ,表示事件的数目。

接下来 Q 行,每行若干个用空格隔开的非负整数,描述一个事件。先是两个整数 t,op ,分别表示发生事件的时间以及事件的类型。如果 op=0 op=2 ,则接下来 1 个正整数 id ,意义见「题目描述」;如果 op=1 ,则接下来没有其他数;如果 op=3 ,则接下来 2 个正整数 l,r ,意义见「题目描述」。

我们保证 t 按输入顺序严格递增。

我们保证 1\leq t\leq 10^9 0\leq op\leq 3 1\leq id\leq n 1\leq l\leq r\leq n

输出格式

输出到标准输出。

对于每个 op\neq 0 的操作,输出一行表示答案。对于不同的 op ,需要输出的内容如下:

  • 对于 op=1 ,如果 Yazid 成功取走食物,则输出他取走食物的编号;否则输出 "Yazid is angry."(不含引号,下同)。
  • 对于 op=2 ,如果 YJQQQAQ 成功取走食物,则输出 "Succeeded!";否则,如果锅里有未煮熟的该类食物,输出最接近煮熟的该种食物还需要多少时间被煮熟;否则,输出 "YJQQQAQ is angry."。
  • 对于 op=3 ,输出锅内编号在指定范围内的熟食的数量。

样例

样例输入 1

1
2
1 100
10
1 0 2
2 0 1
3 2 1
4 2 2
5 2 1
200 0 1
201 3 1 2
202 1
203 1
204 1

样例输出 1

Succeeded!
97
YJQQQAQ is angry.
2
1
2
Yazid is angry.

数据范围与提示

子任务

测试点编号 n\leq Q\leq 特殊约定 测试点分值
1 500 1000 8
2-3 10 300,000 6
4-5 100,000 所有 s_i=1 8
6-7 所有 s_i 都相同 11
8-9 op\neq 3 7
10-11 12
12-13 500,000 2

对于所有数据,保证 T\leq 4 ,保证 n\leq 100,000 Q\leq 500,000 1\leq s_i\leq 10^8


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/王聿中 命题/王聿中 验题/吕时清,杨景钦
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。