luogu#P5163. WD与地图

WD与地图

题目背景

WD 整日沉浸在地图中,无法自拔……

题目描述

CX 让 WD 研究的地图可以看做是 nn 个点,mm 条边的有向图,由于政府正在尝试优化人民生活,他们会废弃一些无用的道路来把省下的钱用于经济建设。

城市都有各自的发达程度 sis_i。为了方便管理,政府将整个地图划分为一些地区,两个点 u,vu,v 在一个地区当且仅当 u,vu,v 可以互相到达。政府希望知道一些时刻某个地区的前 kk 发达城市的发达程度总和,以此推断建设的情况。

也就是说,共有三个操作:

1 a b 表示政府废弃了从 aa 连向 bb 的边,保证这条边存在。

2 a b 表示政府把钱用于建设城市 aa,使其发达程度增加 bb

3 a b 表示政府希望知道 aa 城市所在地区发达程度前 bb 大城市的发达程度之和。如果地区中的城市不足 bb 个输出该地区所有城市的发达程度总和。

输入格式

第一行两个数 n,m,qn,m,q,表示共 nn 个点,mm 条边,qq 次询问。

第二行 nn 个正整数,表示 sis_i,即每个城市的发达程度。

接下来 mm 行每行两个数 u,vu,v,表示初始时有一条从 uu 连向 vv 的边。

接下来 qq 行,表示 qq 组询问,格式如题目描述。

输出格式

对于每个询问操作,输出一个数,表示发达程度之和。

5 8 8
4 2 1 1 3
2 5
4 2
5 3
1 3
4 5
5 1
1 5
1 4
3 3 1
1 4 5
3 3 3
3 4 1
3 1 5
3 2 4
1 5 3
2 3 4
1
1
4
10
10

提示

$subtask1(19pts):~n\le 100,000,~m\le 200,000,~q\le 200,000$,删除操作个数×m1,000,000\times m\le 1,000,000

$subtask2(39pts):~n\le 5,000,~m\le 8,000,~q\le 200,000$

$subtask3(42pts):~n\le 100,000,~m\le 200,000,~q\le 200,000$

保证任何时刻发达程度109\le 10^9,无重边(反向边不算重边)无自环。