xtq的口令
题目背景
三年级时,xtq就展现出高超的身体素质,以至于体育老师允许他不用参加同学们的体育锻炼,而是可以自由活动。
xtq现在正在观察同学们跑步。
题目描述
$n$个同学在排队跑步。
体育老师发了一条指令,要求这$n$名同学加快跑步速度。然而,由于风太大,只有部分同学听到并执行了老师的指令。同时,没有听到指令的同学如果观察到其他的同学执行了老师的指令,他们也会执行老师的指令。
现在我们一般化这个情况。我们将位于队首的同学编号为$1$,将接下来的同学以此类推,最后位于队尾的同学编号为$n$。
经过观察,xtq给出了每位同学的若干位观察对象,这意味着当这位同学看到他的任何一个观察对象加快跑步速度(执行指令)时,他也会加快跑步速度(执行指令)。保证对于任何第i位同学,他的所有观察对象的编号都小于自己(一个同学只会观察排在自己前面同学中的一部分)。
现在有$q$条询问或修改,
询问:每次询问给出$L,R$,询问内容如下:如果编号在$[L,R]$区间范围内的同学听到了老师的指令,至少还需要几位同学听到了老师的指令,才能使得所有同学最后都能加快跑步速度。 格式为$1$ $L$ $R$。
修改:每次修改给出$L,R$以及$x$,代表编号在$[L,R]$的同学添加第$x$位同学为自己的观察对象。保证$x<L\le R$。不保证在修改以前$x$同学不是$[L,R]$范围内的任何一位同学的观察对象。但是,当一组$2$ $L$ $R$ $x$的修改完成后,$x$同学一定被$[L,R]$区间内的所有同学观察。格式$2$ $L$ $R$ $x$。
输入输出格式
输入格式
第一行两个整数$n,q$。
接下来n行,每行第一个整数$a_i$,代表第$i$位同学被共计$a_i$位同学观察。接下来$a_i$个整数,代表观察第$i$位同学的编号。若$a_i=0$,代表没有同学观察这位同学。由于一个同学只会被自己后面的同学观察,所以输入的编号第一大于这位同学自己的编号
###### 请注意,输入的编号是 观察第$i$位同学 的同学编号,而不是 被第$i$位同学观察 的同学编号。
接下来$q$行,每行一个询问或修改,格式见题目描述
输出格式
对于每个询问操作,输出至少还需要几位同学知道指令,才能使最终每位同学都接执行了老师的指令。
输入输出样例
输入样例 #1
4 4
1 3
1 3
1 4
0
1 2 3
1 1 1
2 2 3 1
1 1 1
输出样例 #1
1
1
0
说明
【样例解释】
样例中,$1$同学被$3$同学观察,$2$同学被$3$号同学观察,$3$同学被$4$同学观察。
对于第一个询问$1$ $2$ $3$:这意味着$2,3$两位同学听到了老师的指令。因为$3$号同学被$4$号同学观察,所以当$3$同学加快跑步速度后,$4$同学也会加快跑步速度。所以需要告诉$1$号同学指令是什么,才能使所有同学收到指令。
【数据范围】
测试数据范围及特点如下表:
|编号|n|m|特殊性质|
| ------ | ------ | ------ | ------ |
|1|10|10|有|
|2|10|10|无|
|3|500|500|有|
|4|5000|5000|无|
|5|5000|5000|无|
|6|50000|50000|有|
|7|50000|50000|无|
|8|300000|300000|有|
|9|300000|300000|无|
|10|300000|300000|无|
有特殊性质是指:$q$个操作中,修改操作不超过$100$次。
对于$100\%$的数据,$n,q\le 300000$,$a_i$之和$\le 10000000$。
由于本题有巨大的输入/输出,请不要使用cin/cout