[Contest #5]迫真图论

内存限制：256 MB 时间限制：15000 ms

H君的偶像曾经是有女朋友的人赢，所以H君高中的时候也是青年科学家人赢。

他定义了一种把图映射到长度为 $131072$ 的序列 $A$（下标由 $0$ 开始编号）上的方法 $\rm Guidence-H$ ，具体来说，对于一个边和点都带权的简单无向图（无重边，无自环）$G=\{V,E\}$ ，第 $i$ 个点的点权是 $b_i$。 $E$ 中一条边 $\{x, y, z\}$ （$x, y$ 之间有一条权值为 $z$ 的边），对序列 $A$ 的贡献是把 $A[b_x\oplus b_y]$ 加上 $z$（初始时序列 $A$ 每个数都是 $0$），其中 $\oplus$ 表示按位异或运算。

H君想要测试这一种映射方法的鲁棒性，所以他找到了您帮忙，具体来说，初始时H君会给你一个图，之后您需要帮他完成一系列的操作，操作有以下三种。

操作 1：修改图中一个点的点权。

操作 2：修改图中一条边的边权。

操作 3：询问当前的图映射到的序列 $A$ 中一个区间 $[u, v]$ 的和对 $998244353$ 取模的结果，即 $ (\sum_{i=u}^v A[i]) \bmod 998244353$。

注意：操作 $1$ 和 $2$ 对于图的影响会延续，直到被后面的操作覆盖为止。

第一行三个数 $n, m, q$ 分别表示图的点数，边数以及操作总数。

接下来一行，共 $n$ 个数，第 $i$ 个数表示 $b_i$ ，也就是第 $i$ 个点的点权。

接下来 $m$ 行，每行三个数 $x, y, z$ ，表示 $x, y$ 之间有一条边权为 $z$ 的边。

接下来 $q$ 行，每行三个数 $type, u, v$ 表示操作的类型

当 $type =1$ 时，表示将点 $u$ 的点权改为 $v$。

当 $type=2$ 时，表示将读入的第 $u$ 条边边权改为 $v$。

当 $type=3$ 时，表示询问当前的图映射到的序列的区间 $[u, v]$ 中所有数的和 $\bmod\ 998244353$ 后的值，保证 $u \leq v$ 。

数据范围：

$1 \le n,m,q \le 131071,0 \le b_i \le 131071$ ，$1 \le x, y \le n$，$0 \le z < 10^9$，给定的图是简单图。

对于 $type=1$ ，$1 \le u \le n, 0 \le v \le 131071$。

对于 $type=2$ ，$1 \le u \le m, 0 \le v < 10^9$。

对于 $type=3$ ，$0 \le u \le v \le 131071$。

至少有一个 $type=3$ 的操作。

共若干行，对于每一个 $type = 3$ 的操作，输出对应的答案并换行。

样例输入 1

样例输出 1

样例输入 2

5 7 7
11 45 14 19 19
3 4 6
1 5 14
3 5 99
1 2 83
1 4 44
2 3 53
4 5 46
1 5 20
2 2 31
3 26 103
1 4 43
2 7 87
3 3 56
3 26 103

样例输出 2

272
316
403

样例解释 1：

对于第 $1$ 条边，$b_1 \oplus b_2 = 3$，故此条边对 $A[3]$ 贡献了 $1$ 的值。

对于第 $2$ 条边，$b_2 \oplus b_3 = 1$，故此条边对 $A[1]$ 贡献了 $1$ 的值。

对于第 $3$ 条边，$b_3 \oplus b_4 = 7$，故此条边对 $A[7]$ 贡献了 $1$ 的值。

对于第 $4$ 条边，$b_4 \oplus b_5 = 1$，故此条边对 $A[1]$ 贡献了 $1$ 的值。

对于第 $5$ 条边，$b_5 \oplus b_1 = 4$，故此条边对 $A[4]$ 贡献了 $1$ 的值。

所以原图所映射的的序列下标 $0 \sim 7$ 的位置的值依序是：$0,2,0,1,1,0,0,1$。

本数据的唯一一组询问问的是未经任何修改前 $A[1]$ 的值，故答案是 $2$。

C1082 [Contest #5]迫真图论

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2

提示