いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど
問題概要
頂点数 
、辺数 
のグラフが与えられる。初期状態では各頂点に 
という値がついている (すべて 1 以上で disjoint)。以下の 2 タイプのクエリに 
回答えよ。
- type 1：頂点
を含む連結成分内で、
の値の最大値を求めよ。さらに最大となった箇所の 値を 0 で書き換えておく
- type 2：辺
を削除する
制約
考えたこと
一般に、グラフの辺削除クエリは答えるのが難しい。よってこういうのは逆から見るのが定石。つまり、クエリをすべて終えて削除し尽くした状態から開始して、辺をつないでいくのだ。
しかし一方では type 1 のクエリは、更新を含むクエリなので、その順に答えていかないと混乱してしまう。
こういうときは、Union-Find の連結状態を保存できる機能が欲しい。一つの方法として、「Union-Find のマージ過程を表す木」を構築する方法がある (詳細は略)。今回もバッチリ。
Union-Find のマージ過程を表す木では、頂点 
と頂点 がマージされた瞬間に形成されたグループに対応する超頂点を用意していく。そしてその木を Euler Tour することで、そのときそのときのグループが「区間」として取り出せるのだ。
よって、今回の type 1 の操作も
- ある区間の最大値を求める
- その最大値を 0 で更新する
という操作だとみなせるので、セグ木で扱える。計算量は 
。
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> par;
UnionFind() { }
UnionFind(int n) : par(n, -1) { }
void init(int n) { par.assign(n, -1); }
int root(int x) {
if (par[x] < 0) return x;
else return par[x] = root(par[x]);
}
bool issame(int x, int y) {
return root(x) == root(y);
}
bool merge(int x, int y) {
x = root(x); y = root(y);
if (x == y) return false;
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
return true;
}
int size(int x) {
return -par[root(x)];
}
};
template<class Monoid> struct RMQ {
Monoid INF;
int SIZE_R;
vector<pair<Monoid,int> > dat;
RMQ() {}
RMQ(int n, const Monoid &inf): INF(inf) {
init(n, inf);
}
void init(int n, const Monoid &inf) {
INF = inf;
SIZE_R = 1;
while (SIZE_R < n) SIZE_R *= 2;
dat.assign(SIZE_R * 2, pair<Monoid,int>(INF, -1));
}
void set(int a, const Monoid &v) { dat[a + SIZE_R] = make_pair(v, a); }
void build() {
for (int k = SIZE_R - 1; k > 0; --k) {
dat[k] = max(dat[k*2], dat[k*2+1]);
}
}
void update(int a, const Monoid &v) {
int k = a + SIZE_R;
dat[k] = make_pair(v, a);
while (k >>= 1) dat[k] = max(dat[k*2], dat[k*2+1]);
}
pair<Monoid,int> get(int a, int b) {
pair<Monoid,int> vleft = make_pair(INF, -1), vright = make_pair(INF, -1);
for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
if (left & 1) vleft = max(vleft, dat[left++]);
if (right & 1) vright = max(dat[--right], vright);
}
return max(vleft, vright);
}
inline Monoid operator [] (int a) { return dat[a + SIZE_R].first; }
void print() {
for (int i = 0; i < SIZE_R; ++i) {
Monoid val = (*this)[i];
if (val != INF) cout << val;
else cout << "INF";
if (i != SIZE_R-1) cout << ",";
}
cout << endl;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, M, Q;
cin >> N >> M >> Q;
vector<int> C(N), X(M), Y(M);
for (int i = 0; i < N; ++i) cin >> C[i];
for (int i = 0; i < M; ++i) cin >> X[i] >> Y[i], --X[i], --Y[i];
vector<int> type(Q), id(Q);
set<int> delete_edge;
for (int i = 0; i < Q; ++i) {
cin >> type[i] >> id[i];
--id[i];
if (type[i] == 2) delete_edge.insert(id[i]);
}
UnionFind uf(N);
vector<vector<int>> tree(N*2-1);
vector<int> ancestor(N*2-1);
iota(ancestor.begin(), ancestor.end(), 0);
int V = N;
auto merge = [&](int x, int y) -> void {
x = uf.root(x), y = uf.root(y);
if (x == y) return;
uf.merge(x, y);
if (uf.root(x) != x) swap(x, y);
tree[V].push_back(ancestor[x]);
tree[V].push_back(ancestor[y]);
ancestor[x] = V++;
};
for (int i = 0; i < M; ++i) {
if (delete_edge.count(i)) continue;
merge(X[i], Y[i]);
}
vector<int> qnode(Q, -1);
for (int i = Q-1; i >= 0; --i) {
if (type[i] == 2) merge(X[id[i]], Y[id[i]]);
else qnode[i] = ancestor[uf.root(id[i])];
}
vector<int> left(N*2-1), right(N*2-1);
int iter = 0;
RMQ<int> rmq(N, -(1LL<<29));
auto dfs = [&](auto self, int v) -> void {
left[v] = iter;
if (tree[v].empty()) rmq.set(iter++, C[v]);
for (auto ch: tree[v]) self(self, ch);
right[v] = iter;
};
for (int v = 0; v < N; ++v) {
if (uf.root(v) != v) continue;
dfs(dfs, ancestor[v]);
}
rmq.build();
vector<int> res(Q, -1);
for (int q = 0; q < Q; ++q) {
if (type[q] == 2) continue;
int v = qnode[q];
auto tmp = rmq.get(left[v], right[v]);
rmq.update(tmp.second, 0);
res[q] = tmp.first;
}
for (auto val: res) if (val != -1) cout << val << endl;
}
別解：Undo 付き Union-Find
同じように操作を逆順に併合していって、改めてクエリの先頭からこなしていく方法も考えられそう。
type 2 の辺削除クエリは、undo 付き Union-Find の undo 機能によって実現できる (その辺削除がグループを分断するものであるかどうかはあらかじめ求めておく、分断するものでない場合は undo しない)。
