#1926. 城市建设

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

城市建设

城市建设

题目描述

标题: 城市建设 - Problem - QOJ.ac

#10361. 城市建设

Statistics

The problem was used in the following contests:

小 G 所居住的城市可以抽象为一张 N 个点 M 条边的 有向图。在城市建设的过程中,该城市的道路会发生一些变化;具体来说,一共会有 Q 次操作,包含以下两种类型:

  1. 给出点 p,再给出 tot 个数 ai,在图中加入 ai 到 p 的边。
  2. 给出点 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