建立一个虚拟点 \(p\)，满足 \(p\) 在 LCT 中编号最小。
如果一个点 \(i\) 可以弹到点 \(j\) 那么 \(i\) 到 \(j\) 连一条边。
如果一个点 \(i\) 可以被弹出那么向 \(p\) 连一条边。
然后，直接用 LCT 即可。
\(0\) 操作直接修改即可。
\(1\) 操作最后落在哪一个洞就是编号区间最大值，问弹了多少次就是区间求和。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct Link_Cut_Tree
{
struct Node
{
int l, r;
int f, sz, val, sum, rev, mx, id;
Node()
{
l = r = 0;
f = sz = val = sum = rev = mx = id = 0;
}
} z[N << 2];
void color(int p)
{
z[p].rev ^= 1;
}
void push_down(int p)
{
if (z[p].rev)
{
color(z[p].l);
color(z[p].r);
swap(z[p].l, z[p].r);
z[p].rev = 0;
}
}
void update(int p)
{
z[p].sz = z[z[p].l].sz + z[z[p].r].sz + 1;
z[p].sum = z[z[p].l].sum + z[z[p].r].sum + z[p].val;
z[p].mx = max({z[z[p].l].mx, z[z[p].r].mx, z[p].id});
}
void rot_l(int now)
{
int t = z[now].r;
z[now].r = z[t].l;
z[t].l = now;
if (!z[now].f)
;
else
{
if (z[z[now].f].l == now)
z[z[now].f].l = t;
else if (z[z[now].f].r == now)
z[z[now].f].r = t;
}
z[t].f = z[now].f;
z[now].f = t;
z[z[now].r].f = now;
update(now);
update(t);
}
void rot_r(int now)
{
int t = z[now].l;
z[now].l = z[t].r;
z[t].r = now;
if (!z[now].f)
;
else
{
if (z[z[now].f].l == now)
z[z[now].f].l = t;
else if (z[z[now].f].r == now)
z[z[now].f].r = t;
}
z[t].f = z[now].f;
z[now].f = t;
z[z[now].l].f = now;
update(now);
update(t);
}
void splay(int x)
{
push_down(x);
while (z[z[x].f].l == x || z[z[x].f].r == x)
{
int f = z[x].f, ff = z[f].f;
push_down(ff);
push_down(f);
push_down(x);
if (z[ff].l != f && z[ff].r != f)
{
if (z[f].l == x)
rot_r(f);
else
rot_l(f);
}
else
{
if (z[f].l == x && z[ff].l == f)
{
rot_r(ff);
rot_r(f);
}
if (z[f].r == x && z[ff].r == f)
{
rot_l(ff);
rot_l(f);
}
if (z[f].l == x && z[ff].r == f)
{
rot_r(f);
rot_l(ff);
}
if (z[f].r == x && z[ff].l == f)
{
rot_l(f);
rot_r(ff);
}
}
}
}
void access(int p)
// Link node p to the root node in a chain.
{
int q = 0;
while (p)
{
splay(p);
z[p].r = q;
update(p);
q = p;
p = z[p].f;
}
}
int find(int p)
// Find the shallowest point in the splay to which node p belongs.
{
access(p);
splay(p);
while (z[p].l)
p = z[p].l;
return p;
}
void make(int p)
// Convert node p to the root of the whole tree.
{
access(p);
splay(p);
color(p);
}
int query(int p1, int p2)
// Find the DISTANCE of the dissimilarities of all values in the chain formed by the nodes p1 and p2.
{
make(p1);
access(p2);
splay(p2);
return z[p2].sum;
}
int query_max(int p1, int p2)
// Find the MAXIMUM of the dissimilarities of all values in the chain formed by the nodes p1 and p2.
{
make(p1);
access(p2);
splay(p2);
return z[p2].mx;
}
bool ssame(int p1, int p2)
// Determine if p1 and p2 are the same point.
{
return p1 == p2;
}
bool same(int p1, int p2)
// Determine if p1 and p2 are connected in the tree.
{
p1 = find(p1);
p2 = find(p2);
return ssame(p1, p2);
}
void link(int p1, int p2)
// Join the nodes p1 and p2 in the tree. If these two nodes are already connected then this operation is ignored.
{
if (same(p1, p2))
return;
make(p1);
make(p2);
z[p1].f = p2;
}
void delink(int p1, int p2)
// Delete the edge joining the nodes p1 and p2 in the tree.
{
make(p1);
access(p2);
splay(p2);
if (z[p2].l == p1)
{
z[p2].l = 0;
update(p2);
z[p1].f = 0;
}
}
void change(int p, int val)
// Modify the point weight of point p to val.
{
splay(p);
z[p].id = p;
z[p].val = val;
update(p);
}
int previous(int p)
// Find the previous node of p.
{
make(p);
splay(p);
push_down(p);
p = z[p].l;
while (z[p].r)
{
p = z[p].r;
push_down(p);
}
return p;
}
} lct;
int a[N], link[N];
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
int nxt = i + a[i];
if (nxt <= n)
lct.link(i + 1, nxt + 1), link[i] = nxt;
else
lct.link(i + 1, 1), link[i] = 0;
}
for (int i = 1; i <= n + 1; i++)
lct.change(i, 1);
while (m--)
{
int o;
cin >> o;
if (o == 1)
{
int x;
cin >> x;
cout << lct.query_max(x + 1, 1) - 1 << ' ' << lct.query(x + 1, 1) - 1 << '\n';
}
else
{
int x, y;
cin >> x >> y;
int org = x + a[x];
if (org <= n)
lct.delink(x + 1, org + 1);
else
lct.delink(x + 1, 1);
if (x + y <= n)
lct.link(x + 1, x + y + 1), link[x] = x + y;
else
lct.link(x + 1, 1), link[x] = 0;
a[x] = y;
}
}
return 0;
}