UOJ Logo Universal Online Judge

UOJ

#451. 【集训队作业2018】世界是个动物园

附件下载 统计
“高峰期走出去地铁巴士挤满了蚂蚁,
 计程车打开车门一只蝴蝶飞进去,
 猫头鹰指挥着红灯该何时才变绿”
               ——华晨宇《世界是个动物园》

每隔一段时间,世界上就会出现一种新的物种,现在,世界上总共有$n$种物种,为了方便描述,根据它们在世界上的出现顺序从早到晚将它们按照$1..n$的顺序编号。

自然界是十分友善的,在任意两种物种$x,y(1\le x< y\le n)$之间,都有一个“保护关系”,这种关系是单向的,要么是$x$想保护$y$,要么是$y$想保护$x$,注意,不会存在$x,y$使得$x$和$y$都想保护对方。

但是,自然界同时也是十分残忍的,或天灾,或人祸,或种间竞争,动物们总是避免不了种种的灾难。

为了更好的抵抗到来的灾难,有些动物决定结盟。

结盟的规则是这样的,对于三种动物$x,y,z(x\neq y,x\neq z,y\neq z)$,如果$x$想保护$y$,$y$想保护$z$,$z$想保护$x$,那么他们就会在同一个联盟里面。

比如说(1,2,3),(2,3,4)都是满足上面的条件的,那么最后1,2,3,4都会在同一个联盟里面。

然而,时至今日,由于物种的数量变得十分多,物种间的“保护关系”已经变得十分复杂了。

我们这样定义物种间的“保护关系”:

对于物种$i$,我们给出$i$与$1..i-1$的“保护关系”,具体的,给出$s_i$个区间$[l_{i,j},r_{i,j}] (1\le l_{i,j}\le r_{i,j}< i)$,这些区间两两之间交集为空,对于$x\in[1,i-1]$,如果存在$j(1\le j\le s_i)$满足$x\in[l_{i,j},r_{i,j}]$,那么$i$与$x$之间的关系就是$i$想保护$x$,否则就是$x$想保护$i$。

而对于物种$i$与物种$x(i+1\le x\le n)$之间的“保护关系”,会在$x$与$1..x-1$的“保护关系”中被定义。

这样显然不重不漏地定义了两两物种之间的“保护关系”。

动物中的生物学家们决定探究物种在演变过程中的变化,一个很重要的课题就是每个时期联盟的数量。

作为动物中的佼佼者,生物学家们希望你能帮助他们求出,对于$i\in[1,n]$,在物种$i$在这个世界上出现之后动物中的联盟的数量。

输入格式

第一行两个整数$n$和$ty$,表示物种的数量以及是否强制在线($ty$为$1$表示强制在线,$ty$为$0$表示不强制在线)。

接下来$n$行,其中第$i$行第一个整数$s_i$,表示区间的数量,接下来同一行$s_i$对整数$L_{i,j},R_{i,j}$,如果$ty=0$,那么$l_{i,j}=L_{i,j},r_{i,j}=R_{i,j}$,否则$l_{i,j}=(L_{i,j}+lastans-1)\mod i+1,r_{i,j}=(R_{i,j}+lastans-1)\mod i+1$,其中$lastans$为物种$i-1$来到这个世界后联盟的数量,特殊地,当$i=1$时,$lastans=0$.

$l_{i,j},r_{i,j}$的意义请参考题目。

输出格式

输出一行$n$个整数,其中第$i$个整数,表示物种$i$来到这个世界后联盟的数量。

样例一

input

10 0
0 
1 1 1 
1 1 1 
1 1 1 
2 4 4 1 1 
2 1 1 4 4 
2 1 1 3 6 
2 6 6 1 4 
2 4 4 1 1 
2 2 2 7 8

output

1 2 3 4 5 6 7 4 5 1

样例二

input

10 1
0 
1 0 0 
1 2 2 
1 2 2 
2 0 0 2 2 
2 2 2 5 5 
2 2 2 4 0 
2 7 7 2 5 
2 0 0 6 6 
2 7 7 2 3

output

1 2 3 4 5 6 7 4 5 1

样例三

见样例数据下载。

限制与约定

记$S$为$s_i$的和。 本题采用捆绑测试,每个子任务的时空限制以及数据范围不尽相同,请选手们认真查看。

子任务编号$n\le$$S\le$$ty \le $时间限制空间限制分值
1500$2\times 10^6​$01s512MB9
22000$2\times 10^6​$01s512MB11
3$10^5$$3.5\times 10^5​$01s512MB15
4$10^5$$3.5\times 10^5​$11s512MB19
5$2\times 10^5​$$2\times 10^6​$02s512MB11
6$2\times 10^5​$$2\times 10^6​$12s512MB18
7$2\times 10^5​$$2\times 10^6​$12s16MB17

提示

输入输出的数据量较大,建议使用读入输出优化。

样例2即为样例1的加密版本.

下载

样例数据下载