题解 P5889 【跳树】

## 跳树 显而易见的线段树。 每个线段树的节点维护两个信息： 1. 最多向上走的层数。 2. 走到最上之后，若最上面的点为 $1$ 号点，则会走到几号点。 显然这个信息可以 $\mathcal O(1)$ 合并，分类讨论一下即可。 时间复杂度 $\mathcal O((m + q\log m)n)$，常数较小。 ```cpp const int N = 5e5 + 7; int n, m, q, x, p[37]; struct T { int l, r; pi x; } t[N<<2]; inline int get(int x) { if (!x) return 0; int y; while (x) y = x, x -= x & -x; return p[y%37]; } inline pi operator + (pi a, pi b) { int o = get(a.se); if (b.fi <= o) { o = get(b.se); return mp(a.fi, ((a.se >>= b.fi) ? a.se : 1) << o | (b.se ^ (1 << o))); } return mp(a.fi + b.fi - o, b.se); } void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (l == r) return rd(x), t[p].x = x == 3 ? mp(1, 1) : mp(0, x + 1), void(); build(ls, l, md), build(rs, md + 1, r); t[p].x = t[ls].x + t[rs].x; } pi ask(int p, int l, int r) { if (t[p].l >= l && t[p].r <= r) return t[p].x; pi o = mp(0, 1); if (l <= md) o = o + ask(ls, l, r); if (r > md) o = o + ask(rs, l, r); return o; } void chg(int p, int x, int y) { if (t[p].l == t[p].r) return t[p].x = y == 3 ? mp(1, 1) : mp(0, y + 1), void(); chg(x <= md ? ls : rs, x, y); t[p].x = t[ls].x + t[rs].x; } int main() { rd(n), rd(m), rd(q); for (int i = 0, j = 1; i <= n; i++, j <<= 1) p[j%37] = i; build(1, 1, m); while (q--) { int o; rd(o); if (o == 1) { int s, l, r; rd(s), rd(l), rd(r), print((mp(0, s) + ask(1, l, r)).se); } else { int x, y; rd(x), rd(y), chg(1, x, y); } } return 0; } ```