5994：Generator and Monitor

题目描述

You have a generator that randomly generates a uniformly distributed random number in range [1, m] and a monitor that monitors the generator and gives an alert when some conditions are met. If at the i-th second, a condition is given to the monitor, then the monitor will give an alert at the j-th second reporting that the condition given at the i-th second is met. Here j is the minimum integer such that the numbers generated by the generator from the i-th second to the j-th second and in range [ $l_i, r_i$ ] equals to $c_i$ . Otherwise, the generator will generate a number $a_i$ . However, the monitor stops working now. We need you to write a program to give the alerts.

输入解释

The first line contains an integer T, the number of test cases.
For each test case, the first line contains an integer m and n. The following n lines describe events. The i-th line describe the event happens at the i-th second. If the event is to give a condition, then it contains a character ”C” followed by $l_i , r_i$ and $c_i$ . Otherwise, the event is to generate a number and it contains a character ”G” followed by $b_i$ . $a_i$ , the number generated at the i-th second equals to the XOR sum of bi and the moments of all conditions met before i-th second.
It is guaranteed that 1 ≤ m ≤ $10^4$ and 1 ≤ n ≤ 2 × $10^5$ .

输出解释

For each test case, the output starts with a line ”Case #i:” where i is the test case number, starting from 1. Then you need to report the alerts in order. If some conditions are met at the i-th second, output a line containing i and moments when these conditions were given. Output moments in increasing order.

输入样例

输出样例

Case #1:
4 1
6 2

提示

At the 1st second, a condition is given. We need to make an alert when 1 number in range [1, 3] are generated.
At the 2nd second, a condition is given. We need to make an alert when 2 number in range [3, 5] are generated.
At the 3rd second, a number is generated. It is 4 because no condition is met before. We don’t need to make any alert because no condition is met after 4 is generated.
At the 4th second, a number is generated. It is 1 because no condition is met before. We need to make an alert because condition at 1st second is met after 1 is generated.
At the 5th second, a number is generated. Because condition at the 1st second is met before, the actual number generated should be 3 xor 1 which is 2. We don’t need to make any alert because no condition is met after 2 is generated.
At the 6th second, a number is generated. Because condition at the 1st second is met before, the actual number generated should be 2 xor 1 which is 3. We need to make an alert because condition at the 2nd second is met after 3 is generated.

来自杭电HDUOJ的附加信息

Recommend

jiangzijing2015

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2016ACM/ICPC亚洲区青岛站-重现赛（感谢中国石油大学）

源链接： HDU-5994

最后修改于 2020-10-25T23:27:22+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
32000/16000MS(Java/Others)	70000/70000K(Java/Others)