目錄

• 「學習筆記」平衡樹基礎：Splay 和 Treap
  • 知識點
    • 平衡樹概述
    • Splay
      • 旋轉操作
      • Splay 操作
      • 插入 \(x\)
      • 查詢排名為 \(k\) 的數
      • 查詢 \(x\) 的排名
      • 查詢 \(x\) 的前驅
      • 查詢 \(x\) 的後繼
      • 刪除 \(x\)
      • 程式碼
    • 替罪羊樹
    • Treap
    • FHQ_Treap
    • 樹套樹
    • 平衡樹的區間操作
  • 例題
    • P3391 文藝平衡樹
      • 思路
    • P4036 [JSOI2008]火星人
      • 思路
    • P4309 [TJOI2013]最長上升子序列
      • 思路
    • 星系探索
      • 思路
      • 程式碼

const ll N = 2e5 + 10, INF = 1ll << 40;
namespace Splay {
	class TreePoint {
	public:
		ll val, cnt, sz;
		ll fa, son[2];
		inline void New (ll num) { val = num, cnt = sz = 1, fa = son[0] = son[1] = 0; return; }
		inline void Clear () { val = cnt = sz = fa = son[0] = son[1] = 0; return; }
	};

	class splay {
	public:
		TreePoint tr[N];
		ll tot = 0, rt = 0;

#define va(p) tr[p].val
#define cn(p) tr[p].cnt
#define sz(p) tr[p].sz
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].son[lr]

		inline void PushUp (ll p) { sz (p) = sz (so (p, 0)) + sz (so (p, 1)) + cn (p); return; } // Update the size.
		inline bool Get (ll p) { return p == so (fa (p), 1); } // Left son(0) or right son(1)?
		inline ll NewPoint (ll num) { tr[++tot].New (num); return tot; } // Build a new Point.

		inline void Rotate (ll p) {
			ll q = fa (p), r = fa (q), sd = Get (p);
			so (q, sd) = so (p, sd ^ 1);
			if (so (p, sd ^ 1)) fa (so (p, sd ^ 1)) = q;
			so (p, sd ^ 1) = q, fa (q) = p, fa (p) = r;
			if (r) so (r, q == so (r, 1)) = p;
			PushUp (q), PushUp (p);
			return;
		} // Zig or zag.
		inline void Splay (ll p) {
			for (ll q = fa (p); q = fa (p), q; Rotate (p))
				if (fa (q)) Rotate (Get (p) == Get (q) ? q : p);
			rt = p;
			return;
		} // Splay's core operations!

		inline void Out () {
			_for (i, 1, tot) {
				printf ("%lld : val=%lld cnt=%lld sz=%lld fa=%lld  %lld %lld\n", i, va (i), cn (i), sz (i), fa (i), so (i, 0), so (i, 1));
			}
			puts ("");
			return;
		} // For debug.

		inline void Insert (ll x) {
			if (!rt) rt = NewPoint (x), PushUp (rt);
			else {
				ll p = rt;
				while (1) {
					ll sd = (bool)(va (p) < x);
					if (va (p) == x) {
						++cn (p);
						PushUp (p), PushUp (fa (p));
						break;
					}
					else if (so (p, sd)) p = so (p, sd);
					else {
						so (p, sd) = NewPoint (x);
						fa (so (p, sd)) = p, p = so (p, sd);
						PushUp (p), PushUp (fa (p));
						break;
					}
				}
				Splay (p);
			}
			return;
		} // Insert a number x.
		inline ll GetRank (ll x) {
			ll p = rt, cnt = 1;
			while (p) {
				if (va (p) <= x) {
					cnt += sz (so (p, 0));
					if (va (p) == x) break;
					cnt += cn (p);
					p = so (p, 1);
				}
				else p = so (p, 0);
			}
			Splay (p);
			return cnt;
		} // Get x's rank.
		inline ll GetKth (ll x) {
			ll p = rt;
			while (p) {
				if (sz (so (p, 0)) < x) {
					x -= sz (so (p, 0));
					if (cn (p) >= x) break;
					x -= cn (p);
					p = so (p, 1);
				}
				else p = so (p, 0);
			}
			Splay (p);
			return va (p);
		} // Get k-th number.
		inline ll RealPre () {
			ll p = so (rt, 0);
			if (p) {
				while (so (p, 1)) p = so (p, 1);
				Splay (p);
			}
			return p;
		}
		inline void Delete (ll x) {
			GetRank (x);
			ll sd = (bool)(so (rt, 1));
			if (cn (rt) > 1) --cn (rt), PushUp (rt);
			else if (!so (rt, 0) && !so (rt, 1)) tr[rt].Clear (), rt = 0;
			else if (so (rt, 0) && so (rt, 1)) {
				ll p = rt, q = RealPre ();
				fa (so (p, 1)) = q;
				so (q, 1) = so (p, 1);
				tr[p].Clear ();
				PushUp (rt);
			}
			else {
				ll q = so (rt, sd);
				tr[rt].Clear ();
				fa (rt = q) = 0;
			}
			return;
		} // Delete a number x.
		inline ll Pre (ll x) {
			Insert (x);
			ll ans = va (RealPre ());
			Delete (x);
			return ans;
		} // Get x's pre.
		inline ll Next (ll x) {
			Insert (x);
			ll p = so (rt, 1), ans = 0;
			if (p) {
				while (so (p, 0)) p = so (p, 0);
				Splay (p);
			}
			ans = va (rt);
			Delete (x);
			return ans;
		} // Get x's next.

#undef va
#undef cn
#undef sz
#undef fa
#undef so
	};
}

