[luoguP3203][HNOI2010]BOUNCE 弹飞绵羊(LCT)
2024-08-30 21:36:34
每个点都会跳到另一个点,连边就是一棵树。
更改弹力就是换边。
求一个点跳多少次跳到终点就是求这个点的深度,那么只需要维护 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 ;
}
最新文章
- linux文件分割(将大的日志文件分割成小的)
- 6.python模块(导入,内置,自定义,开源)
- Java与.NET DES加密解密互转
- c的基础 1. 无符号数和补码
- KNN算法理解
- leetcode第26题--Remove Duplicates from Sorted Array
- jquery删除未来项 jquery on
- Wes7 剪裁方法
- 【编程技巧】一些 NSArray 的基本操作代码例子
- Erlang cowboy 架构
- 2955 ACM 杭电 抢银行 01背包 乘法
- Python基础(七) python自带的三个装饰器
- web api使用JObject接收时,报“无法创建抽象类”错误
- 正确使用AES对称加密
- jquery中$.get()提交和$.post()提交的区别
- 单点登录(SSO)解决方案之 CAS服务端数据源设置及页面改造
- headfirst 07
- sql 内连接、外连接、自然连接等各种连接
- 线段树(Segment Tree)(转)
- 利用OPENSSH自身记录密码