UOJ Logo Universal Online Judge

UOJ

#612. 【JOISC2021】饮食区

附件下载 统计

IOI 中心是一个配备了生活设施的训练中心。这里有着为大型团体设置的饮食区。在饮食区内,依次排列着 $N$ 家商店,从 $1$ 到 $N$ 标号。在每家商店前,都有一个为顾客准备的队列。顾客们会在每个队列中排队。

今天有 $M$ 个团体呆在 IOI 中心,从 $1$ 到 $M$ 标号。团体中的成员们会以一种相对奇怪的方式排队,以享受他们之间的闲谈。

在这个饮食区中,有时商店会给予在他们的队列中的顾客免费的甜点。在饮食区中工作的 JOI 君的工作内容是记录被给予免费甜点的顾客所在的团体编号。

没有顾客会在关门的商店前排队。今天,当所有商店都营业时,在队列中发生了 $Q$ 次事件。第 $i$ 次事件是下列几种之一:

  1. 加入:对于编号在 $L_i$ 到 $R_i$ 之间(包括边界)的所有商店,来自 $C_i$ 团体的 $K_i$ 位顾客加入于队列的末尾。
  2. 离开:对于编号在 $L_i$ 到 $R_i$ 之间(包括边界)的所有商店,如果队列中有 $K_i$ 或更多位顾客,于队列开头的前 $K_i$ 位顾客离开队列。否则,所有顾客离开队列。
  3. 服务:如果在商店 $A_i$ 前的队列中有 $B_i$ 或更多位顾客,商店会给予队列中从开头数起第 $B_i$ 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。

不幸的是,JOI 君丢失了被给予免费甜点的顾客所在的团体编号的记录。他决定利用上述 $Q$ 次事件的信息恢复记录。

给出商店、团体、事件的数量,以及事件的详细信息,请编写一个程序确定每次“服务”时是否有顾客被给予了免费甜点。如果有顾客被给予了免费甜点,程序还应该确定这位顾客所在的团体的编号。

输入格式

第一行,三个正整数 $N, M, Q$。

接下来 $Q$ 行,第 $i$ 行描述一个事件:

令 $T_i$ 为第一个数,则第 $i$ 个询问:

  1. 如果 $T_i = 1$,同一行接下来四个正整数 $L_i, R_i, C_i, K_i$。表示第 $i$ 次事件为“加入”,并且对于编号在 $L_i$ 到 $R_i$ 之间(包括边界)的所有商店,来自 $C_i$ 团体的 $K_i$ 位顾客加入于队列的末尾。
  2. 如果 $T_i = 2$,同一行接下来三个正整数 $L_i, R_i, K_i$。表示第 $i$ 次事件为“离开”,并且对于编号在 $L_i$ 到 $R_i$ 之间(包括边界)的所有商店,如果队列中有 $K_i$ 或更多位顾客,于队列开头的前 $K_i$ 位顾客离开队列。否则,所有顾客离开队列。
  3. 如果 $T_i = 3$,同一行接下来两个正整数 $A_i, B_i$。表示第 $i$ 次事件为“服务”,并且如果在商店 $A_i$ 前的队列中有 $B_i$ 或更多位顾客,商店会给予队列中从开头数起第 $B_i$ 位顾客一个免费甜点。否则商店的工作人员会吃掉免费甜点。

输出格式

对于每次“服务”事件,也就是所有满足 $T_i = 3$ 的事件 $i$($1 \le i \le Q$)输出一行。如果在第 $i$ 次事件中有顾客被给予了免费甜点,输出这位顾客所在的团体的编号。如果在第 $i$ 次事件中商店的工作人员吃掉了免费甜点,输出 0

样例一

input

3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
3 3 2

output

2
0
4

explanation

下面我们用顾客所在团体的整数序列表示队列。例如,如果有 3 个顾客在商店前的队列,而且他们从队头开始分别属于团体 1, 2, 2,我们就写作 $(1,2,2)$。空队列写成 $()$。

在样例输入中,7 个事件发生了。

  1. 第一个事件是加入。2 个团体 5 的顾客加入了商店 2, 3 前的队列,之后商店 1, 2, 3 的队列变成 $(),(5,5),(5,5)$。
  2. 第二个事件是加入。4 个团体 2 的顾客加入了商店 1, 2 前的队列,之后商店 1, 2, 3 的队列变成 $(2,2,2,2),(5,5,2,2,2,2),(5,5)$。
  3. 第三个事件是服务。商店 2 有 6 个顾客排队。由于 6 不小于 3,第三个顾客获得了一份免费甜点。第三个顾客属于团体 2,所以输出 2.
  4. 第四个时间是离开。商店 1, 2 均有至少 3 个顾客排队,因此分别有 3 个顾客离开了。由于商店 3 的队伍不到 3 个顾客,所有顾客均离开。之后商店 1, 2, 3 的队列变成 $(2),(2,2,2),()$。
  5. 第五个事件是服务。商店 1 只有 1 个顾客排队,1 比 2 小,商店职员会把免费甜点吃掉,因此输出 0
  6. 第六个事件是加入。2 个团体 4 的顾客加入了商店 2, 3,之后商店 1, 2, 3 的队列变成 $(2),(2,2,2,4,4),(4,4)$。
  7. 第七个事件是服务。商店 3 有 2 个顾客排队,因此第二个顾客获得了一份免费甜点。第二个顾客属于团体 4,所以输出 4

此样例满足子任务 $2, 7, 8$ 的限制。

样例二

input

3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

output

4
0

explanation

此样例满足子任务 $1, 2, 3, 5, 7, 8$ 的限制。

样例三

input

183326 218318 22
1 106761 160918 151683 574906362
3 68709 1
1 29240 156379 22166 957318472
1 14054 181502 82845 97183925
2 112033 122908 587808357
2 57819 160939 215041262
3 36674 524274467
1 35854 69866 32334 322730299
1 1384 7230 115069 454256926
1 44192 158235 8750 84192710
3 54457 1077490708
2 10592 110384 979714505
2 44594 79244 311724477
3 160965 97183926
1 88748 101697 39148 373927458
3 41166 58039001
1 91501 137591 205480 958877326
2 77775 169655 135756956
1 12497 57047 60918 15666764
1 47839 51716 144688 732270998
3 114514 774994894
3 48645 169986425

output

0
22166
32334
0
82845
8750
60918

限制与约定

本题采用捆绑测试。

对于 $100 \%$ 的数据,$1 \le N, M, Q \le 2.5 \times {10}^5$,$T_i \in \{ 1, 2, 3 \}$,$1 \le L_i, R_i, A_i \le N$,$L_i \le R_i$,$1 \le C_i \le M$,$1 \le K_i \le {10}^9$,$1 \le B_i \le {10}^{15}$,至少存在一次满足 $T_i = 3$ 的事件。

每个子任务的具体限制见下表:

子任务编号 分值 特殊限制
$1$ $2$ $N, Q \le 2000$,$K_i = 1$
$2$ $5$ $N, Q \le 2000$
$3$ $7$ $N, Q \le 65000$,当 $T_i = 1$ 时保证 $R_i - L_i \le 10$ 且 $K_i = 1$
$4$ $21$ $M = 1$
$5$ $15$ $N, Q \le 65000$,$K_i = 1$
$6$ $13$ $N, Q \le 65000$,$T_i \in \{ 1, 3 \}$
$7$ $26$ $N, Q \le 65000$
$8$ $11$ 无特殊限制

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载