传送门

每个点都会跳到另一个点,连边就是一棵树。

更改弹力就是换边。

求一个点跳多少次跳到终点就是求这个点的深度,那么只需要维护 size 域,access(n + 1) 然后 splay(x),求 size[son[x][0]] 即可,

因为 splay 是以深度为关键字的,所以左端点就是深度比它小的。

——代码

 #include <cstdio>
#include <iostream>
#define N 200010
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
#define get(x) (son[f[x]][1] == (x))
#define isroot(x) (son[f[x]][0] ^ (x) && son[f[x]][1] ^ (x)) int n, k;
int a[N], f[N], size[N], rev[N], son[N][], s[N]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline void update(int x)
{
if(x)
{
size[x] = ;
if(son[x][]) size[x] += size[son[x][]];
if(son[x][]) size[x] += size[son[x][]];
}
} inline void pushdown(int x)
{
if(x && rev[x])
{
swap(son[x][], son[x][]);
if(son[x][]) rev[son[x][]] ^= ;
if(son[x][]) rev[son[x][]] ^= ;
rev[x] = ;
}
} inline void rotate(int x)
{
int old = f[x], oldf = f[old], wh = get(x); if(!isroot(old))
son[oldf][old == son[oldf][]] = x;
f[x] = oldf; son[old][wh] = son[x][wh ^ ];
f[son[old][wh]] = old; son[x][wh ^ ] = old;
f[old] = x; update(old);
update(x);
} inline void splay(int x)
{
int i, fa, t = ;
s[++t] = x;
for(i = x; !isroot(i); i = f[i]) s[++t] = f[i];
for(i = t; i >= ; i--) pushdown(s[i]);
for(; !isroot(x); rotate(x))
if(!isroot(fa = f[x]))
rotate(get(x) ^ get(fa) ? x : fa);
} inline void access(int x)
{
for(int t = ; x; t = x, x = f[x]) splay(x), son[x][] = t, update(x);
} inline void reverse(int x)
{
access(x);
splay(x);
rev[x] ^= ;
} inline void cut(int x, int y)
{
reverse(x);
access(y);
splay(y);
son[y][] = f[x] = ;
update(y);
} inline void link(int x, int y)
{
reverse(x);
f[x] = y;
access(x);
} inline int query(int x)
{
reverse(n + );
access(x);
splay(x);
return size[son[x][]];
} int main()
{
int i, x, y, z;
n = read();
for(i = ; i <= n; i++)
{
x = read();
a[i] = f[i] = min(i + x, n + );
size[i] = ;
}
size[n + ] = ;
k = read();
for(i = ; i <= k; i++)
{
z = read();
x = read() + ;
if(z == ) printf("%d\n", query(x));
else
{
y = read();
cut(x, a[x]);
link(x, a[x] = min(x + y, n + ));
}
}
return ;
}

最新文章

  1. linux文件分割(将大的日志文件分割成小的)
  2. 6.python模块(导入,内置,自定义,开源)
  3. Java与.NET DES加密解密互转
  4. c的基础 1. 无符号数和补码
  5. KNN算法理解
  6. leetcode第26题--Remove Duplicates from Sorted Array
  7. jquery删除未来项 jquery on
  8. Wes7 剪裁方法
  9. 【编程技巧】一些 NSArray 的基本操作代码例子
  10. Erlang cowboy 架构
  11. 2955 ACM 杭电 抢银行 01背包 乘法
  12. Python基础(七) python自带的三个装饰器
  13. web api使用JObject接收时,报“无法创建抽象类”错误
  14. 正确使用AES对称加密
  15. jquery中$.get()提交和$.post()提交的区别
  16. 单点登录(SSO)解决方案之 CAS服务端数据源设置及页面改造
  17. headfirst 07
  18. sql 内连接、外连接、自然连接等各种连接
  19. 线段树(Segment Tree)(转)
  20. 利用OPENSSH自身记录密码

热门文章

  1. n阶完全生成图的数量
  2. jQuery——表单应用(1)
  3. ACM_Appleman and Card Game(简单贪心)
  4. 解决:org.springframework.tuple.spel.TuplePropertyAccessor
  5. ActiveMQ应用
  6. java list遍历三种方法
  7. 2057. [ZLXOI2015]殉国
  8. Rxjava1升级Rxjava2踩坑一记
  9. jdbc分页查询
  10. 通过Maven将指定Jar包下载到指定的本地目录