namespace ScapeGoatTree {
	const ldb alpha = 0.75;
	const ll N = 1e5 + 10;
	class TreePoint {
	public:
		ll val, cnt, sz, cp, del;
		ll fa, son[2];
	};
	class SGT {
	private:
		ll tot = 0, rt = 0, dp[N], cd = 0;
		TreePoint tr[N];
		vec tmp, c;

#define va(p) tr[p].val
#define cn(p) tr[p].cnt
#define sz(p) tr[p].sz
#define de(p) tr[p].del
#define cp(p) tr[p].cp
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].son[lr]

		inline ll NewP (ll num) {
			ll p = cd ? dp[cd--] : ++tot;
			va (p) = num;
			cn (p) = sz (p) = 1;
			cp (p) = fa (p) = so (p, 0) = so (p, 1) = de (p) = 0;
			return p;
		}
		inline void DelP (ll p) {
			va (p) = cn (p) = sz (p) = cp (p) = fa (p) = so (p, 0) = so (p, 1) = de (p) = 0;
			dp[++cd] = p;
			return;
		}
		inline void PushUp (ll p) {
			sz (p) = (de (p) ? 0 : cn (p)) + sz (so (p, 0)) + sz (so (p, 1));
			cp (p) = 1 + cp (so (p, 0)) + cp (so (p, 1));
			return;
		}

	public:
		inline void Clap (ll p) {
			if (so (p, 0)) Clap (so (p, 0));
			if (!de (p)) tmp.push_back (va (p)), c.push_back (cn (p));
			if (so (p, 1)) Clap (so (p, 1));
			DelP (p);
			return;
		}
		inline ll PullUp (ll l, ll r, ll fat) {
			if (l > r) return 0;
			bdmd;
			ll p = NewP (tmp[mid]);
			cn (p) = c[mid], fa (p) = fat;
			if (l < mid) so (p, 0) = PullUp (l, mid - 1, p);
			if (mid < r) so (p, 1) = PullUp (mid + 1, r, p);
			PushUp (p);
			return p;
		}
		inline void ReBuild (ll p) {
			ll q = fa (p);
			tmp.clear (), c.clear ();
			Clap (p);
			if (!q) rt = PullUp (0, tmp.size () - 1, q);
			else so (q, p == so (q, 1)) = PullUp (0, tmp.size () - 1, q);
			return;
		}

		inline bool Bad (ll p) {
			return cp (so (p, 0)) > cp (p) * alpha || cp (so (p, 1)) > cp (p) * alpha;
		}
		inline void Check (ll p) {
			ll q = 0;
			while (p) {
				if (Bad (p)) q = p;
				rt = p;
				PushUp (p);
				p = fa (p);
			}
			if (q) ReBuild (q);
			return;
		}

