#337. [HAOI2017] 八纵八横

[HAOI2017] 八纵八横

[HAOI2017] 八纵八横

题目描述

Anihc 国有 nn 个城市,这 nn 个城市从 11nn 编号,11 号城市为首都。城市间初始时有 mm 条高速公路,每条高速公路都有一个非负整数的经济影响因子,每条高速公路的两端都是城市(可能两端是同一个城市),保证任意两个城市都可以通过高速公路互达。

国正在筹划“八纵八横”的高铁建设计划,计划要修建一些高速铁路,每条高速铁路两端也都是城市(可能两端是同一个城市),也都有一个非负整数的经济影响因子。国家还计划在“八纵八横”计划建成之后,将“一带一路”扩展为“一带一路一环”,增加“内陆城市经济环”即选择一条从首都出发沿若一系列高铁与高速公路走的路径,每条高铁或高速公路可以经过多次,每座城市也可以经过多次,最后路径又在首都结束。令“内陆城市经济环”的 GDP 为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来(一条路经过多次则会被计算多次)。

现在 Anihc 在会议上讨论“八纵八横”的建设计划方案,他们会不断地修改计划方案,希望你能实时反馈对于当前的“八纵八横”的建设计划的方案“内陆城市经济环”的最大是多少。

初始时,八纵八横计划中不包含任何一条高铁,有以下 33 种操作:

Add x y z

在计划中给在城市 xx 和城市 yy 之间建设一条高铁,其经济影响因子为 zz,如果这是第 kkAdd 操作,则将这条高铁命名为 kk 号高铁。

Cancel k

将计划中的 kk 号高铁取消掉,保证此时 kk 号高铁一定存在。

Change k z

表示将第 kk 号高铁的经济影响因子更改为 zz,保证此时 kk 号高铁一定存在。

输入格式

第一行 33 个整数 n,m,Qn,m,Q,表示城市个数,高速公路条数,操作个数。

接下来 mm 行,每行 33 个整数表示高速公路的信息。

接下来 QQ 行,每行为一个操作。

注意:输入的所有经济影响因子都将以二进制的形式从高位到低位给出。

输出格式

第一行一个整数。表示如果不修建任何高铁,“内陆城市经济环”的 GDP 最大值。

接下 QQ 行每行一个整数,表示进行了对应的每一个操作之后,对于当前的计划,“内陆城市经济环”的 GDP 最大值。

注意:输出的答案也要以二进制的形式从高位到低位给出。

样例 #1

样例输入 #1

4 4 3
1 2 1110
1 3 10
2 4 1110
2 3 100
Add 3 4 11
Change 1 101
Cancel 1

样例输出 #1

1000
1001
1111
1000

提示

数据规模与约定

令所有的经济因子二进制表示的最多位数为 lenlen。数据满足以下表格:

数据点 nn mm QQ lenlen 特殊性质
1 5\leq 5 8\leq 8 00 31\leq 31
2 100\leq 100 =n+1=n + 1 100\leq 100
3 100\leq 100
4 500\leq 500 1000\leq 1000
5 100\leq 100 200\leq 200 只存在 Add 操作
6 500\leq 500 200\leq 200 1000\leq 1000
7 100\leq 100 1000\leq 1000 200\leq 200
8 500\leq 500 1000\leq 1000
9
10

对于所有的数据保证:1n,m5001\leq n,m\leq 5000Q10000\leq Q\leq 10001len10001\leq len\leq 10001x,yn1\leq x,y\leq n。且 Add 操作不超过 550550 个。两个城市之间可能有多条高速公路或高铁,高速公路或高铁的两端可能是同一个城市(即:有重边,有自环)。