LG P5537 【XR-3】系统设计

本文核心卖点：用树状数组神秘地维护哈希（不如另一篇题解巧妙，内含简单数论知识）。

观察到，走这个操作的可行性关于走的步数有单调性，考虑二分走的步数。

那么如何判断从点 \(x\) 走 \(mid\) 步的可行性呢？树的结构是固定的，每一种走法（路径上每个点儿子的排名构成的序列）与走到某个重点一一对应，和哈希很类似。

那么二分出 \(mid\)，求出走 \(mid\) 步的哈希值（即为 \(a[l...l+mid-1]\) 的哈希值）后，如何判断这个哈希值是否存在呢？

由于每个终点可能对应很多个起点，进行 \((起点,终点)\) 的哈希值的记录是 \(\mathcal O(n^2)\) 的。但是这种树上问题，起点终点又有祖先关系，容易想到前缀相关。

具体怎么做呢？根走到起点构成的序列对应唯一一个起点，但是起点到终点构成序列不一定对应唯一一条路径。那么就把这两个拼在一起，在全局中存在，就是在起点的子树内存在。用unordered_map再维护下。

这时候万事俱备，只欠支持单点修改，区间查询的哈希值维护了。

想偷懒，不想用线段树，那么树状数组怎么做呢。

我是铸币，想不到那篇题解中的做法。于是转而用了一种稍微复杂的。

有一个初步的想法，一个正常的树状数组+每一位的值为 \(a[i]*base^{n-i}\)。

但是这样区间查询出的值不是 \(a_l*base^{r-l}+...+a_r*base^{0}\) 的，而是全体乘上了一个 \(base^{m-r}\) ，我们想要把它除掉。

这时候就要求逆元了，可是我们又想偷懒，用自然溢出，模数为 \(2^{64}\) ，不是质数啊。

无所谓，模数是死的，\(base\) 是活的，我们只要求 \(base\) 的幂的逆元就行了，选一个与 \(2^{64}\) 互质的 \(base\) 就行了（按照讨论区的建议，用的一个神秘 \(base\)）。

至此，这题就完成了。

#include <bits/stdc++.h>

using namespace std;

#define typ int
inline char gc(){static char buf[100000] , *p1 = buf , *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;}inline typ read(){typ x = 0; bool f = 0;char ch = gc();while(!isdigit(ch)){f |= (ch == '-');ch = gc();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = gc();}return (f ? -x : x);}

typedef unsigned long long ull;

const int N = 5e5 + 5;
const ull BB = 3846711;
const ull invBB = 918018653273039751;

int n , m , q , rt , a[N];
ull H[N] , B[N] , invB[N];

vector<int> E[N];

unordered_map<ull , int> mp;

namespace BIT {
	ull t[N];
#define lowbit(x) ((x) & (-(x)))
	void ch(int x , ull v){
		while(x <= m){
			t[x] += v;
			x += lowbit(x);
		}
	}
	ull qwq(int x){
		ull res = 0;
		while(x > 0){
			res += t[x];
			x -= lowbit(x);
		}
		return res;
	}
}

signed main(){
	n = read() , m = read() , q = read();
	for(int i = 1; i <= n; ++ i){
		int fa = read();
		if(fa == 0) rt = i;
		else {
			E[i].push_back(fa);
			E[fa].push_back(i);
		}
	}
	
	for(int i = 1; i <= m; ++ i) a[i] = read();
	
	for(int i = 1; i <= n; ++ i) 
		sort(E[i].begin() , E[i].end());
	
	invB[0] = B[0] = 1;
	for(int i = 1; i <= m; ++ i) {
		B[i] = B[i - 1] * BB;
		invB[i] = invB[i - 1] * invBB;
		assert(invB[i] * B[i] == 1);
	}
	
	function<void(int , int)> dfs = [&] (int u , int fa) -> void {
		mp[H[u]] = u;
		int rk = 0;
		for(auto v : E[u]){
			if(v == fa) continue;
			
			++ rk;
			H[v] = H[u] * BB + rk;
			
			dfs(v , u);
		}
	};
	
	dfs(rt , 0);
	
	for(int i = 1; i <= m; ++ i){
		BIT::ch(i , a[i] * B[m - i]);
	}
	
	for(int tt = 1; tt <= q; ++ tt){
		int op = read();
		if(op == 1){
			int u = read() , L = read() , R = read();
			int l = 0 , r = R - L + 1 , res = -1;
			while(l <= r){
				int mid = (l + r) >> 1;
				ull v = BIT::qwq(L + mid - 1) - BIT::qwq(L - 1);
				v *= invB[m - (L + mid - 1)];
				v += H[u] * B[mid];
				if(mp.find(v) != mp.end()){
					res = mp[v];
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
//			assert(res != -1);
			printf("%d\n" , res);
		}
		if(op == 2){
			int x = read() , k = read();
			BIT::ch(x , -a[x] * B[m - x]);
			a[x] = k;
			BIT::ch(x , a[x] * B[m - x]);
		}
	}
	
	return 0;
}