		inline void Insert (ll num) {
			ll p = rt;
			if (!rt) {
				rt = NewP (num);
				return;
			}
			while (1) {
				if (va (p) == num) {
					++cn (p);
					if (de (p)) de (p) = 0;
					Check (p);
					return;
				}
				ll sd = num > va (p);
				if (so (p, sd)) p = so (p, sd);
				else {
					so (p, sd) = NewP (num);
					fa (so (p, sd)) = p;
					Check (p);
					return;
				}
			}
			return;
		}
		inline void Delete (ll num) {
			ll p = rt;
			while (p) {
				if (va (p) == num) {
					--cn (p);
					if (cn (p) < 1) {
						cn (p) = 0;
						de (p) = 1;
					}
					Check (p);
					return;
				}
				ll sd = num > va (p);
				p = so (p, sd);
			}
			return;
		}
		inline ll GetRank (ll num) {
			ll p = rt, rk = 1;
			while (p) {
				if (va (p) > num) {
					p = so (p, 0);
					continue;
				}
				rk += sz (so (p, 0));
				if (num == va (p)) break;
				rk += cn (p);
				p = so (p, 1);
			}
			return rk;
		}
		inline ll GetKth (ll k) {
			ll p = rt;
			while (p) {
				if (sz (so (p, 0)) >= k) {
					p = so (p, 0);
					continue;
				}
				k -= sz (so (p, 0));
				if (k <= cn (p)) break;
				k -= cn (p);
				p = so (p, 1);
			}
			return va (p);
		}
		inline ll Pre (ll num) { return GetKth (GetRank (num) - 1); }
		inline ll Nxt (ll num) { return GetKth (GetRank (num + 1)); }

#undef va
#undef cn
#undef sz
#undef de
#undef cp
#undef fa
#undef so
	};
}

namespace TREAP {
	class TreePoint {
	public:
		ll val, rk, sz, cnt;
		ll son[2];
		inline void NewP (ll x) { val = x, rk = rand (), cnt = sz = 1, son[0] = son[1] = 0;return; }
	};
	class Treap {
	public:
		TreePoint tr[N];
		ll tot = 0, rt = 0;

#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define cn(p) tr[p].cnt
#define so(p, lr) tr[p].son[lr]

		inline void PushUp (ll p) { sz (p) = cn (p) + sz (so (p, 0)) + sz (so (p, 1)); return; }
		inline ll NewP (ll num) { tr[++tot].NewP (num); return tot; }
		inline void DelP (ll p) { va (p) = rk (p) = sz (p) = cn (p) = so (p, 0) = so (p, 1) = 0;return; }

		inline void Rotate (ll& p, ll sd) {
			ll q = so (p, sd ^ 1);
			so (p, sd ^ 1) = so (q, sd);
			so (q, sd) = p, p = q;
			PushUp (so (q, sd)), PushUp (q);
			return;
		}

		void Insert (ll& p, ll x) {
			if (!p) {
				p = NewP (x);
				return;
			}
			if (va (p) == x) ++cn (p);
			else {
				bool sd = (va (p) < x);
				Insert (so (p, sd), x);
				if (rk (so (p, sd)) > rk (p)) Rotate (p, sd ^ 1);
			}
			PushUp (p);
			return;
		}
		void Delete (ll& p, ll x) {
			if (!p) return;
			if (va (p) == x) {
				if (cn (p) == 1) {
					if (!so (p, 0) && !so (p, 1)) DelP (p), p = 0;
					else if (!so (p, 0) || !so (p, 1)) p = so (p, 0) + so (p, 1);
					else {
						ll sd = (rk (so (p, 1)) < rk (so (p, 0)));
						Rotate (p, sd), Delete (so (p, sd), x);
					}
				}
				else --cn (p);
			}
			else Delete (so (p, (x > va (p))), x);
			PushUp (p);
			return;
		}
		ll GetRank (ll p, ll x) {
			if (!p) return 1;
			if (va (p) == x) return 1 + sz (so (p, 0));
			if (va (p) < x) return GetRank (so (p, 1), x) + sz (so (p, 0)) + cn (p);
			return GetRank (so (p, 0), x);
		}
		ll GetKth (ll p, ll x) {
			if (!p) return 0;
			if (x <= sz (so (p, 0))) return GetKth (so (p, 0), x);
			x -= sz (so (p, 0));
			if (x <= cn (p)) return va (p);
			x -= cn (p);
			return GetKth (so (p, 1), x);
		}
		ll Pre (ll x) { return GetKth (rt, GetRank (rt, x) - 1); }
		ll Next (ll x) { return GetKth (rt, GetRank (rt, x + 1)); }

#undef va
#undef rk
#undef sz
#undef cn
#undef so
	};
}

