#1926. 城市建设
城市建设
城市建设
题目描述
标题: 城市建设 - Problem - QOJ.ac
#10361. 城市建设
The problem was used in the following contests:
小 G 所居住的城市可以抽象为一张 N 个点 M 条边的 有向图。在城市建设的过程中,该城市的道路会发生一些变化;具体来说,一共会有 Q 次操作,包含以下两种类型:
- 给出点 p,再给出 tot 个数 ai,在图中加入 ai 到 p 的边。
- 给出点 p,再给出 tot 个数 ai,在图中删除 ai 到 p 的边。
好奇的小 G 想在每次操作后知道,所有点对之间的 可达情况。
令 F(u,v) 表示 u,v 之间的可达状态,如果图中存在一条从 u 到 v 的路径,那么 F(u,v)=1,否则 F(u,v)=0。 容易发现 F(u,v) 和 F(v,u) 不一定相等,且 F(u,u) 必然是 1。
为了方便询问,每一个点有点权 vali,你需要在每次操作后回答下式的值:
∑u=1N∑v=1NF(u,v)×(valu⊕valv)
其中 ⊕ 表示两个数的异或值。 保证初始给出的图以及每次操作后的图 不存在重边和自环;并且删除一条边时,图上必然存在这条边。 我们还会有一些手段来 强制在线。
输入格式
-
第一行包含一个整数 ID,表示当前是第 ID 组测试数据;其中样例的 ID 均为 0。
-
第二行包含一个整数 flag,保证 flag 是 0 或 1;当 flag=1 时,这组数据要求强制在线。
-
第三行包含三个整数 N,M,Q,分别表示图的点数、初始图的边数、需要进行的操作次数。
-
第四行包含 N 个非负整数,表示每个点的点权 vali。
-
接下来 M 行,每行包含两个整数 u,v,表示初始图上有一条从 u 到 v 的有向边。
-
接下来 2Q 行,每两行描述一次操作:
- 第一行包含三个整数 k,p,tot。其中 k 为 0 或 1,当 k=0 时,为加边操作;反之为删边操作。
- 第二行包含 tot 个 互不相同 的整数 ai。
当 flag=1(即强制在线)时,令 lastAns 表示上一次操作后输出的答案(第一次操作的 lastAns=0),需要将 p 异或上 lastAns 作为 p 的真实的值。
注意:lastAns 可能会很大!
输出格式
共 Q 行,每行一个整数,表示这次操作后的答案。
样例
样例输入一
0
0
10 10 1
0 1 1 1 1 1 1 1 1 0
1 7
2 1
7 3
3 7
10 2
8 5
2 10
2 5
3 6
4 5
0 1 0
样例输出一
10
样例输入二
0
0
5 0 10
775753708 730589119 295766137 411078803 10973174
0 1 1
3
0 2 1
3
0 1 1
4
0 3 1
2
0 5 1
4
0 4 1
1
0 1 1
2
0 2 1
5
0 4 1
3
0 1 1
5
样例输出二
1067190165
2043082587
2961479386
4033244915
4438519384
8158342623
8158342623
12528106804
12528106804
12528106804
样例输入三
0
0
5 7 5
505212782 768758516 141501571 189544889 292811675
2 1
2 3
2 5
3 1
3 4
4 1
5 3
0 3 2
1 4
1 5 1
2
0 1 1
5
1 1 4
2 3 4 5
0 5 1
2
样例输出三
5862031096
4844805513
4844805513
2982371382
3999596965
样例说明
这三个样例分别满足类型一、类型二、类型三的要求。
限制与约定
本题共 20 个测试数据,每个测试数据的分值为 5 分。
所有测试数据可分为以下三种类型:
类型一(共 20 分)
保证 Q=1,tot=0,即只需对原图询问答案。
且 0≤vali≤1
ID flag N M Q tot 1 0 ≤35000 ≤100000 1 0 2 0 ≤35000 ≤100000 1 0 3 0 ≤35000 ≤100000 1 0 4 0 ≤35000 ≤100000 1 0
类型二(共 40 分)
保证不存在删边操作,即每次操作 k=0;同时 tot=1,M=0
ID flag N M Q tot 5 0 ≤500 0 ≤15000 1 6 0 ≤600 0 ≤20000 1 7 0 ≤800 0 ≤30000 1 8 0 ≤1000 0 ≤50000 1 9 0 ≤1500 0 ≤80000 1 10 0 ≤2000 0 ≤100000 1 11 1 ≤2500 0 ≤150000 1 12 1 ≤2500 0 ≤150000 1
类型三(共 40 分)
无特殊约定:
ID flag N M Q tot 13 0 ≤10 / ≤10 / 14 0 ≤50 / ≤50 / 15 0 ≤200 / ≤200 / 16 0 ≤300 / ≤300 / 17 0 ≤400 / ≤800 / 18 0 ≤400 / ≤800 / 19 0 ≤400 / ≤800 / 20 1 ≤400 / ≤800 /
保证 100% 的数据满足:
- N≥2
- 0≤M≤N(N−1)
- 1≤u,v,p,ai≤N
- 0≤tot<N
- 0≤vali≤109
时间与内存限制
因为某种不可抗拒的力量,不同类型的时限不同:
- 类型一:2 秒
- 类型二:1 秒
- 类型三:1.5 秒
内存限制:512 MB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
0
0
10 10 1
0 1 1 1 1 1 1 1 1 0
1 7
2 1
7 3
3 7
10 2
8 5
2 10
2 5
3 6
4 5
0 1 0
10
样例 2
0
0
5 0 10
775753708 730589119 295766137 411078803 10973174
0 1 1
3
0 2 1
3
0 1 1
4
0 3 1
2
0 5 1
4
0 4 1
1
0 1 1
2
0 2 1
5
0 4 1
3
0 1 1
5
1067190165
2043082587
2961479386
4033244915
4438519384
8158342623
8158342623
12528106804
12528106804
12528106804