#1745. 术树数

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

术树数

术树数

题目描述

标题: 术树数 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 W 拥有一个庞大的国家。这个国家初始的时候只有一座城池,编号为 1。小 W 打算记录他的国家交通发展的历程。具体的,小 W 记录了 Q 次操作,记每一次操作前编号最大的城市为 m,每次操作是如下三种操作中的某一种:

  • 1 x v。小 W 占领了一座新的城市并将其编号为 m+1。在攻占完成后小 W 新建了一条连接 x 和 m+1 的权值为 v 的双向通行道路。(1≤x≤m,0≤v<V)
  • 2 x y v。小 W 新建了一条连接 x 和 y 的权值为 v 的双向通行道路。(1≤x≤m,0≤v<V)
  • 3 x y。小 W 询问连接 x 和 y 的所有路径的权值中,最小的那一条路径的权值。这里一条路径可以重复经过一条道路多次。(1≤x<y≤m)

在这里,小 W 定义一条路径的权值为路径上所有道路权值的 k 进制异或和。如果一条道路被经过了 x 次,则在计算异或和的时候也会计算 x 次。也就是说,有可能重复经过一条过路多次会使得路径权值变小。

注意城市 x、y 之间可能会出现很多条连接它们的道路,这些道路权值可能相同,也可能不同。

设 a 的 k 进制表示为 a1a2⋯am,b 的 k 进制表示为 b1b2⋯bn。,不妨在开头补零使得 m=n,则它们的 k 进制异或和的 k 进制表示为 (a1+b1)modk(a2+b2)modk⋯(an+bn)modk。

输入格式

第一行三个正整数,依次表示 Q,k,m。这里我们定义 V=km。

接下来 Q 行,每行若干个数字,表示一次操作。

输出格式

对于每一次操作 3,输出一行一个整数表示答案。

样例数据

样例输入

10 2 20
1 1 114514
1 2 191981
1 2 1926
1 2 817
3 1 4
3 1 5
2 3 5 1949
2 1 4 1001
3 1 4
3 1 5

样例输出

112852
113763
1001
1886

子任务

Subtask 1(2%):Q≤30,V≤2000。

Subtask 2(11%):Q≤1000,V≤100000。

Subtask 3(11%):不存在操作 2。

Subtask 4(19%):m=1。

Subtask 5(15%):k=2。

Subtask 6(3%):k 是奇数。

Subtask 7(39%):无特殊限制。

对于所有测试数据,满足 1≤Q≤2×105,2≤k,1≤m,V≤5×107。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

10 2 20
1 1 114514
1 2 191981
1 2 1926
1 2 817
3 1 4
3 1 5
2 3 5 1949
2 1 4 1001
3 1 4
3 1 5
112852
113763
1001
1886