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.