首页 > 代码库 > bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊 動態樹
bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊 動態樹
2002: [Hnoi2010]Bounce 弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 4055 Solved: 2172
[Submit][Status]
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
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
3
HINT
第一次編LCT，主要還是照着網上的標程在編，LCT的主體思路是對於每一個鏈維護一個splay，而非常巧妙的地方是splay的pnt[]指針，對於當前鏈上對應根節點，pnt指針等同於樹鏈剖分中的top指針，這樣可以巧妙地維護splay森林中每一顆子樹所代表的鏈的關係。
這個LCT支持樹的刪邊加邊。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 310000#define MAXV MAXN*2#define MAXE MAXV*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLL//ACtypedef long long qword;inline int nextInt(){ char ch; int x=0; bool flag=false; do ch=(char)getchar(),flag=(ch==‘-‘)?true:flag; while(ch<‘0‘||ch>‘9‘); do x=x*10+ch-‘0‘; while (ch=(char)getchar(),ch<=‘9‘ && ch>=‘0‘); return x*(flag?-1:1);}int n,m;int ch[MAXN][2],pnt[MAXN];int siz[MAXN];bool rt[MAXN];bool is_root(int cur){ return pnt[cur]==0 || (cur!=ch[pnt[cur]][0] && cur!=ch[pnt[cur]][1]);}void push_up(int cur){ siz[cur]=siz[ch[cur][0]]+siz[ch[cur][1]]+1;}void rotate(int cur){ int p=pnt[cur],anc=pnt[p]; int dir=ch[p][0]==cur; if (!is_root(p)) ch[anc][ch[anc][1]==p]=cur; pnt[cur]=anc; pnt[ch[cur][dir]]=p; ch[p][1-dir]=ch[cur][dir]; ch[cur][dir]=p; pnt[p]=cur; push_up(p); push_up(cur);}//int stack[MAXN];void splay(int cur){ int now; /* int tops=-1; now=cur; while (pnt[now]) stack[++tops]=now; int i; for (i=tops;i>=0;i--) push_down(i); *///本題不用打標記 while (!is_root(cur)) { int p=pnt[cur],anc=pnt[p]; if (is_root(pnt[cur])) rotate(cur); else if ( (ch[p][1]==cur) == (ch[anc][1]==p) ) rotate(p),rotate(cur);//Attention! else rotate(cur),rotate(cur); } push_up(cur);}void Access(int cur){ int son=0; for (;cur;cur=pnt[son=cur]) { splay(cur); ch[cur][1]=son; push_up(cur); }}int a[MAXN];int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int i,j,k; int x,y,z; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&a[i]); } for (i=1;i<=n;i++) siz[i]=1; siz[n+1]=1; for (i=1;i<=n;i++) { int t=i+a[i]; if (t>n+1)t=n+1; pnt[i]=t;//初始化時不存在重鏈 } scanf("%d",&m); int opt; while (m--) { scanf("%d",&opt); if (opt==1) { scanf("%d",&x); x++;//編號從0開始 Access(x); splay(x);//保證siz[x]包含整棵子樹 printf("%d\n",siz[x]-1); //printf("%d\n",siz[ch[x][0]]); 二者等價 }else { scanf("%d%d",&x,&y); x++; Access(x); splay(x);//意味着ch[x][1]==null //此時pnt[x]不在這顆splay上 pnt[ch[x][0]]=pnt[x]; pnt[x]=0; ch[x][0]=0; push_up(x);//對於x即其子節點有所改動時使用 int t=x+y;; if (t>n+1)t=n+1; pnt[x]=t; } } return 0;}
bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊 動態樹
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。