来一发分治题解吧。
感觉和单纯的整体二分还是有一点区别。
虽然整体二分也能看作分治就是了。
思路
首先时光倒流。
删边改为加边。
这没有什么好说的，比较基础。
我们考虑在不断加边时，每两个点是在什么时候变成一个强连通分量里面的。
考虑分治。
首先在 \([l,r]\) 内选取中点 \(\text{mid}\)。
其中 \([l,r]\) 维护的是时间。
然后将时间小于等于 \(\text{mid}\) 的边加入。
跑一次缩点。
这时我们可以发现，边集自然而然的分为了几类。
对于时间小于等于 \(\text{mid}\) 的边：
-
连接在同一个强连通分量的边。
我们发现它在前面也会发生作用，所以丢向左边。
-
连接在不同的强连通分量的边。
我们发现它在后面可能发生作用，所以丢向右边。
对于时间晚于 \(\text{mid}\) 的边，也就是暂时没有加入图中的边：
-
连接在同一个强连通分量的边。
我们发现它已经没有用处了，可以直接丢掉。
-
连接在不同的强连通分量的边。
我们发现它在后面可能发生作用，所以丢向右边。
这样，我们就把每一条边恰好的分散在了每一层的各个位置。
假如最后分治到了两端时间相同。
那么我们就可以直接把相应的点也给缩起来。
强连通分量这一部分可以使用可撤销并查集来维护。
所以这部分的时间复杂度为 \(O(m\log m\log n)\) 的。
可以求出每个强连通分量的合并是在什么时候。
有了这个以后，其他的就比较简单了。
单点修，区间查，支持合并。
使用线段树合并可以做到 \(O(n\log n)\)。
这里用的是平衡树启发式合并（因为不影响最终复杂度）\(O(n\log n\log v)\)。
当然了。这个做法也可以拓展到接近单 \(\log\)。
前面的分治时不用可撤销并查集，直接使用 \(\text{tarjan}\) 的染色。
那么就可以直接用普通并查集了。
后面再使用线段树合并就可以了。
时间复杂度：\(O(m\alpha(n)\log m)\)。
当然我自己因为写的时候没想那么多直接写的双 \(\log\)。
Code
/**
* @file P5163.cpp
* @author mfeitveer
* @date 2023-11-24
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 200010;
const int mod = 998244353;
int n, m, q, tt, s[N], fa[N], sz[N];
int top, tot, vs[N], dfn[N], low[N], stk[N];
map<PII, int> mp; PII e[N], add[N], sk[N];
struct Node { int op, a, b; } d[N];
vector<int> to[N], edge; vector<PII> mer;
vector<tuple<int, int, int>> fin;
i64 ans[N];
inline int gf(int x)
{ return (x == fa[x] ? x : gf(fa[x])); }
inline void merge(int x, int y)
{
x = gf(x), y = gf(y);
if(x == y) return;
if(sz[x] > sz[y]) swap(x, y);
fa[x] = y, sz[y] += sz[x];
sk[++tt] = mp(x, y), mer.eb(x, y);
}
inline void rev(int t)
{
while(tt > t)
fa[sk[tt].x] = sk[tt].x,
sz[sk[tt].y] -= sz[sk[tt].x], tt--;
}
inline void tarjan(int x)
{
vs[x] = 1, dfn[x] = low[x] = ++tot, stk[++top] = x;
for(auto i : to[x])
if(!dfn[i]) tarjan(i), low[x] = min(low[x], low[i]);
else if(vs[i]) low[x] = min(low[x], dfn[i]);
if(dfn[x] == low[x])
{
vs[x] = 0;
while(stk[top--] != x)
vs[stk[top + 1]] = 0,
merge(stk[top + 1], x);
}
}
inline void solve(int l, int r)
{
if(l == r)
{
vector<int> node; tot = top = 0;
for(auto i : edge) if(gf(add[i].x) != gf(add[i].y))
to[gf(add[i].x)].eb(gf(add[i].y)), node.eb(gf(add[i].x));
for(auto i : node) dfn[i] = low[i] = vs[i] = 0;
for(auto i : node) if(!dfn[i]) tarjan(i);
for(auto i : mer) fin.eb(i.x, i.y, l); mer.clear();
for(auto i : node) to[i].clear();
return;
}
int mid = (l + r) >> 1, cur = tt;
vector<int> node{}; tot = top = 0;
for(auto i : edge) if(i <= mid && gf(add[i].x) != gf(add[i].y))
to[gf(add[i].x)].eb(gf(add[i].y)), node.eb(gf(add[i].x));
for(auto i : node) dfn[i] = low[i] = vs[i] = 0;
for(auto i : node) if(!dfn[i]) tarjan(i);
vector<int> ls, rs;
for(auto i : edge) if(gf(add[i].x) != gf(add[i].y))
rs.eb(i);
for(auto i : edge) if(i <= mid && gf(add[i].x) == gf(add[i].y))
ls.eb(i);
rev(cur); for(auto i : node) to[i].clear(); mer.clear();
edge = ls, solve(l, mid);
edge = rs, solve(mid + 1, r);
}
namespace Solve
{
const int N = ::N<<1;
int ls[N], rs[N], id[N], tot;
i64 sz[N], vl[N], al[N], rt[N], rd[N];
inline int nd(int x)
{ return ++tot, sz[tot] = 1, vl[tot] = al[tot] = x, rd[tot] = rand(), tot; }
inline void push(int x)
{ sz[x] = 1 + sz[ls[x]] + sz[rs[x]], al[x] = vl[x] + al[ls[x]] + al[rs[x]]; }
inline int mer(int x, int y)
{
if(!x || !y) return x | y;
if(rd[x] < rd[y]) return rs[x] = mer(rs[x], y), push(x), x;
return ls[y] = mer(x, ls[y]), push(y), y;
}
inline void spl(int p, int k, int &x, int &y)
{
if(!p) return x = y = 0, void();
if(k > sz[ls[p]])
spl(rs[p], k - sz[ls[p]] - 1, rs[x = p], y);
else spl(ls[p], k, x, ls[y = p]); push(p);
}
inline void spll(int p, int k, int &x, int &y)
{
if(!p) return x = y = 0, void();
if(k > vl[p]) spll(ls[p], k, x, ls[y = p]);
else spll(rs[p], k, rs[x = p], y); push(p);
}
inline int gf(int x)
{ return (fa[x] == x ? fa[x] : fa[x] = gf(fa[x])); }
inline void dfs(int x, int y)
{
if(!x) return;
dfs(ls[x], y), dfs(rs[x], y); int a, b;
spll(rt[y], vl[x], a, b);
ls[x] = rs[x] = 0, sz[x] = 1, al[x] = vl[x];
rt[y] = mer(a, mer(x, b));
}
inline void merge(int x, int y)
{
x = gf(x), y = gf(y);
if(sz[rt[x]] < sz[rt[y]])
swap(x, y);
fa[y] = x, dfs(rt[y], x);
}
inline void del(i64 &rt, i64 x)
{
int a, b, c;
spll(rt, x, a, b);
spl(a, sz[a] - 1, a, c);
rt = mer(a, b);
}
inline void ins(i64 &rt, i64 x)
{
int a, b; spll(rt, x, a, b);
rt = mer(a, mer(nd(x), b));
}
inline void solve()
{
int res = m, it = 0;
iota(fa + 1, fa + n + 1, 1);
fro(i, 1, q)
{
if(d[i].op == 1) res--;
if(d[i].op == 2) s[d[i].a] += d[i].b;
id[i] = res;
}
fro(i, 1, n) rt[i] = nd(s[i]);
pre(i, q, 1)
{
while(it < fin.size() && id[i] >= get<2>(fin[it]))
merge(get<0>(fin[it]), get<1>(fin[it])), it++;
if(d[i].op == 3)
{
int x = gf(d[i].a), y, z;
spl(rt[x], d[i].b, y, z);
ans[i] = al[y], rt[x] = mer(y, z);
}
else if(d[i].op == 2)
{
int x = gf(d[i].a), a, b;
del(rt[x], s[d[i].a]);
s[d[i].a] -= d[i].b;
ins(rt[x], s[d[i].a]);
}
}
}
}
inline void solve()
{
cin >> n >> m >> q; int tot{};
fro(i, 1, n) cin >> s[i];
fro(i, 1, m) cin >> e[i].x >> e[i].y, mp[e[i]] = 1;
fro(i, 1, q) cin >> d[i].op >> d[i].a >> d[i].b, ans[i] = -1;
fro(i, 1, q) if(d[i].op == 1)
add[++tot] = mp(d[i].a, d[i].b), mp[mp(d[i].a, d[i].b)] = 0;
for(auto i : mp) if(i.y == 1)
add[++tot] = i.x;
reverse(add + 1, add + tot + 1);
fro(i, 1, tot) edge.eb(i);
iota(fa + 1, fa + n + 1, 1);
fill(sz + 1, sz + n + 1, 1);
solve(1, tot), Solve::solve();
fro(i, 1, q) if(ans[i] != -1) cout << ans[i] << "\n";
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 500;
cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
srand(random_device{}()), solve();
return 0;
}