4764: 弹飞大爷
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 4 Solved: 4
[Submit][Status][Discuss]
Description
自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们
决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了
第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里，其中ai就是第i个小伙伴的力量值，也
就是序列的第i项。然而，因为大爷太沉了，所以有些小伙伴不能撑到锻（you）炼（xi）结束，所以我们中途会替
换一些小伙伴，也就是改变序列的某些项。而且，因为大爷太沉了，所以有些小伙伴不能把大爷扔向前方，而是会
把大爷往反方向扔，也就是序列中的一些项会是负的（当然，也可能是零喽）。现在机智的大爷通过在空中的观察
，已经知道小伙伴们的所有活动——即初始序列、所有更改操作，他想请你算一算，如果他在某时刻落到了某个位
置，那么他会在几次弹起之后落到小伙伴序列之外（毕竟摔在地上还是蛮疼的）。
Input
第一行为两个整数N和M，代表序列长度和操作次数。
第二行为N个整数，代表初始的小伙伴序列。
接下来有M行，每行代表一个操作。
如果这一行的第一个数是1，代表该操作是一个询问操作，接下来一个数X，代表询问此时大爷从X处，经过几次弹
起会摔在地上。如果永远不会摔在地上，请输出-1。
如果这一行的第一个数是2，代表该操作是一个更改操作，接下来两个数X，Y，代表将序列的第X项改为Y。
N,M <= 200000 |Ai| < N
Output
对于每次询问操作，输出弹起次数或-1。
Sample Input
3 19
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
Sample Output
3
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2
HINT
Source
今天偶然看到了某童鞋的弹飞绵羊的分块做法，十分不爽，想法卡他，然后就有了这道题，反正我觉得原来的分块方法是绝望了。但是万万木有想到，这道题依然有非LCT做法，比如大爷的Split Treap做法等等。
作为此题的出题人之一，其实我只负责题面部分和代码，解法都是ZZ和LH想的，和我没有半毛钱关系。
考虑怎么继续沿用弹飞绵羊的LCT做法，发现可能产生环，很烦。但是可以通过把环上的一条断掉，使得其在LCT中仍然是一棵树，我们把这条被“隐藏”起来的边标记在该树的Root上。那么每次加入边的时候，现考虑一下是否会形成环，如果会，就按照上面的方法处理。然后还有断边操作，只需要考虑一下断掉这条边后，是否会使得Root上的隐藏边重新显现即可。
不爽的是，刚刚放到大视野上一个下午，std就被LincHpin和Claris踩了。开心的是，至少我数据应该没造错。
#include <bits/stdc++.h> const int mxn = ; int tag[mxn];
int rev[mxn];
int siz[mxn];
int fat[mxn];
int son[mxn][]; inline bool isRoot(int t)
{
int f = fat[t]; if (!f)
return true; if (son[f][] == t)
return false;
if (son[f][] == t)
return false; return true;
} inline void update(int t)
{
siz[t] = ; if (son[t][])
siz[t] += siz[son[t][]];
if (son[t][])
siz[t] += siz[son[t][]];
} inline void connect(int f, int t, int s)
{
if (t)
fat[t] = f;
if (f)
son[f][s] = t;
} inline void rotate(int t)
{
int f = fat[t];
int g = fat[f];
int s = son[f][] == t; connect(f, son[t][!s], s);
connect(t, f, !s); fat[t] = g;
if (g && son[g][] == f)
son[g][] = t;
if (g && son[g][] == f)
son[g][] = t; update(f);
update(t);
} inline void push(int t)
{
if (rev[t])
{
rev[t] = ; if (son[t][])
rev[son[t][]] ^= ;
if (son[t][])
rev[son[t][]] ^= ; std::swap(son[t][], son[t][]);
}
} inline void pushdown(int t)
{
static int stk[mxn], tot; stk[++tot] = t; while (!isRoot(t))
stk[++tot] = t = fat[t]; while (tot)push(stk[tot--]);
} inline void splay(int t)
{
pushdown(t); while (!isRoot(t))
{
int f = fat[t];
int g = fat[f]; if (isRoot(f))
rotate(t);
else
{
int a = f && son[f][] == t;
int b = g && son[g][] == f; if (a == b)
rotate(f), rotate(t);
else
rotate(t), rotate(t);
}
}
} inline void access(int t)
{
int q = t; for (int p = ; t; p = t, t = fat[t])
splay(t), son[t][] = p, update(t); splay(q);
} inline void makeRoot(int t)
{
access(t), rev[t] ^= ;
} inline void link(int t, int f)
{
makeRoot(t), fat[t] = f;
} inline void cut(int t)
{
access(t);
fat[son[t][]] = ;
son[t][] = ;
update(t);
} inline int find(int t)
{
access(t); int p = t; while (son[p][])
p = son[p][]; return p;
} inline void Link(int t, int f)
{
if (t == f)
{
tag[t] = f;
return;
} if (find(t) != find(f))
link(t, f);
else
makeRoot(t), tag[t] = f;
} inline void change(int t, int f)
{
access(t); int p = find(t); if (!tag[p])
cut(t), Link(t, f);
else
{
if (t == p)
{
tag[p] = ;
Link(t, f);
}
else
{
int k = tag[p]; cut(t), Link(t, f); if (find(k) != find(p))
link(p, k), tag[p] = ;
}
}
} int n, m, s[mxn]; signed main(void)
{
scanf("%d%d", &n, &m); for (int i = ; i <= n; ++i)
scanf("%d", s + i); for (int i = ; i <= n; ++i)
{
int t = i + s[i]; if (t < )
Link(i, n + );
else if (t > n)
Link(i, n + );
else
Link(i, t);
} for (int i = ; i <= m; ++i)
{
int opt; scanf("%d", &opt); if (opt == )
{
int t; scanf("%d", &t); int p = find(t); if (tag[p])
puts("-1");
else
{
makeRoot(n + ), access(t);
printf("%d\n", siz[son[t][]]);
}
}
else
{
int a, b; scanf("%d%d", &a, &b); s[a] = b; int t = a + b; if (t < )
change(a, n + );
else if (t > n)
change(a, n + );
else
change(a, t);
}
}
}
@Author: YouSiki