题解 P3203 【[HNOI2010]弹飞绵羊】
一道对初学LCT者来说比较有思维难度的题。
题解里的开一个点表示弹飞的做法蒟蒻只能表示想不到qaq，在没看题解的情况下想出了这样的做法：
首先我们可以让每个点弹到的点作为它的父亲，如果弹飞那么就是根。容易发现我们需要维护一个森林。询问操作就是求这个点的深度，而修改操作就是把一个点断开和父亲的连接，接到一个新的点上。说白了就是可以修改父亲的动态深度询问。
那么，看到动态维护森林，便可以想到LCT。问题是要求深度，那么我们有了一个很令人讨厌的限制条件：不能换根。这样，我们就不得不用剩下来的几种操作和人类的智慧来完成这道题。
外接表示弹飞的点的做法：渣渣，我就可以换根！
0. 建树
要是所有点都link到它的father，且不说带一个log，不能换根link操作也用不了啊。这里有一个好方法：所有边默认初始虚边，直接连就完事。
建树部分代码：
for (int i=1; i<=n; ++i)
{
int tmp;
scanf("%d", &tmp);
fa[i]=(i+tmp>n)?0:(i+tmp);
// 要是弹飞father就是0（即是树根）
}1. 查询操作
这个操作相对简单。LCT的实链剖分有一个好处：可以直接用access操作打通到根节点的路径。比如说，我们的原树长这样：
2
/ \
1 5
/ \
3 4
\
6（假设一开始全是虚边）
然后假如我们要查询节点4的路径，我们先access一下4号点，树变成这样：
2
// \
1 5
/ \\
3 4
\
6（双杠表示实边，单杠表示虚边）
此时根所在的splay的元素一定是根到查询的点这条链，因此要查询点的rank即是它的深度。把要查询的点splay到根，那么它的左子树的大小就是它的祖先个数（而且它一定没有右子树）。把左子树的size加一，即可得到要查询的点的rank，也就是它的深度。
为了便于理解，这时的辅助树长这样：
4
// \
1 6
// \
2 3
|
5可以看到查询的点（4）所有的祖先都在左子树。如果仍有疑虑，可以加一句assert(son[i][1]==0);来验证。
查询操作代码：
int query(int i)
{
access(i);
splay(i);
assert(son[i][1]==0);
return son[i][0]?siz[son[i][0]]+1:1;
// 要额外判目前的点已经是根节点的情况，因为0号节点可能有垃圾数值
}2. 修改操作
这是比较困难的一个操作。
看到断/连，想到的第一个就是cut和link。然而先不说常数，不能换根这一点，就让cut和link成为了不可能。那么，怎么做呢？
要断开查询节点（称为i）和它在原树中的父亲，我们首先要找到它在原树中的父亲。容易想到，首先要让它和父亲在一棵splay里面。所以，先要access(i)。然后，我们可以知道，由于i和i的父亲在原树中深度连续，i的父亲在splay中一定是i的前驱。查找前驱是比较基础的splay操作（当然不是普通的二叉搜索树那种从根节点查找前驱的操作），可以先splay(i)，然后从i的左儿子一直往右儿子找，直到不存在右儿子为止。找父亲部分代码：
access(i);
splay(i);
// 找父亲
int ifa=son[i][0];
while (son[ifa][1]) ifa=son[ifa][1];找到父亲之后，为了断边，我们要让i号节点和ifa节点之间存在直接相连的边。因此，先splay(ifa)，然后，由于ifa和i深度连续，ifa的右儿子一定是i，而且i不存在左儿子（其实也不存在右儿子，因为我们access过i）。直接断边，把i连到新父亲即可。修改操作代码：
void modify(int i, int j) // 修改，j是新的父亲
{
access(i);
splay(i);
// find father
int ifa=son[i][0];
while (son[ifa][1]) ifa=son[ifa][1];
splay(ifa);
assert(ifa==fa[i]);
son[ifa][1]=0;
push_up(ifa);
fa[i]=j;
return;
}但是，且慢！如果你用这份代码提交，你将会得到两个TLE（而且是小数据的）。这倒不是常数的原因，而是因为，如果i已经是根，那么ifa就是0，然后我们就会进入splay(0)死循环！解决的方法是加一个ifa是否为0的判断。正确的修改操作代码：
void modify(int i, int j) // 修改，j是新的父亲
{
access(i);
splay(i);
// find father
int ifa=son[i][0];
if (ifa)
{
while (son[ifa][1]) ifa=son[ifa][1];
splay(ifa);
assert(ifa==fa[i]);
son[ifa][1]=0;
push_up(ifa);
}
fa[i]=j;
return;
}好啦，操作都讲完啦qwq，接下来就是完整的AC代码了。顺带提一句，这份代码只有130+行（含空行），比普通LCT码量小了很多，而且常数出奇地小，不加任何刻意卡常，吸一口氧，总时间580+ms，在洛谷居然排在前5页（前几页有大量的巨佬反复提交），可谓是相当令人惊喜了qwq。
完整AC code:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <assert.h>
// by luogu @樱初音斗橡皮
const int N=200000;
const int M=100000;
int n, m;
int fa[N+10], son[N+10][2], siz[N+10];
inline bool nroot(int i) // 不是根
{
return (son[fa[i]][0]==i)||(son[fa[i]][1]==i);
}
inline bool chk(int i) // 是右儿子
{
return son[fa[i]][1]==i;
}
inline void push_up(int i) // 上传信息
{
siz[i]=1;
if (son[i][0])
siz[i]+=siz[son[i][0]];
if (son[i][1])
siz[i]+=siz[son[i][1]];
return;
}
inline void spin(int i) // 旋转
{
int ifa=fa[i], igfa=fa[ifa], dir=chk(i),
ison=son[i][dir^1], dirfa=chk(fa[i]), nrt=nroot(ifa);
fa[ison]=ifa;
son[ifa][dir]=ison;
fa[ifa]=i;
son[i][dir^1]=ifa;
fa[i]=igfa;
if (nrt)
son[igfa][dirfa]=i;
push_up(ifa);
push_up(i);
return;
}
void splay(int i) // splay
{
int ifa=fa[i];
while (nroot(i))
{
if (nroot(ifa))
{
if (chk(i)==chk(ifa))
spin(ifa);
else
spin(i);
}
spin(i);
ifa=fa[i];
}
return;
}
void access(int i) // access
{
int j=0;
while (i)
splay(i), son[i][1]=j, push_up(i), j=i, i=fa[i];
return;
}
int query(int i) // 查询
{
access(i);
splay(i);
assert(son[i][1]==0);
return son[i][0]?siz[son[i][0]]+1:1;
}
void modify(int i, int j) // 修改，j是新的父亲
{
access(i);
splay(i);
// find father
int ifa=son[i][0];
if (ifa)
{
while (son[ifa][1]) ifa=son[ifa][1];
splay(ifa);
assert(ifa==fa[i]);
son[ifa][1]=0;
push_up(ifa);
}
fa[i]=j;
return;
}
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; ++i)
fa[i]=0, son[i][0]=son[i][1]=0, siz[i]=1;
for (int i=1; i<=n; ++i)
{
int tmp;
scanf("%d", &tmp);
fa[i]=(i+tmp>n)?0:(i+tmp);
}
scanf("%d", &m);
for (int i=1; i<=m; ++i)
{
int cmd, j, k;
scanf("%d%d", &cmd, &j);
++j;
// 题目中的编号为0~n-1，实际的编号要+1便于操作
switch (cmd)
{
case 1:
printf("%d\n", query(j));
break;
case 2:
scanf("%d", &k);
modify(j, (j+k>n)?0:(j+k));
break;
default:
printf("stupid yyc\n"); // 滑稽
// 防止数据出错
break;
}
}
return 0;
}