多校比赛的签到题，难度颇高。
HDOJ問題ページへのリンクリ
無向グラフ\(G=(V,E),|V|=n,|E|=m\)が与えられ、各頂点には重み\(a_i\)が設定されている。\(S_i=\{a_j\mid (i,j)\in E\}\)と定義される。支持する操作は2種類あり、\(q\)回処理する：
- \(\texttt1\ x\ y)：(a_x=y)と更新する；
- \(\texttt2\ x)：(\mathrm{mex}(S_x))をを求める。
\(n,m\in\left[1,10^5\right],a_i\in\left[0,10^9\right])。複数テストケースあり、最大10ケース。\(\mathrm{TL}=3\mathrm s)。
以下では\(n,m\)を同一規模として、計算量解析では\(n\)で表現する。
グラフ上のクエリ問題では、平方分割（根号分治）が有効なアプローチとなる。閾値\(lim\)を設定し、次数が\(lim\)以下の頂点を低次数頂点、それ以上の頂点を高次数頂点と分類する。低次数頂点の次数は最大\(O(lim))、高次数頂点数は最大\(O!\left(\dfrac n{lim}\right))（全次数和が\(2m\)であることから導出可能）という優れた性質が得られる。
これにより四つのケースに分類できる：低次数頂点の更新、低次数頂点のクエリ、高次数頂点の更新、高次数頂点のクエリ。
まず重要な補題として、(\mathrm{mex}(S)=O(|S|))が成り立つ。\(S=\{0,1,2,\dots\}\)の場合に最大値をとることを利用すれば容易く証明できる。低次数頂点\(x\)の次数は\(O(lim)\)程度なので、(\mathrm{mex}(S_x))も\(O(lim)\)レベルであり、特別なデータ構造を保持する必要はない。\(0\)から\(n\)までの範囲のグローバルなbool配列を外部に用意し（\(n\)を超える重みは\(n\)とみなして問題ない）、クエリ時に隣接頂点の重みを\(true\)に設定し、\(0\)から順に触れて答えを見つけた後、元に戻す Brute Force 手法を採用する。
高次数頂点のクエリに対しては、高速な応答を可能にするデータ構造を保持する必要がある。更新操作（低次数頂点・高次数頂点の両方）においては、影響を受ける全高次数頂点（\(O!\left(\dfrac m{lim}\right)\)個程度）のデータ構造を更新する。
集合に対するクエリ処理において、平衡二分木が有効である。本稿ではfhq-Treapを採用する。重み更新時の平衡二分木操作は挿入と削除のみで\(O(\log n)\)。mex探索では二分探索类似的考え方を利用し、左部分木が「満タン」（先頭から現在ノードまでに隙間がない）の場合は右部分木へ、否则は左部分木へ進む。\(O(\log n)\)で処理が完了する。
各操作の計算量を整理する：
- 低次数頂点更新：二分木挿入＋削除、\(O!\left(\dfrac n{lim}\log n\right)\)；
- 低次数頂点クエリ：Brute Force、\(O(lim)\)；
- 高次数頂点更新：二分木挿入＋削除、\(O!\left(\dfrac n{lim}\log n\right)\)；
- 高次数頂点クエリ：二分木探索、\(O(\log n)\)。
全体の計算量は\(O!\left(q\left(\dfrac n{lim}\log n+lim\right)\right))。相加相乗平均により、\(lim=\sqrt{m\log n}\)の場合に最適化し、\(O!\left(n\sqrt{n\log n}\right)\)となる。
試合中にこの計算量は危険だと感じた上、定数項も大きかった。提出したところ案の定TLEを食らい、紆余曲折を経て（TLE→RE→WA→AC）ようやくACできた。
以下がTreapを用いた実装である：
#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
unsigned rnd;
int left, right, size, val, maxv;
};
struct BalancedTree{
int tree_root, node_cnt;
vector<TreeNode> nodes;
BalancedTree(int capacity){
nodes.resize(capacity * 2 + 5);
node_cnt = 0;
tree_root = 0;
}
void update(int p){
if(p == 0) return;
nodes[p].size = getSize(nodes[p].left) + 1 + getSize(nodes[p].right);
nodes[p].maxv = max(nodes[p].val,
max(nodes[getSize(nodes[p].left)].maxv, nodes[getSize(nodes[p].right)].maxv));
}
int getSize(int p){ return p ? nodes[p].size : 0; }
pair<int,int> split(int root, int key){
if(root == 0) return {0, 0};
pair<int,int> result;
if(nodes[root].val < key){
auto sp = split(nodes[root].right, key);
nodes[root].right = sp.first;
update(root);
result = {root, sp.second};
} else {
auto sp = split(nodes[root].left, key);
nodes[root].left = sp.second;
update(root);
result = {sp.first, root};
}
return result;
}
int merge(int left, int right){
if(left == 0 || right == 0) return left | right;
if(nodes[left].rnd < nodes[right].rnd){
nodes[left].right = merge(nodes[left].right, right);
update(left);
return left;
} else {
nodes[right].left = merge(left, nodes[right].left);
update(right);
return right;
}
}
int newNode(int value){
nodes[++node_cnt] = {randomUInt(), 0, 0, 1, value, value};
return node_cnt;
}
unsigned randomUInt(){
static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
return rng();
}
void insert(int value){
auto sp = split(tree_root, value);
tree_root = merge(merge(sp.first, newNode(value)), sp.second);
}
void erase(int value){
auto sp = split(tree_root, value);
auto sp2 = split(sp.second, value + 1);
tree_root = merge(sp.first, sp2.second);
}
int findMex(int node = 0, int start = 0){
if(node == 0) return start;
int leftSize = getSize(nodes[node].left);
if(nodes[node].val - start == leftSize){
return findMex(nodes[node].right, nodes[node].val + 1);
}
return findMex(nodes[node].left, start);
}
};
さらに効率的な\(O(n\sqrt n)\)解法が存在する（dlsの解法参照）。
前述の計算量解析から分かるように、二分木クエリの実行回数は\(O(q)\)であるのに対し、挿入・削除は\(O\left(q\dfrac n{lim}\right)\)回である。両者の計算量クラスが同一である点が键となる。クエリの計算量を犠牲にして、挿入・削除を高速化することは可能か？
\(O(1)\)で挿入・削除可能なデータ構造として、ブロック分割が挙げられる。値域に対してブロック化し、各ブロックのサイズを\(sz1\)とする。挿入・削除時は\(O(1)\)で直接更新して終了。クエリ時は最初の空ブロックを見つけ、内部で線形探索を行う。各ブロック内の要素存在状態を保持するbool配列が必要となり、クエリ計算量は\(O!\left(sz1+\dfrac n{sz1}\right)\)となる。\(sz1=\sqrt n\)の場合に最適化し、全体の計算量は\(O(n\sqrt n)\)に到達する。
ブロック分割による実装は以下の通りである：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int BLOCK_SIZE = 330;
const int MAXBLOCK = 340;
int n, m, q;
int weight[MAXN + 5];
vector<int> adjacency[MAXN + 5];
vector<int> highDegreeAdj[MAXN + 5];
struct BlockStructure{
int blockCnt, blockLen;
struct Block{
int left, right;
int count;
bool present[BLOCK_SIZE];
};
vector<Block> blocks;
void initialize(int totalElements){
blockLen = sqrt(totalElements) + 1;
blockCnt = (totalElements + blockLen - 1) / blockLen;
blocks.resize(blockCnt + 1);
for(int i = 0; i < blockCnt; i++){
blocks[i].left = i * blockLen;
blocks[i].right = min((i + 1) * blockLen - 1, totalElements);
blocks[i].count = 0;
fill(blocks[i].present, blocks[i].present + blockLen, false);
}
}
void addElement(int value){
int idx = value / blockLen;
if(idx >= blockCnt) idx = blockCnt - 1;
int pos = value - blocks[idx].left;
if(pos >= 0 && pos < blockLen){
blocks[idx].present[pos] = true;
blocks[idx].count++;
}
}
void removeElement(int value){
int idx = value / blockLen;
if(idx >= blockCnt) idx = blockCnt - 1;
int pos = value - blocks[idx].left;
if(pos >= 0 && pos < blockLen){
blocks[idx].present[pos] = false;
blocks[idx].count--;
}
}
int calculateMex(){
for(int i = 0; i < blockCnt; i++){
int capacity = blocks[i].right - blocks[i].left + 1;
if(blocks[i].count < capacity){
for(int j = blocks[i].left; j <= blocks[i].right; j++){
int pos = j - blocks[i].left;
if(!blocks[i].present[pos]) return j;
}
}
}
return n;
}
};
BlockStructure blocks[MAXBLOCK];
int occurrence[MAXBLOCK][MAXN + 5];
int highDegreeId[MAXN + 5];
bool visited[MAXN + 5];
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
adjacency[i].clear();
highDegreeAdj[i].clear();
cin >> weight[i];
if(weight[i] > n) weight[i] = n;
}
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adjacency[u].push_back(v);
adjacency[v].push_back(u);
}
int threshold = sqrt(m);
for(int i = 1; i <= n; i++){
for(int v : adjacency[i]){
if((int)adjacency[v].size() > threshold){
highDegreeAdj[i].push_back(v);
}
}
}
int highCount = 0;
for(int i = 1; i <= n; i++){
if((int)adjacency[i].size() > threshold){
highDegreeId[i] = highCount++;
blocks[highDegreeId[i]].initialize(n);
fill(occurrence[highDegreeId[i]], occurrence[highDegreeId[i]] + n + 1, 0);
for(int v : adjacency[i]){
if(occurrence[highDegreeId[i]][weight[v]] == 0){
blocks[highDegreeId[i]].addElement(weight[v]);
}
occurrence[highDegreeId[i]][weight[v]]++;
}
}
}
cin >> q;
while(q--){
int type, x;
cin >> type >> x;
if(type == 1){
int y;
cin >> y;
if(y > n) y = n;
for(int v : highDegreeAdj[x]){
int id = highDegreeId[v];
occurrence[id][weight[x]]--;
if(occurrence[id][weight[x]] == 0){
blocks[id].removeElement(weight[x]);
}
if(occurrence[id][y] == 0){
blocks[id].addElement(y);
}
occurrence[id][y]++;
}
weight[x] = y;
} else {
if((int)adjacency[x].size() <= threshold){
for(int v : adjacency[x]){
visited[weight[v]] = true;
}
int answer = 0;
while(visited[answer]) answer++;
cout << answer << '\n';
for(int v : adjacency[x]){
visited[weight[v]] = false;
}
} else {
cout << blocks[highDegreeId[x]].calculateMex() << '\n';
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testcases;
cin >> testcases;
while(testcases--) solve();
return 0;
}