Day \(\lfloor\pi^3\rfloor\)。
原神答辩缝合怪题目。
先考虑无向图的版本怎么做。套路地，考虑时间倒流，然后就变成了加边、改点权、查询连通块前 \(k\) 大之和，线段树合并加并查集维护即可。
现在的边有向，依旧考虑时间倒流，相当于将连通块改成了强连通分量。问题在于只有一条边不一定能使两条边处在同一个强连通分量内，这启示我们对边考虑。
如果能求出每条边 \(e_i(u,v)\)，\((u,v)\) 首次被加入同一个强连通块内的时刻 \(t_{i}\)，那么 \(u,v\) 就相当于连了无向边，这条边的存在时间区间为 \([t_i,q]\)，于是就可以转换为无向图的版本。
压力来到如何求出 \(t_{i}\)，显然越早加入的边的 \(t_i\) 越小，那么整体二分即可，每次分治答案区间 \([l,r]\)，则加入插入时间在 \([l,\text{mid}]\) 的所有边，跑一遍 tarjan，再递归右半边，撤销后递归左半边即可。复杂度两个 \(\log\)，注意不能遍历到孤立点否则就会爆炸。
// Problem: P5163 WD与地图
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5163
// Memory Limit: 500 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int N = 1e5 + 100;
const int M = 2e5 + 200;
const int W = 1e9;
int n, m, q, w[N], id[N], rt[N];
int dfc, top, dfn[N], low[N], in[N], st[N];
struct node { int op, x, y; } qr[M];
struct edge { int u, v, t, ti; } e[M], el[M], er[M];
map<pi, int> eid;
vector<int> g[N], p;
vector<ll> ans;
namespace DSU {
int fa[N], sz[N];
vector<int> op;
int gf(int x) { return x == fa[x] ? x : gf(fa[x]); }
int gff(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
void mrg(int x, int y) {
if ((x = gf(x)) == (y = gf(y))) return;
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y, sz[y] += sz[x], op.pb(x);
}
void del(int tp) {
while ((int)op.size() > tp) {
int x = op.back(); op.pop_back();
sz[fa[x]] -= sz[x], fa[x] = x;
}
}
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
op.clear();
}
}
using DSU::gf;
using DSU::gff;
using DSU::mrg;
using DSU::del;
using DSU::init;
namespace SGT {
int tot, lc[N << 6], rc[N << 6], ct[N << 6];
ll s[N << 6];
#define ls lc[x]
#define rs rc[x]
void upd(int l, int r, int p, int c, int &x) {
if (!x) x = ++tot;
ct[x] += c, s[x] += 1ll * c * p;
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid) upd(l, mid, p, c, ls);
else upd(mid + 1, r, p, c, rs);
}
void mrg(int l, int r, int &x, int y) {
if (!x || !y) return (x = x | y), void();
s[x] += s[y], ct[x] += ct[y];
if (l == r) return;
int mid = (l + r) >> 1;
mrg(l, mid, ls, lc[y]), mrg(mid + 1, r, rs, rc[y]);
}
ll qry(int l, int r, int k, int x) {
if (!x) return 0;
if (ct[x] <= k) return s[x];
if (l == r) return 1ll * k * l;
int mid = (l + r) >> 1;
if (ct[rs] >= k) return qry(mid + 1, r, k, rs);
return s[rs] + qry(l, mid, k - ct[rs], ls);
}
}
using SGT::upd;
using SGT::mrg;
using SGT::qry;
void clr() {
for (int i : p)
g[i].clear(), dfn[i] = low[i] = in[i] = 0;
p.clear(), dfc = top = 0;
}
void dfs(int u) {
dfn[u] = low[u] = ++dfc, st[++top] = u;
for (int v : g[u]) {
if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
else if (!in[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] != dfn[u]) return;
while (st[top] != u)
in[st[top]] = u, mrg(u, st[top]), top--;
in[u] = u, top--;
}
void conq(int l, int r, int s, int t) {
if (l > r || s == t) {
for (int i = l; i <= r; i++) e[i].ti = s;
return;
}
int mid = (s + t) >> 1, tp = DSU::op.size();
for (int i = l; i <= r; i++) {
int u = gf(e[i].u), v = gf(e[i].v);
if ((u ^ v) && e[i].t > mid)
g[u].pb(v), p.pb(u), p.pb(v);
}
for (int i : p)
if (!dfn[i]) dfs(i);
clr();
int cl = 0, cr = 0;
for (int i = l; i <= r; i++) {
int u = gf(e[i].u), v = gf(e[i].v);
if ((u == v) && e[i].t > mid) er[++cr] = e[i];
else el[++cl] = e[i];
}
for (int i = l; i <= l + cl - 1; i++) e[i] = el[i - l + 1];
for (int i = l + cl; i <= l + cl + cr - 1; i++) e[i] = er[i - l - cl + 1];
conq(l, l + cl - 1, s, mid), del(tp), conq(l + cl, l + cl + cr - 1, mid + 1, t);
}
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1, u, v; i <= m; i++)
cin >> u >> v, eid[mp(u, v)] = i, e[i] = (edge) { u, v, q };
for (int i = 1, op, x, y; i <= q; i++) {
cin >> op >> x >> y, qr[i] = (node) { op, x, y };
if (op == 1) e[eid[mp(x, y)]].t = i - 1;
else if (op == 2) w[x] += y;
}
sort(e + 1, e + m + 1, [](edge &x, edge &y) {
return x.t < y.t;
}), init(n), conq(1, m, 0, q);
sort(e + 1, e + m + 1, [](edge &x, edge &y) {
return x.ti < y.ti;
}), init(n);
for (int i = 1; i <= n; i++) upd(0, W, w[i], 1, rt[i]);
for (int i = q, j = m; i; i--) {
int op = qr[i].op, x = qr[i].x, y = qr[i].y;
while (j && e[j].ti >= i) {
int u = gff(e[j].u), v = gff(e[j].v);
if (u ^ v) DSU::fa[v] = u, mrg(0, W, rt[u], rt[v]);
j--;
}
if (op == 2) x = gff(x), upd(0, W, w[qr[i].x], -1, rt[x]), upd(0, W, w[qr[i].x] -= y, 1, rt[x]);
else if (op == 3) x = gff(x), ans.pb(qry(0, W, y, rt[x]));
}
reverse(ans.begin(), ans.end());
for (ll i : ans) cout << i << '\n';
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}