題目大意
給定一棵 N 個(gè)節(jié)點(diǎn)的樹(shù)，每個(gè)點(diǎn)有各自的點(diǎn)權(quán) pi 器罐，但是邊的權(quán)值都是 1 （也可以認(rèn)為沒(méi)有邊權(quán)）。保證所有點(diǎn)的點(diǎn)權(quán)是所有小于 N 的非負(fù)整數(shù)的一個(gè)排列。
定義函數(shù) y = mex(S) 归薛，其中 S 表示一個(gè)非負(fù)整數(shù)集， y 表示不在這個(gè)集合里的最小非負(fù)整數(shù)匪蝙。
現(xiàn)有 Q 組詢問(wèn)主籍。詢問(wèn)有兩個(gè)類型：
- 交換兩個(gè)給定點(diǎn)的點(diǎn)權(quán)
- 如果將樹(shù)上的任意一條簡(jiǎn)單路徑 L 經(jīng)過(guò)的點(diǎn)的點(diǎn)權(quán)看作一個(gè)非負(fù)整數(shù)集，則可求得其對(duì)應(yīng)的 mex(L) 」淝颍現(xiàn)要求輸出當(dāng)前樹(shù)上所有路徑的最大 mex 值千元，即 max(mex(L))
題目保證 N 和 Q 不超過(guò) 2 × 105
分析
這個(gè)題剛看到的時(shí)候感覺(jué)有兩個(gè)可能的切入點(diǎn)。題目中間定義的這個(gè) mex 函數(shù)可以算是對(duì)于前綴的查詢颤绕，然后交換點(diǎn)權(quán)可以看成兩次連續(xù)的點(diǎn)修改幸海。這也就是說(shuō)這題可能可以用樹(shù)狀數(shù)組或者線段樹(shù)解決。第二個(gè)點(diǎn)就是題目中多次提到的路徑奥务，讓我有一種樹(shù)剖的感覺(jué)物独。但是鑒于我不會(huì)樹(shù)剖所以這條路就沒(méi)往下想...
嘗試在線段樹(shù)的框架下考慮這個(gè)問(wèn)題，如果線段 [L, R] 對(duì)應(yīng)的線段樹(shù)節(jié)點(diǎn)表示對(duì)于閉區(qū)間 [L, R] 中的所有數(shù)都出現(xiàn)的最短簡(jiǎn)單路徑（當(dāng)然也可能無(wú)解）氯葬，假如我們可以快速維護(hù)這棵線段樹(shù)挡篓，那么每次二型詢問(wèn)就可以在 O(T × log2n) 內(nèi)通過(guò)二分地詢問(wèn)線段樹(shù)完成（其中 T 表示單次維護(hù)時(shí)間）；每次一型詢問(wèn)可以分拆成兩個(gè)點(diǎn)修改帚称，修改葉子節(jié)點(diǎn)以后維護(hù)它的所有祖先官研，復(fù)雜度 O(T × logn) ∈郎保看起來(lái)算是一個(gè)不那么爆炸的復(fù)雜度了阀参。
下面的問(wèn)題就是如何維護(hù)（合并）兩個(gè)鄰接區(qū)間了。首先瞻坝，線段樹(shù)的所有葉子區(qū)間都有解（寬度為 1）蛛壳。其次，父節(jié)點(diǎn)有解的必要（但是不充分）條件是它的兩個(gè)兒子都有解所刀。然后我仔細(xì)想了一下衙荐，樹(shù)上兩條路徑可以合并的充要條件應(yīng)該是這些：
- 兩條路徑滿足包含關(guān)系，即某條路徑的兩個(gè)端點(diǎn)都在另一條路徑上
- 兩條路徑各有一個(gè)端點(diǎn)在另一條路徑上
- 可以從兩條路徑中各選一個(gè)端點(diǎn)使得剩下的兩個(gè)端點(diǎn)在被選的兩個(gè)端點(diǎn)確定的路徑上
大概感受了一下這些條件跟存在四個(gè)端點(diǎn)中的兩個(gè)使得剩下兩個(gè)在它們確定的路徑上是等價(jià)的浮创。于是就轉(zhuǎn)化成了判斷點(diǎn)是否在路徑上的問(wèn)題忧吟。
這個(gè)問(wèn)題可以用 LCA 來(lái)解決， 假設(shè)一條路徑的端點(diǎn)為 E1 和 E2 斩披，點(diǎn) M 在這條路徑上的充要條件是：
記 A = LCA(E1, E2) 則
(LCA(E1, M) == M || LCA(E2, M) == M) && LCA(A, M) == A
LCA 的話如果用離散表預(yù)處理的話可以做到 O(1) 查詢溜族。這樣就差不多想清楚了讹俊。
然后交了，TLE...
仔細(xì)算了一下復(fù)雜度煌抒，這個(gè) LCA 雖然是 O(1) 的查詢仍劈，但是在極端情況下一次維護(hù)竟然能查詢 48 次 LCA 。加上 LCA 本身常數(shù)也不小寡壮，復(fù)雜度會(huì)非常爆炸...
所幸我很快就發(fā)現(xiàn)贩疙，二分在最壞情況下會(huì)有非常多的重復(fù)詢問(wèn)（因?yàn)槊看卧儐?wèn)都是 [1, x] 的區(qū)間）而且詢問(wèn)主要慢在合并區(qū)間的操作上...不過(guò)這似乎可以一次完成。即先找到最左邊的合法線段况既，然后對(duì)于該線段的兄弟節(jié)點(diǎn)这溅，嘗試將其左邊部分二分地合并到可行解尾部并更新答案。這樣修改以后單次二型操作的理論復(fù)雜度也下降到 O(logn)棒仍。然后剪了剪枝就過(guò)了...
代碼
總復(fù)雜度為 O((n + q) × logn)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
const int maxn = 212345;
struct Seg {
int l, r, lv, rv;
} T[maxn << 2];
vector<int> G[maxn];
int n, q, clk, st[maxn << 1][19], in[maxn], out[maxn], dep[maxn], w[maxn];
void dfs(int u, int p) {
in[u] = ++clk;
st[clk][0] = u;
for (int v : G[u]) {
if (v == p) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
st[++clk][0] = u;
}
out[u] = clk;
}
void rmq_init() {
FOR(i, 1, clk) FOR(j, 1, 18) {
st[i][j] = st[i][j - 1];
int val = i - (1 << j - 1);
if (val > 0 && dep[st[val][j - 1]] < dep[st[i][j]])
st[i][j] = st[val][j - 1];
}
}
inline int rmq(int l, int r) {
int val = floor(log(r - l + 1) / log(2));
int u = st[l + (1 << val) - 1][val], v = st[r][val];
return dep[u] < dep[v] ? u : v;
}
inline int lca(int u, int v) {
if (in[u] > in[v]) swap(u, v);
return rmq(in[u], in[v]);
}
inline bool between(int e1, int e2, int m) {
int a = lca(e1, e2);
return lca(a, m) == a && (lca(e1, m) == m || lca(e2, m) == m);
}
inline pii get(const int *buff) {
if (between(buff[0], buff[1], buff[2]) && between(buff[0], buff[1], buff[3]))
return mp(buff[0], buff[1]);
if (between(buff[0], buff[2], buff[1]) && between(buff[0], buff[2], buff[3]))
return mp(buff[0], buff[2]);
if (between(buff[0], buff[3], buff[1]) && between(buff[0], buff[3], buff[2]))
return mp(buff[0], buff[3]);
if (between(buff[1], buff[2], buff[0]) && between(buff[1], buff[2], buff[3]))
return mp(buff[1], buff[2]);
if (between(buff[1], buff[3], buff[0]) && between(buff[1], buff[3], buff[2]))
return mp(buff[1], buff[3]);
if (between(buff[2], buff[3], buff[0]) && between(buff[2], buff[3], buff[1]))
return mp(buff[2], buff[3]);
return mp(-1, -1);
}
void maintain(int o) {
int lson = o << 1, rson = o << 1 | 1;
if (T[lson].lv == -1 || T[rson].lv == -1) {
T[o].lv = T[o].rv = -1;
return;
}
if (T[lson].lv == T[lson].rv) {
T[o].lv = T[lson].lv;
T[o].rv = T[rson].lv;
return;
}
int buff[] = {T[lson].lv, T[lson].rv, T[rson].lv, T[rson].rv};
auto tmp = get(buff);
T[o].lv = tmp._1;
T[o].rv = tmp._2;
}
int solve(int o, int &p1, int &p2) {
if (T[o].lv == -1) {
if (T[o].l == T[o].r) return T[o].l - 1;
int flag = solve(o << 1, p1, p2);
return flag == T[o << 1].r ? solve(o << 1 | 1, p1, p2) : flag;
}
int buff[] = {p1, p2, T[o].lv, T[o].rv};
auto check = get(buff);
if (check._1 != -1) {
p1 = check._1, p2 = check._2;
return T[o].r;
}
if (T[o].lv == T[o].rv) return T[o].l - 1;
int flag = solve(o << 1, p1, p2);
return flag == T[o << 1].r ? solve(o << 1 | 1, p1, p2) : flag;
}
int query(int o) {
while (T[o].lv == -1) o <<= 1;
pii tmp = mp(T[o].lv, T[o].rv);
return solve(o | 1, tmp._1, tmp._2);
}
void update(int o, int pos, int u) {
if (T[o].l == T[o].r) {
T[o].lv = T[o].rv = u;
return;
}
int M = T[o].l + T[o].r >> 1;
pos <= M ? update(o << 1, pos, u) : update(o << 1 | 1, pos, u);
maintain(o);
}
void build(int o, int l, int r) {
T[o].l = l, T[o].r = r;
T[o].lv = T[o].rv = -1;
if (l != r) {
int m = l + r >> 1;
build(o << 1, l, m);
build(o << 1 | 1, m + 1, r);
}
}
int main() {
scanf("%d", &n);
build(1, 1, 1 << 18);
FOR(i, 1, n) {
scanf("%d", w + i);
w[i]++;
}
FOR(i, 2, n) {
int d;
scanf("%d", &d);
G[i].pb(d);
G[d].pb(i);
}
dfs(1, 0);
rmq_init();
FOR(i, 1, n) update(1, w[i], i);
scanf("%d", &q);
while (q--) {
int t;
scanf("%d", &t);
if (t == 1) {
int i, j;
scanf("%d%d", &i, &j);
update(1, w[i], j);
update(1, w[j], i);
swap(w[i], w[j]);
} else {
printf("%d\n", query(1));
}
}
}
