聽說有版權(quán)問題不能貼題目？。那就只能先忍一忍了。
題目抽象為：我們有一個由有根樹構(gòu)成的森林，對這個森林進行兩種操作：
把某棵子樹拔下來接到某一棵樹（可能還是那個子樹原來所在的樹）的某個節(jié)點下面，詢問某個節(jié)點在樹中的深度。
因為把一棵邊權(quán)為1的樹的括號序列拿出來，樹上某兩點的距離就是在括號序列中兩點間沒匹配括號的個數(shù)（有左括號右括號選擇的區(qū)別，具體分析處理）。當然，既然是對一群樹操作，那就直接用動態(tài)樹就行了。
于是就去學了動態(tài)樹。發(fā)現(xiàn)其實不算很難（1.指時間復(fù)雜度均攤logn的算法，還有基于輕重邊剖分的嚴格logn的算法 2.如果你對splay熟的話），寫起來也就基本上就是一棵splay，也算比較好寫的。。（以后就告別路徑剖分了。。太麻煩了。。復(fù)雜度也沒動態(tài)樹好。。）
以下所說的動態(tài)樹都是基于splay的時間復(fù)雜度均攤logn的動態(tài)樹。
動態(tài)樹的主要思想就是：類似輕重邊剖分一樣，把整棵樹劃分成若干實邊(solid edge)和虛邊(dashed edge)，但這個都是根據(jù)你的需要來設(shè)定的，不像輕重邊一樣每個點往下都必須有一條重邊（單獨的葉子節(jié)點算長度為0的重邊），而是每次把你所需要操作的點到根的邊都改為實邊(expose操作)，且每個點往下的實邊數(shù)不超過1。修改沿途如果有一個點已經(jīng)有了實邊邊那么就把它原來的實邊改成虛邊。這樣每次對一個點操作都是在一條實路徑上(solid path)。對于每一條實路徑，都用一棵splay來維護就行了。（splay可以亂轉(zhuǎn)亂拔亂接太爽了。。- -!當然是在一定規(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;
}