我好像国赛以后就再也没有写过 OI 相关的博客 qwq
Upd: 这篇博客是 NOIP （现在叫 CSP 了）之前写的，但是咕到 CSP 以后快一个月才发表 …… 我最近这么咕怎么办啊 ……
题目
分析
这道题可以说是非常神了。这题看上去无从下手，但是 通过膜拜题解 后能发现一些美妙的性质。树是不修改的，任意一对祖先 - 后代之间的路径一定都可以表示成一个 固定的 整数序列。并且，如果 (u,v,w) 是祖先 - 后代且深度递增，则 ((u,v)) 的序列与 ((v,w)) 的序列拼接起来就是 ((u,w)) 的序列。
如图，((1,2)) 之间的序列是 "1" （因为 (2) 是 (1) 的第一小的儿子）；((1,5)) 之间的序列是 "12" （因为从 (1) 到 (5) 要先走第一小，再走第二小），恰好是 ((1,2)) 和 ((2,5)) 的序列拼起来。
这样，我们就可以用一个序列（对应着从根到这个结点的走法）来表示一个结点了（设 (u) 的序列为 (s_u) ）。从结点 (u) 开始按照一个序列 (a) 走，走到的结点（如果存在）对应的序列就是 (s_u) 和 (a) 拼接起来（相当于从根开始先按照 (s_u) 走到 (u) ，然后按 (a) 走到 (s_u+a) ）。把序列 - 结点的映射关系用哈希表存下来，就可以 (O(1)) 判断从一个结点按照一个序列走若干步能否走到一个结点，以及查询如果能走到，走到的是哪个结点。
那么我们就有了一个做法：预处理出每个结点的序列的哈希值，并用线段树维护给定序列的哈希值。查询时二分走的长度（即取序列 ([l,mathrm{mid}]) 的部分），判断能否走到一个结点。直接二分是 (O(nlog^2n)) 过不去，必须在线段树上二分。
代码
比较弱，写了 6KB 。顺便说下陕西省美术馆门口写代码体验极佳。
注意拼接两个哈希值时乘的种子的次数。（这是个大坑）
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
namespace zyt
{
template<typename T>
inline bool read(T &x)
{
char c;
bool f = false;
x = 0;
do
c = getchar();
while (c != EOF && c != '-' && !isdigit(c));
if (c == EOF)
return false;
if (c == '-')
f = true, c = getchar();
do
x = x * 10 + c - '0', c = getchar();
while (isdigit(c));
if (f)
x = -x;
return true;
}
template<typename T>
inline void write(T x)
{
static char buf[20];
char *pos = buf;
if (x < 0)
putchar('-'), x = -x;
do
*pos++ = x % 10 + '0';
while (x /= 10);
while (pos > buf)
putchar(*--pos);
}
const int N = 5e5 + 10;
typedef long long ll;
int rot, n, m, q, arr[N];
vector<int> g[N];
namespace Hash
{
typedef pair<int, int> pii;
typedef pii hash_t;
const pii seed = pii(71, 853), P = pii(int(1e9 + 7), int(1e9 + 9));
hash_t pow[N];
pii operator + (const pii &a, const pii &b)
{
return pii((a.first + b.first) % P.first, (a.second + b.second) % P.second);
}
pii operator * (const pii &a, const pii &b)
{
return pii(int((ll)a.first * b.first % P.first), int((ll)a.second * b.second % P.second));
}
void init()
{
pow[0] = pii(1, 1);
for (int i = 1; i < N; i++)
pow[i] = pow[i - 1] * seed;
}
}
using namespace Hash;
hash_t h[N];
namespace Hash_Table
{
const int P = 1e6 - 17, seed = 24601;
struct edge
{
pii to;
int w, next;
}e[N];
int head[P], ecnt;
void add(const int a, const pii b, const int c)
{
e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++;
}
void init()
{
ecnt = 0;
memset(head, -1, sizeof(head));
}
void insert(const pii a, const int b)
{
int tmp = ((ll)a.first * seed + a.second) % P;
add(tmp, a, b);
}
int query(const pii a)
{
int tmp = ((ll)a.first * seed + a.second) % P;
for (int i = head[tmp]; ~i; i = e[i].next)
if (e[i].to == a)
return e[i].w;
return -1;
}
}
namespace Segment_Tree
{
struct node
{
hash_t h;
}tree[N << 2];
void update(const int rot, const int len)
{
tree[rot].h = tree[rot << 1].h * pow[len] + tree[rot << 1 | 1].h;
}
void build(const int rot, const int lt, const int rt)
{
if (lt == rt)
return void(tree[rot].h = hash_t(arr[lt], arr[lt]));
int mid = (lt + rt) >> 1;
build(rot << 1, lt, mid), build(rot << 1 | 1, mid + 1, rt);
update(rot, rt - mid);
}
void change(const int rot, const int lt, const int rt, const int pos, const int x)
{
if (lt == rt)
return void(tree[rot].h = hash_t(x, x));
int mid = (lt + rt) >> 1;
if (pos <= mid)
change(rot << 1, lt, mid, pos, x);
else
change(rot << 1 | 1, mid + 1, rt, pos, x);
update(rot, rt - mid);
}
hash_t query(const int rot, const int lt, const int rt, const int ls, const int rs)
{
if (ls <= lt && rt <= rs)
return tree[rot].h;
int mid = (lt + rt) >> 1;
if (rs <= mid)
return query(rot << 1, lt, mid, ls, rs);
else if (ls > mid)
return query(rot << 1 | 1, mid + 1, rt, ls, rs);
else
return query(rot << 1, lt, mid, ls, rs) * pow[min(rs, rt) - mid]
+ query(rot << 1 | 1, mid + 1, rt, ls, rs);
}
int query(const int rot, const int lt, const int rt, const int ls, const int rs, const hash_t h)
{
if (lt == rt)
return Hash_Table::query(h * seed + tree[rot].h);
int mid = (lt + rt) >> 1;
if (rs <= mid)
return query(rot << 1, lt, mid, ls, rs, h);
else if (ls > mid)
return query(rot << 1 | 1, mid + 1, rt, ls, rs, h);
else
{
int w;
hash_t hh = h * pow[mid - max(ls, lt) + 1] +
(ls <= lt ? tree[rot << 1].h : query(1, 1, m, ls, mid));
if ((w = Hash_Table::query(hh)) != -1)
{
int tmp = query(rot << 1 | 1, mid + 1, rt, ls, rs, hh);
if (tmp == -1)
return w;
else
return tmp;
}
else
return query(rot << 1, lt, mid, ls, rs, h);
}
}
}
void dfs(const int u)
{
sort(g[u].begin(), g[u].end());
int cnt = 0;
for (vector<int>::iterator it = g[u].begin(); it != g[u].end(); it++)
{
int v = *it;
++cnt;
h[v] = h[u] * seed + hash_t(cnt, cnt);
dfs(v);
}
}
int work()
{
using namespace Segment_Tree;
init();
Hash_Table::init();
read(n), read(m), read(q);
for (int i = 1; i <= n; i++)
{
int a;
read(a);
if (!a)
rot = i;
else
g[a].push_back(i);
}
h[rot] = hash_t(0, 0);
dfs(rot);
for (int i = 1; i <= n; i++)
Hash_Table::insert(h[i], i);
for (int i = 1; i <= m; i++)
read(arr[i]);
build(1, 1, m);
while (q--)
{
int opt;
read(opt);
if (opt == 1)
{
int x, l, r, ans;
read(x), read(l), read(r);
ans = query(1, 1, m, l, r, h[x]);
write(ans == -1 ? x : ans), putchar('
');
}
else
{
int a, b;
read(a), read(b);
change(1, 1, m, a, b);
}
}
return 0;
}
}
int main()
{
freopen("5537.in", "r", stdin);
return zyt::work();
}