[Code+#2] 火锅盛宴/n/n## 题目背景/n/nSkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。/n/n## 题目描述/n/n在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和 $n$ 种食物，每种食物数量都是无限的。我们用 $1$ 至 $n$ 将这些食材编号。/n/n每种食物煮熟所需要的时间不同，第 $i$ 种食物煮熟需要 $s_i$ 单位时间。这表示如果你在第 $T$ 个时刻将一个食物 $i$ 下到火锅里，那么它会在第 $T+s_i$ 个时刻被煮熟，并且此后一直会延续被煮熟的状态，直到它被拿走为止。/n/nYazid 和 YJQQQAQ 的口味不同：YJQQQAQ 觉得所有食物的好吃程度都是相同的；而 Yazid 则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物 Yazid 越喜欢吃。可怜的 SkyDec 由于不能吃辣，所以只能帮 Yazid 和 YJQQQAQ 煮食物。/n/n整个火锅盛宴持续 $10^9$ 单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列 $4$ 种事件中的任意一种，我们用 $0$ 至 $3$ 之间的整数 $op$ 描述事件类型：/n/n- $0// id$：表示 SkyDec 往火锅里下了一个编号为 $id$ 的食物。/n- $1$：Yazid 在锅内搜寻熟了的且最喜欢吃的食物，并拿走一个这种食物。特别地，如果锅里没有熟了的食物，那么 Yazid 会很愤怒。/n- $2// id$：YJQQQAQ 在锅内搜寻编号为 $id$ 的食物：/n - 如果锅里不存在该种食物，则 YJQQQAQ 会很愤怒；/n - 如果锅里存在熟了的该食物，则 YJQQQAQ 会取走一个并食用；/n - 如果锅里只有未煮熟的该种食物，那么 YJQQQAQ 会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。/n- $3// l// r$：馋涎欲滴的 SkyDec 想知道，锅里编号在 $[l,r]$ 之间的且熟了的食物总共有多少个。/n/n## 输入格式/n/n从标准输入读入数据。/n/n本题包含多组数据，输入的第一行为一个正整数 $T$，表示数据组数。接下来依次描述每组数据，对于每组数据：/n/n第一行一个正整数 $n$，表示食物的种类数。/n/n第二行 $n$ 个用空格隔开的正整数 $s_1,s_2,//cdots, s_n$，描述每种食物煮熟需要的时间。/n/n第三行一个正整数 $Q$，表示事件的数目。/n/n接下来 $Q$ 行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数 $t,op$，分别表示发生事件的时间以及事件的类型。/n/n- 如果 $op=0$ 或 $op=2$，则接下来 $1$ 个正整数 $id$，意义见题目描述；/n- 如果 $op=1$，则接下来没有其他数；/n- 如果 $op=3$，则接下来 $2$ 个正整数 $l,r$，意义见题目描述。/n/n数据保证 $t$ 按输入顺序严格递增。/n/n## 输出格式/n/n对于每个 $op//neq 0$ 的操作，输出一行表示答案。对于不同的 $op$，需要输出的内容如下：/n/n- 对于 $op=1$，如果 Yazid 成功取走食物，则输出他取走食物的编号；否则输出 'Yazid is angry.'（不含引号，下同）。/n- 对于 $op=2$，如果 YJQQQAQ 成功取走食物，则输出 'Succeeded!'；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出 'YJQQQAQ is angry.'。/n- 对于 $op=3$，输出锅内编号在指定范围内的熟食的数量。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n1/n2/n1 100/n10/n1 0 2/n2 0 1/n3 2 1/n4 2 2/n5 2 1/n200 0 1/n201 3 1 2/n202 1/n203 1/n204 1/n/n/n### 样例输出 #1/n/n/nSucceeded!/n97/nYJQQQAQ is angry./n2/n1/n2/nYazid is angry./n/n/n## 提示/n/n对于所有数据，保证$ T//leq 4$，保证 $n//leq 100,000$，$Q//leq 500,000$，$1//leq s_i//leq 10^8$，$1//leq t//leq 10^9$，$op//in//{0, 1, 2, 3/}$，$1//leq id//leq n$，$1//leq l//leq r//leq n$。数据保证 $t$ 按输入顺序严格递增。/n/n来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。/n/nCredit：idea/王聿中 命题/王聿中 验题/吕时清，杨景钦/n/nGit Repo：https://git.thusaac.org/publish/CodePlus201712/n/n感谢腾讯公司对此次比赛的支持。/n用C++内容：cpp/n#include <iostream>/n#include <vector>/n#include <queue>/n#include <algorithm>/nusing namespace std;/n/nstruct Food {/n int id;/n int time;/n};/n/nstruct Compare {/n bool operator()(const Food& f1, const Food& f2) {/n if (f1.time == f2.time) {/n return f1.id > f2.id;/n }/n return f1.time > f2.time;/n }/n};/n/nint main() {/n int T;/n cin >> T;/n while (T--) {/n int n;/n cin >> n;/n vector<int> s(n);/n for (int i = 0; i < n; ++i) {/n cin >> s[i];/n }/n priority_queue<Food, vector<Food>, Compare> cooked;/n priority_queue<Food, vector<Food>, Compare> uncooked;/n int time = 0;/n int Q;/n cin >> Q;/n while (Q--) {/n int t, op;/n cin >> t >> op;/n while (!uncooked.empty() && uncooked.top().time <= t) {/n cooked.push(uncooked.top());/n uncooked.pop();/n }/n if (op == 0) {/n int id;/n cin >> id;/n Food food;/n food.id = id;/n food.time = t + s[id - 1];/n uncooked.push(food);/n } else if (op == 1) {/n if (cooked.empty()) {/n cout << /'Yazid is angry./' << endl;/n } else {/n cout << cooked.top().id << endl;/n cooked.pop();/n }/n } else if (op == 2) {/n int id;/n cin >> id;/n bool found = false;/n int closestTime = -1;/n while (!uncooked.empty() && uncooked.top().id != id) {/n closestTime = uncooked.top().time;/n uncooked.pop();/n }/n if (!uncooked.empty() && uncooked.top().id == id) {/n found = true;/n cout << s[id - 1] - (t - uncooked.top().time) << endl;/n } else if (!cooked.empty() && cooked.top().id == id) {/n found = true;/n cooked.pop();/n }/n if (!found) {/n cout << /'YJQQQAQ is angry./' << endl;/n }/n } else if (op == 3) {/n int l, r;/n cin >> l >> r;/n int count = 0;/n priority_queue<Food, vector<Food>, Compare> temp = cooked;/n while (!temp.empty()) {/n int id = temp.top().id;/n if (id >= l && id <= r) {/n count++;/n }/n temp.pop();/n }/n temp = uncooked;/n while (!temp.empty()) {/n int id = temp.top().id;/n if (id >= l && id <= r) {/n count++;/n }/n temp.pop();/n }/n cout << count << endl;/n }/n }/n }/n return 0;/n}/n