namespace FHQ_TREAP {
	class TreeNode {
	public:
		ll val, rk, sz, son[2];
		inline void Add (ll num) { val = num, rk = rand (), sz = 1, son[0] = son[1] = 0; return; }
	};
	class FHQTreap {
	private:
		TreeNode tr[N];
		ll tot = 0, rt = 0, a, b, c;

#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define so(p, lr) tr[p].son[lr]

		inline ll NewP (ll num) { tr[++tot].Add (num); return tot; }
		inline void PushUp (ll p) { sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1)); return; }

		void Split (ll p, ll x, ll& l, ll& r) {
			if (!p) l = r = 0;
			else {
				if (va (p) <= x) l = p, Split (so (p, 1), x, so (p, 1), r);
				else r = p, Split (so (p, 0), x, l, so (p, 0));
				PushUp (p);
			}
			return;
		}
		inline ll Merge (ll l, ll r) {
			if (!l || !r) return l + r;
			if (rk (l) < rk (r)) {
				so (l, 1) = Merge (so (l, 1), r);
				PushUp (l);
				return l;
			}
			else {
				so (r, 0) = Merge (l, so (r, 0));
				PushUp (r);
				return r;
			}
		}

	public:
		inline void Insert (ll x) {
			Split (rt, x, a, b);
			rt = Merge (Merge (a, NewP (x)), b);
			return;
		}
		inline void Delete (ll x) {
			Split (rt, x, a, b);
			Split (a, x - 1, a, c);
			rt = Merge (Merge (a, Merge (so (c, 0), so (c, 1))), b);
			return;
		}
		inline ll GetRank (ll x) {
			Split (rt, x - 1, a, b);
			ll ans = sz (a) + 1;
			rt = Merge (a, b);
			return ans;
		}
		inline ll GetKth (ll x) {
			ll p = rt;
			while (p) {
				if (x <= sz (so (p, 0))) p = so (p, 0);
				else {
					x -= sz (so (p, 0)) + 1;
					if (!x) break;
					p = so (p, 1);
				}
			}
			return va (p);
		}
		inline ll Pre (ll x) {
			Split (rt, x - 1, a, b);
			ll p = a;
			while (so (p, 1)) p = so (p, 1);
			rt = Merge (a, b);
			return va (p);
		}
		inline ll Next (ll x) {
			Split (rt, x, a, b);
			ll p = b;
			while (so (p, 0)) p = so (p, 0);
			rt = Merge (a, b);
			return va (p);
		}

#undef va
#undef rk
#undef sz
#undef so
	};
}

const ll N = 1e5 + 10, inf = 2147483647;

namespace FHQ_TREAP {
	class TreeNode {
	public:
		ll val, rk, sz, son[2];
		inline void Add (ll num) noexcept { val = num, rk = rand (), sz = 1, son[0] = son[1] = 0; return; }
	} tr[N << 4];
	ll tot = 0, len = 0, free[N << 4];

#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define so(p, lr) tr[p].son[lr]

	class FHQTreap {
	private:
		ll rt = 0, a, b, c;

		inline void PushUp (ll p) noexcept { sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1)); }
		inline ll NewP (ll num) noexcept {
			ll p = len ? free[len--] : ++tot;
			tr[p].Add (num);
			return p;
		}
		inline void DelP (ll p) noexcept {
			va (p) = rk (p) = sz (p) = so (p, 0) = so (p, 1) = 0;
			free[++len] = p;
			return;
		}

		inline void Split (ll p, ll x, ll& l, ll& r) noexcept {
			if (!p) l = r = 0;
			else {
				if (va (p) <= x) l = p, Split (so (p, 1), x, so (p, 1), r);
				else r = p, Split (so (p, 0), x, l, so (p, 0));
				PushUp (p);
			}
			return;
		}
		inline ll Merge (ll l, ll r) noexcept {
			if (!l || !r) return l + r;
			if (rk (l) > rk (r)) {
				so (l, 1) = Merge (so (l, 1), r);
				PushUp (l);
				return l;
			}
			else {
				so (r, 0) = Merge (l, so (r, 0));
				PushUp (r);
				return r;
			}
		}

	public:
		inline void Insert (ll x) noexcept {
			Split (rt, x, a, b);
			rt = Merge (Merge (a, NewP (x)), b);
			return;
		}
		inline void Delete (ll x) noexcept {
			Split (rt, x, a, b);
			Split (a, x - 1, a, c);
			rt = Merge (Merge (a, Merge (so (c, 0), so (c, 1))), b);
			DelP (c);
			return;
		}
		inline ll GetRank (ll x) noexcept {
			Split (rt, x - 1, a, b);
			ll ans = sz (a);
			rt = Merge (a, b);
			return ans;
		}
		inline ll Pre (ll x) noexcept {
			Split (rt, x - 1, a, b);
			ll p = a;
			while (so (p, 1)) p = so (p, 1);
			rt = Merge (a, b);
			return va (p);
		}
		inline ll Next (ll x) noexcept {
			Split (rt, x, a, b);
			ll p = b;
			while (so (p, 0)) p = so (p, 0);
			rt = Merge (a, b);
			return va (p);
		}
	};

