首先不用说，倒着操作。整体二分来做强连通分量，然后线段树合并，这题就做完了。
// powered by c++11
// by Isaunoya
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)
#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)
using namespace std;
using db = double;
using ll = long long;
using uint = unsigned int;
#define int long long
using pii = pair<int, int>;
#define ve vector
#define Tp template
#define all(v) v.begin(), v.end()
#define sz(v) ((int)v.size())
#define pb emplace_back
#define fir first
#define sec second
// the cmin && cmax
Tp<class T> void cmax(T& x, const T& y) {
if (x < y) x = y;
}
Tp<class T> void cmin(T& x, const T& y) {
if (x > y) x = y;
}
// sort , unique , reverse
Tp<class T> void sort(ve<T>& v) { sort(all(v)); }
Tp<class T> void unique(ve<T>& v) {
sort(all(v));
v.erase(unique(all(v)), v.end());
}
Tp<class T> void reverse(ve<T>& v) { reverse(all(v)); }
const int SZ = 0x191981;
struct FILEIN {
~FILEIN() {}
char qwq[SZ], *S = qwq, *T = qwq, ch;
char GETC() { return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T) ? EOF : *S++; }
FILEIN& operator>>(char& c) {
while (isspace(c = GETC()))
;
return *this;
}
FILEIN& operator>>(string& s) {
while (isspace(ch = GETC()))
;
s = ch;
while (!isspace(ch = GETC())) s += ch;
return *this;
}
Tp<class T> void read(T& x) {
bool sign = 1;
while ((ch = GETC()) < 0x30)
if (ch == 0x2d) sign = 0;
x = (ch ^ 0x30);
while ((ch = GETC()) > 0x2f) x = x * 0xa + (ch ^ 0x30);
x = sign ? x : -x;
}
FILEIN& operator>>(int& x) { return read(x), *this; }
FILEIN& operator>>(signed& x) { return read(x), *this; }
FILEIN& operator>>(unsigned& x) { return read(x), *this; }
} in;
struct FILEOUT {
const static int LIMIT = 0x114514;
char quq[SZ], ST[0x114];
signed sz, O;
~FILEOUT() { sz = O = 0; }
void flush() {
fwrite(quq, 1, O, stdout);
fflush(stdout);
O = 0;
}
FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }
FILEOUT& operator<<(string str) {
if (O > LIMIT) flush();
for (char c : str) quq[O++] = c;
return *this;
}
Tp<class T> void write(T x) {
if (O > LIMIT) flush();
if (x < 0) {
quq[O++] = 0x2d;
x = -x;
}
do {
ST[++sz] = x % 0xa ^ 0x30;
x /= 0xa;
} while (x);
while (sz) quq[O++] = ST[sz--];
return;
}
FILEOUT& operator<<(int x) { return write(x), *this; }
FILEOUT& operator<<(signed x) { return write(x), *this; }
FILEOUT& operator<<(unsigned x) { return write(x), *this; }
} out;
int n, m, qwq;
const int maxn = 1e6 + 61;
const int lim = 1e9;
struct edge {
int v, nxt;
} e[maxn];
int head[maxn], tot = 0;
struct node {
int u, v, t;
} a[maxn], b[maxn];
vector<node> path[maxn];
int rt[maxn], ls[maxn << 5], rs[maxn << 5], s[maxn << 5], sum[maxn << 5];
int fa[maxn], low[maxn], dfn[maxn], st[maxn], ins[maxn], q[maxn];
int type[maxn], aa[maxn], bb[maxn], val[maxn], cnt = 0, top = 0, h = 0, idx = 0;
set<pii> se;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) {
if ((x = find(x)) ^ (y = find(y))) fa[x] = y;
}
void tarjan(int u) {
dfn[u] = low[u] = ++idx, st[++top] = u, ins[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v);
cmin(low[u], low[v]);
} else if (ins[v])
cmin(low[u], dfn[v]);
}
if (low[u] == dfn[u]) do {
ins[st[top]] = 0, unite(st[top], u);
} while (st[top--] != u);
}
void upd(int& p, int l, int r, int x, int v) {
if (!p) p = ++cnt;
s[p] += v, sum[p] += v * x;
if (l == r) return;
int mid = l + r >> 1;
(x <= mid) ? upd(ls[p], l, mid, x, v) : upd(rs[p], mid + 1, r, x, v);
}
int qry(int p, int l, int r, int k) {
if (k >= s[p]) return sum[p];
if (l == r) return l * k;
int mid = l + r >> 1, x = s[rs[p]];
if (x >= k)
return qry(rs[p], mid + 1, r, k);
else
return sum[rs[p]] + qry(ls[p], l, mid, k - x);
}
int merge(int x, int y) {
if (!x || !y) return x | y;
sum[x] += sum[y], s[x] += s[y];
ls[x] = merge(ls[x], ls[y]), rs[x] = merge(rs[x], rs[y]);
return x;
}
void solve(int l, int r, int ql, int qr) {
if (l == r) {
for (int i = ql; i <= qr; i++) path[l].push_back(a[i]);
return;
}
if (ql == qr) {
if (find(a[ql].u) == find(a[ql].v)) path[a[ql].t].push_back(a[ql]);
return;
}
int mid = l + r >> 1;
tot = h = 0;
for (int i = ql; i <= qr; i++)
if (a[i].t <= mid) {
int u = find(a[i].u), v = find(a[i].v);
q[++h] = u, q[++h] = v;
head[u] = head[v] = 0;
}
for (int i = 1; i <= h; i += 2) {
int u = q[i], v = q[i + 1];
e[++tot] = { v, head[u] }, head[u] = tot;
dfn[u] = low[u] = ins[u] = 0;
dfn[v] = low[v] = ins[v] = 0;
}
top = idx = 0;
for (int i = 1; i <= h; i++)
if (!dfn[q[i]]) tarjan(q[i]);
vector<pii> mp;
int t1 = 0, t2 = ql;
h = 1;
for (int i = ql; i <= qr; i++) {
int flag = 0;
if (a[i].t <= mid) {
int u = q[h], v = q[h + 1];
h += 2;
if (find(u) == find(v)) flag = 1;
mp.push_back({ u, fa[u] }), mp.push_back({ v, fa[v] });
}
if (flag)
a[t2++] = a[i];
else
b[++t1] = a[i];
}
for (int i = t2; i <= qr; i++) a[i] = b[i - t2 + 1];
h--;
for (int i = 1; i <= h; i++) fa[q[i]] = q[i];
if (ql < t2) solve(l, mid, ql, t2 - 1);
for (auto x : mp) fa[x.first] = x.second;
if (qr >= t2) solve(mid + 1, r, t2, qr);
}
signed main() {
#ifdef _WIN64
freopen("testdata.in", "r", stdin);
#else
ios_base ::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
#endif
// code begin.
in >> n >> m >> qwq;
for (int i = 1; i <= n; i++) in >> val[i], fa[i] = i;
for (int i = 1; i <= m; i++) {
int u, v;
in >> u >> v, se.insert({ u, v });
}
for (int i = qwq; i; i--) {
int op, x, y;
in >> op >> x >> y;
type[i] = op, aa[i] = x, bb[i] = y;
if (op == 1) a[++tot] = { x, y, i }, se.erase({ x, y });
if (op == 2) val[x] += y;
}
for (pii x : se) a[++tot] = { x.first, x.second, 0 };
solve(0, qwq + 1, 1, m), tot = top = 0, type[0] = 1;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) upd(rt[i], 1, lim, val[i], 1);
vector<int> ans;
for (int i = 0; i <= qwq; i++) {
if (type[i] == 1) {
for (auto x : path[i]) {
x.u = find(x.u), x.v = find(x.v);
if (x.u == x.v) continue;
fa[x.v] = x.u, rt[x.u] = merge(rt[x.u], rt[x.v]);
}
}
if (type[i] == 2) {
int u = find(aa[i]);
upd(rt[u], 1, lim, val[aa[i]], -1);
val[aa[i]] -= bb[i];
upd(rt[u], 1, lim, val[aa[i]], 1);
}
if (type[i] == 3) {
int u = find(aa[i]);
ans.push_back(qry(rt[u], 1, lim, bb[i]));
}
}
reverse(ans);
for (int x : ans) out << x << '\n';
return out.flush(), 0;
// code end.
}