BZOJ2002[HNOI2010] 弹飞绵羊 （LCT）
Description
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Input
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4 1 2 1 1 3 1 1 2 1 1 1 1
Sample Output
2 3
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2002
题解：
LCT基础板题，终于凑出了属于自己代码风格的一套LCT模板，以后终于不用百度别人的去改LCT了
只不过此题的link和cut操作可以叠在一起，由于题目性质，cut后的点一定是某个辅助树的根，所以不需要换根操作（evert），自然也就不用写pushdown。不过写上也没错，只是运行速度会稍慢一些。
代码（写了些多余的比如push_down）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
int num = 0;
char ch;
bool flag = false;
while(true){
ch = getchar();
if(ch == '-' || isdigit(ch))break;
}
if(ch == '-')
flag = true;
else num = ch - '0';
while(isdigit(ch = getchar()))
num = num * 10 + ch - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 5e5+5;
int cnt = 0;
int rd,a[maxn];
int opt,b,c;
int n,m;
struct splay_node{
splay_node *pre,*ch[2];
int siz;
int rf;
void update();
void rev(){
swap(ch[0],ch[1]);
return;
}
void set_ch(int wh,splay_node *child);
int get_wh(){
return pre->ch[0] == this ? 0 : 1;
}
void push_down();
bool isroot();
}pool[maxn],*null,*x,*y;
void init(){
null = pool;
null->pre = null->ch[0] = null->ch[1] = null;
null->siz = 0;
null->rf = 0;
return;
}
void splay_node::update(){
siz = ch[0]->siz + ch[1]->siz + 1;
return ;
}
bool splay_node::isroot(){
if(pre->ch[0] != this && pre->ch[1] != this)return true;
return false;
}
void get_new(){
splay_node *newone = pool + ++cnt;
newone->pre = newone->ch[1] = newone->ch[0] = null;
newone->siz = 1;
newone->rf = 0;
return;
}
void splay_node::set_ch(int wh,splay_node *child){
ch[wh] = child;
if(child != null)child->pre = this;
update();
return;
}
splay_node *find_splay(int p){
return pool + p;
}
void splay_node::push_down(){
if(rf){
if(ch[0] != null){
ch[0]->rf ^= 1;
ch[0]->rev();
}
if(ch[1] != null){
ch[1]->rf ^= 1;
ch[1]->rev();
}
}
rf = 0;
}
void rotate(splay_node *&now){
splay_node *fa = now->pre,*grand = now->pre->pre;
bool o = fa->isroot();
int wh = now->get_wh();
fa->set_ch(wh,now->ch[wh^1]);
now->set_ch(wh^1,fa);
now->pre = grand;
if(!o){
grand->ch[grand->ch[0] == fa ? 0 : 1] = now;
grand->update();
}
return;
}
void splay(splay_node *now){
while(!now->isroot()){
if(!now->pre->isroot()){
now->pre->pre->push_down();
now->pre->push_down();
now->push_down();
now->pre->get_wh() == now->get_wh() ? rotate(now->pre) : rotate(now);
}
else{
now->pre->push_down();
now->push_down();
}
rotate(now);
}
return;
}
void access(splay_node *now){
splay_node *last = null;
splay_node *bupt = now;
while(now != null){
splay(now);
now->set_ch(1,last);
last = now;
now = now->pre;
}
splay(bupt);
return;
}
void link(splay_node *now,splay_node *newf){
access(now);
now->ch[0]->pre = null;
now->ch[0] = null;
now->pre = newf;
now->update();
return;
}
splay_node *get_root(splay_node *now){
access(now);
while(now->ch[0] != null){
now = now->ch[0];
}
return now;
}
int check_ans(splay_node *now){
access(now);
return now->ch[0]->siz;
}
int main(){
init();
n = get_num();
for(int i = 1;i <= n;++i){
rd = get_num();
a[i] = i + rd;
get_new();
}
get_new();
for(int i = 1;i <= n;++i){
if(a[i] > n+1)a[i] = n + 1;
x = find_splay(i);
y = find_splay(a[i]);
link(x,y);
}
m = get_num();
while(m--){
opt = get_num();
if(opt == 1){
b = get_num();
b++;
x = find_splay(b);
printf("%d\n",check_ans(x));
}
if(opt == 2){
b = get_num();
b++;
c = get_num();
a[b] = min(b+c,n+1);
x = find_splay(b);
y = find_splay(a[b]);
link(x,y);
}
}
return 0;
}
No Leanote account ? Sign up now.