#undef va
#undef rk
#undef sz
#undef so
}

namespace SEGMENT_TREE {
	class SegmentTree {
	private:
		FHQ_TREAP::FHQTreap tr[N << 2];

#define ls(p) p << 1, l, mid
#define rs(p) p << 1 | 1, mid + 1, r

	public:
		inline void Build (ll p, ll l, ll r, ll* a) noexcept {
			if (l != r) {
				ll mid = md;
				Build (ls (p), a);
				Build (rs (p), a);
			}
			tr[p].Insert (inf), tr[p].Insert (-inf);
			_for (i, l, r) tr[p].Insert (a[i]);
			return;
		}
		inline void Update (ll p, ll l, ll r, ll x, ll y, ll z) noexcept {
			if (r < x || x < l) return;
			if (l != r) {
				ll mid = md;
				Update (ls (p), x, y, z);
				Update (rs (p), x, y, z);
			}
			tr[p].Delete (z), tr[p].Insert (y);
		}
		inline ll QueryRank (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
			if (ri < l || r < le) return 0;
			ll mid = md;
			if (le <= l && r <= ri) return tr[p].GetRank (x) - 1;
			else return QueryRank (ls (p), le, ri, x) + QueryRank (rs (p), le, ri, x);
		}
		inline ll QueryKth (ll le, ll ri, ll x, ll n, ll mx) noexcept {
			ll l = 0, r = mx, ans = 0;
			while (l <= r) {
				ll mid = md;
				if (QueryRank (1, 1, n, le, ri, mid) + 1 <= x) ans = mid, l = mid + 1;
				else r = mid - 1;
			}
			return ans;
		}
		inline ll QueryPre (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
			if (ri < l || r < le) return -inf;
			ll mid = md;
			if (le <= l && r <= ri) return tr[p].Pre (x);
			else return std::max (QueryPre (ls (p), le, ri, x), QueryPre (rs (p), le, ri, x));
		}
		inline ll QueryNext (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
			if (ri < l || r < le) return inf;
			ll mid = md;
			if (le <= l && r <= ri) return tr[p].Next (x);
			else return std::min (QueryNext (ls (p), le, ri, x), QueryNext (rs (p), le, ri, x));
		}
	};
}

使用 Splay：通過對 \(l-1\) 和 \(r+1\) 提根使得區間 \([l, r]\) 在一顆子樹上，然後對這棵子樹進行操作。

使用 FHQ-Treap：把區間 \([l, r]\) 裂出來，然後對這棵子樹進行操作，再合併回去。

const ll N = 1e6+ 10;

namespace FHQ_TREAP {
	class TreeNode {
	public:
		ll val, pn, rk, sz, so[2], ta, sum, sp, fa;
		inline void Add (ll num, ll tmp) { sum = val = num * tmp, sp = pn = tmp, rk = rand (), sz = 1, so[0] = so[1] = 0; return; }
	};
	class FHQTreap {
	private:
		TreeNode tr[N];
		ll tot = 0, rt = 0, a, b, c;

#define va(p) tr[p].val
#define ta(p) tr[p].ta
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define pn(p) tr[p].pn
#define su(p) tr[p].sum
#define sp(p) tr[p].sp
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].so[lr]

