聽(tīng)說(shuō)有版權(quán)問(wèn)題不能貼題目？。那就只能先忍一忍了。
題目抽象為：我們有一個(gè)由有根樹(shù)構(gòu)成的森林，對(duì)這個(gè)森林進(jìn)行兩種操作：
把某棵子樹(shù)拔下來(lái)接到某一棵樹(shù)（可能還是那個(gè)子樹(shù)原來(lái)所在的樹(shù)）的某個(gè)節(jié)點(diǎn)下面，詢問(wèn)某個(gè)節(jié)點(diǎn)在樹(shù)中的深度。
因?yàn)榘岩豢眠厵?quán)為1的樹(shù)的括號(hào)序列拿出來(lái)，樹(shù)上某兩點(diǎn)的距離就是在括號(hào)序列中兩點(diǎn)間沒(méi)匹配括號(hào)的個(gè)數(shù)（有左括號(hào)右括號(hào)選擇的區(qū)別，具體分析處理）。當(dāng)然，既然是對(duì)一群樹(shù)操作，那就直接用動(dòng)態(tài)樹(shù)就行了。
于是就去學(xué)了動(dòng)態(tài)樹(shù)。發(fā)現(xiàn)其實(shí)不算很難（1.指時(shí)間復(fù)雜度均攤logn的算法，還有基于輕重邊剖分的嚴(yán)格logn的算法 2.如果你對(duì)splay熟的話），寫(xiě)起來(lái)也就基本上就是一棵splay，也算比較好寫(xiě)的。。（以后就告別路徑剖分了。。太麻煩了。。復(fù)雜度也沒(méi)動(dòng)態(tài)樹(shù)好。。）
以下所說(shuō)的動(dòng)態(tài)樹(shù)都是基于splay的時(shí)間復(fù)雜度均攤logn的動(dòng)態(tài)樹(shù)。
動(dòng)態(tài)樹(shù)的主要思想就是：類似輕重邊剖分一樣，把整棵樹(shù)劃分成若干實(shí)邊(solid edge)和虛邊(dashed edge)，但這個(gè)都是根據(jù)你的需要來(lái)設(shè)定的，不像輕重邊一樣每個(gè)點(diǎn)往下都必須有一條重邊（單獨(dú)的葉子節(jié)點(diǎn)算長(zhǎng)度為0的重邊），而是每次把你所需要操作的點(diǎn)到根的邊都改為實(shí)邊(expose操作)，且每個(gè)點(diǎn)往下的實(shí)邊數(shù)不超過(guò)1。修改沿途如果有一個(gè)點(diǎn)已經(jīng)有了實(shí)邊邊那么就把它原來(lái)的實(shí)邊改成虛邊。這樣每次對(duì)一個(gè)點(diǎn)操作都是在一條實(shí)路徑上(solid path)。對(duì)于每一條實(shí)路徑，都用一棵splay來(lái)維護(hù)就行了。（splay可以亂轉(zhuǎn)亂拔亂接太爽了。。- -!當(dāng)然是在一定規(guī)則下的亂。。）
/*
* $File: bounce.cpp
* $Date: Fri Jul 09 20:59:27 2010 +0800
* $Author: Tim
* $Solution: Dynamic Tree with Splay Tree implementation
* $Time complexity: O(mlogn) , per operation amorized O(logn);
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#define MAXN 200005
using namespace std;
class SplayNode
{
public:
int fa, lt, rt, size;
};
SplayNode node[MAXN + 1];
// functions below are belong to splay tree
// we can see that, this splay tree is quite
// simple, and just 'splay' function
// and size maintaining supported.
// but that what all we need to
// solve this problem
void Renew(int x)
{
if (!x)
return;
node[x].size = node[node[x].lt].size + node[node[x].rt].size + 1;
}
void RightRotate(int x)
{
int lc = node[x].lt, fa = node[x].fa;
node[x].lt = node[lc].rt; node[node[x].lt].fa = x;
node[lc].rt = x; node[x].fa = lc;
node[lc].fa = fa;
if (x == node[fa].lt)
node[fa].lt = lc;
else
node[fa].rt = lc;
Renew(x);
Renew(lc);
}
void LeftRotate(int x)
{
int rc = node[x].rt, fa = node[x].fa;
node[x].rt = node[rc].lt; node[node[x].rt].fa = x;
node[rc].lt = x; node[x].fa = rc;
node[rc].fa = fa;
if (x == node[fa].lt)
node[fa].lt = rc;
else
node[fa].rt = rc;
Renew(x);
Renew(rc);
}
void splay(int x, int FA = 0)
{
int fa, Fa;
while ((fa = node[x].fa) != FA)
{
if ((Fa = node[fa].fa) == FA)
{
if (x == node[fa].lt)
RightRotate(fa);
else
LeftRotate(fa);
}
else
{
if (x == node[fa].lt)
{
if (fa == node[Fa].lt)
{
RightRotate(Fa);
RightRotate(fa);
}
else
{
RightRotate(fa);
LeftRotate(Fa);
}
}
else
{
if (fa == node[Fa].rt)
{
LeftRotate(Fa);
LeftRotate(fa);
}
else
{
LeftRotate(fa);
RightRotate(Fa);
}
}
}
}
}
// end splay
int root;
int query_rank(int id)
{
splay(id);
return node[node[id].lt].size + 1;
}
int father[MAXN + 1];
int n;
void Init()
{
scanf("%d", &n);
for (int i = 1, k; i <= n; i ++)
{
scanf("%d", &k);
k += i;
if (k > n + 1)
k = n + 1;
father[i] = k;
node[i].size = 1;
}
node[n + 1].size = 1;
}
int split(int id)
// isolate id and the node right after it on the solid path
// and return that node
{
splay(id);
if (node[id].rt)
{
int rc = node[id].rt;
node[id].rt = node[rc].fa = 0;
node[id].size -= node[rc].size;
return rc;
}
else
return 0;
}
void Link(int id, int fa)
// let fa be the father of id,
// we assume that before this,
// id is the head of a solid path,
// and fa is the tail of a solid path,
// this was done by function 'cut' and 'split'
{
splay(id);
assert(!node[id].lt);
splay(fa);
assert(!node[fa].rt);
node[fa].rt = id;
node[fa].size += node[id].size;
node[id].fa = fa;
}
int get_head(int x)
// get the head of the solid path which x is in.
{
while (node[x].fa)
x = node[x].fa;
while (node[x].lt)
x = node[x].lt;
splay(x);
return x;
}
void expose(int id)
// turn the edges between id and the root of the tree id is in
// all into solid edges. with this operation, we can query what
// we want conveniently in a splay tree.
{
while (true)
{
id = get_head(id);
if (!father[id])
break;
split(father[id]);
Link(id, father[id]);
}
}
int query_depth(int id)
{
expose(id);
return query_rank(id) - 1;
}
void cut(int id)
// this function isolated the subtree rooted id
{
expose(id);
split(father[id]);
}
void modify_father(int id, int fa)
{
cut(id);
split(fa);
father[id] = fa;
Link(id, fa);
}
void Solve()
{
int m, cmd, id, k;
scanf("%d", &m);
while (m --)
{
scanf("%d%d", &cmd, &id);
id ++;
if (cmd == 1)
printf("%d\n", query_depth(id));
else
{
scanf("%d", &k);
k += id;
if (k > n + 1)
k = n + 1;
modify_father(id, k);
}
}
}
int main()
{
freopen("bounce.in", "r", stdin);
freopen("bounce.out", "w", stdout);
Init();
Solve();
return 0;
}