#1786. 化学实验

    ID: 1786 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1415来源:qoj.ac数据:公开样例并查集深搜

化学实验

化学实验

题目描述

标题: 化学实验 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

实验室中有 n 种试剂,编号分别为 1,2,⋯,n,其中试剂 i 的危险程度为 i。你正在进行化学实验,但现在,你不知道任何化学反应。接下来发生了 q 个事件,每个事件为以下两种形式之一:

1 x y:你知道了如何通过化学反应使试剂 x 与试剂 y 互相转化。

2 x y:你现在只有试剂 x,求有多少试剂 x′ 满足,你可以用试剂 x 通过若干反应生成试剂 x′,且反应过程中产生的所有试剂的危险程度均不超过 y。

由于你很急切地想要知道实验结果,所以询问将强制在线。

输入格式

第一行:三个整数 t,n,q。

接下来 q 行:每行三个整数 op,x0,y0,表示一个事件 op x y,其中 x=(x0−1+t×lastans)modn+1,y=(y0−1+t×lastans)modn+1,lastans 为上一次询问的答案(不存在则为 0)。

输出格式

对于每个 op=2 的事件,输出一行一个整数,表示答案。

样例一

input

0 5 15
1 3 4
2 1 4
1 5 1
2 5 5
1 3 5
1 4 3
1 2 1
2 2 4
2 4 4
2 4 5
2 2 2
2 1 3
1 1 5
1 3 1
2 3 4

output

1
2
2
2
5
2
2
4

数据范围

对于所有数据,满足 t∈{0,1},1≤n,q≤5×105,op∈{1,2},1≤x0,y0≤n。当 op=1 时,x≠y;当 op=2 时,x≤y。

子任务编号分值n≤q≤t=11075007500121550001051320105105042010510515205×1055×10506155×1055×1051

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

0 5 15
1 3 4
2 1 4
1 5 1
2 5 5
1 3 5
1 4 3
1 2 1
2 2 4
2 4 4
2 4 5
2 2 2
2 1 3
1 1 5
1 3 1
2 3 4
1
2
2
2
5
2
2
4