		inline ll NewP (ll num, ll pn) { tr[++tot].Add (num, pn); return tot; }
		inline void PushUp (ll p) {
			sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1));
			su (p) = va (p) + su (so (p, 0)) + su (so (p, 1));
			sp (p) = pn (p) + sp (so (p, 0)) + sp (so (p, 1));
			fa (so (p, 0)) = fa (so (p, 1)) = p;
			return;
		}
		inline void Tag (ll p, ll num) {
			ta (p) += num;
			va (p) += num * pn (p);
			su (p) += num * sp (p);
			return;
		}
		inline void PushDown (ll p) {
			if (!ta (p)) return;
			if (so (p, 0)) Tag (so (p, 0), ta (p));
			if (so (p, 1)) Tag (so (p, 1), ta (p));
			fa (so (p, 0)) = fa (so (p, 1)) = p;
			ta (p) = 0;
			return;
		}

		inline void Split (ll p, ll x, ll& l, ll& r) {
			if (!p) l = r = 0;
			else {
				PushDown (p);
				if (sz (so (p, 0)) < x) l = p, Split (so (p, 1), x - sz (so (p, 0)) - 1, so (p, 1), r);
				else r = p, Split (so (p, 0), x, l, so (p, 0));
				PushUp (p);
			}
			return;
		}
		inline ll Merge (ll l, ll r) {
			PushDown (l), PushDown (r);
			if (!l || !r) return l + r;
			if (rk (l) > rk (r)) {
				so (l, 1) = Merge (so (l, 1), r);
				PushUp (l);
				return l;
			}
			else {
				so (r, 0) = Merge (l, so (r, 0));
				PushUp (r);
				return r;
			}
		}
		inline ll GetRank (ll x) {
			ll cnt = sz (so (x, 0)) + 1;
			for (ll p = x; fa (p); p = fa (p))
				if (so (fa (p), 1) == p) cnt += sz (so (fa (p), 0)) + 1;
			return cnt;
		}

	public:
		inline void Insert (ll x, ll p) {
			rt = Merge (rt, NewP (x, p));
			return;
		}
		inline void Modify (ll l, ll r, ll x) {
			l = GetRank (l), r = GetRank (r);
			Split (rt, r, a, b);
			Split (a, l - 1, a, c);
			Tag (c, x);
			rt = Merge (Merge (a, c), b);
			return;
		}
		inline void Move (ll l, ll r, ll x) {
			l = GetRank (l), r = GetRank (r), x = GetRank (x);
			if (x > r) x -= r - l + 1;
			Split (rt, r, a, b);
			Split (a, l - 1, a, c);
			a = Merge (a, b);
			Split (a, x, a, b);
			rt = Merge (Merge (a, c), b);
			return;
		}
		inline ll Query (ll x) {
			x = GetRank (x);
			Split (rt, x, a, b);
			ll ans = su (a);
			rt = Merge (a, b);
			return ans;
		}

#undef va 
#undef ta
#undef rk
#undef sz
#undef pn
#undef su
#undef sp
#undef fa
#undef so
	};
}

namespace SOLVE {
	FHQ_TREAP::FHQTreap tr;
	ll n, m, fa[N], w[N], cnt;
	ll dfn[N], sec[N][2];
	std::vector<ll> tu[N];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline char rch () {
		char c = getchar ();
		while (c < 'A' || 'Z' < c) c = getchar ();
		return c;
	}
	inline void Dfs (ll x) {
		dfn[sec[x][0] = ++cnt] = x;
		tr.Insert (w[x], 1);
		far (i, tu[x]) Dfs (i);
		sec[x][1] = ++cnt;
		tr.Insert (w[x], -1);
		return;
	}
	inline void In () {
		n = rnt ();
		_for (i, 2, n) {
			fa[i] = rnt ();
			tu[fa[i]].push_back (i);
		}
		_for (i, 1, n) w[i] = rnt ();
		m = rnt ();
		Dfs (1);
		return;
	}
	inline void Out () {
		while (m--) {
			char opt = rch ();
			if (opt == 'Q') {
				ll d = rnt ();
				printf ("%lld\n", tr.Query (sec[d][0]));
			}
			else if (opt == 'C') {
				ll x = rnt (), y = rnt ();
				tr.Move (sec[x][0], sec[x][1], sec[y][0]);
			}
			else {
				ll x = rnt (), y = rnt ();
				tr.Modify (sec[x][0], sec[x][1], y);
			}
		}
		return;
	}
}