首页 > 代码库 > AC日记——[HNOI2010]BOUNCE 弹飞绵羊 洛谷 P3203
AC日记——[HNOI2010]BOUNCE 弹飞绵羊 洛谷 P3203
[HNOI2010]BOUNCE 弹飞绵羊
思路:
SBlct;
代码:
#include <bits/stdc++.h>using namespace std;#define maxn 200005int n,m,f[maxn],ch[maxn][2],rev[maxn],ki[maxn],sta[maxn],top,lit,size[maxn];inline void in(int &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘)Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}void updata(int now){ size[now]=size[ch[now][0]]+size[ch[now][1]]+1;}void downdata(int now){ if(rev[now]) { swap(ch[now][1],ch[now][0]); rev[now]^=1,rev[ch[now][1]]^=1,rev[ch[now][0]]^=1; }}bool isroot(int now){ return (ch[f[now]][1]!=now)&&(ch[f[now]][0]!=now);}void rotate(int now){ int fa=f[now],ffa=f[fa],l=(ch[fa][1]==now),r=l^1; if(!isroot(fa)) ch[ffa][ch[ffa][1]==fa]=now; f[now]=ffa,f[fa]=now,ch[fa][l]=ch[now][r],ch[now][r]=fa; if(ch[fa][l]) f[ch[fa][l]]=fa; updata(fa),updata(now);}void splay(int now){ top=1,sta[1]=now; for(int i=now;!isroot(i);i=f[i]) sta[++top]=f[i]; while(top) downdata(sta[top--]); int fa,ffa; while(!isroot(now)) { fa=f[now],ffa=f[fa]; if(!isroot(fa)) { if((ch[fa][0]==now)^(ch[ffa][0]==fa)) rotate(fa); else rotate(now); } rotate(now); }}void access(int now){ for(int i=0;now;i=now,now=f[now]) splay(now),ch[now][1]=i;}void makeroot(int now){ access(now),splay(now),rev[now]^=1;}void split(int x,int y){ makeroot(x),access(y),splay(y);}void cut(int x,int y){ split(x,y),f[x]=ch[y][0]=0;}void link(int x,int y){ makeroot(x),f[x]=y;}int ofans(int x){ makeroot(lit),access(x),splay(x); return size[ch[x][0]];}int main(){ freopen("data.txt","r",stdin); in(n),lit=n+1;int u,v,op; for(int i=1;i<=n;i++) { in(ki[i]); if(i+ki[i]<=n) link(i,i+ki[i]); else link(i,lit); } in(m); while(m--) { in(op); if(op==1) in(u),u++,printf("%d\n",ofans(u)); else { in(u),in(v),u++; if(u+ki[u]<=n) cut(u,u+ki[u]); else cut(u,lit); ki[u]=v; if(u+v<=n) link(u,u+v); else link(u,lit); } } return 0;}
AC日记——[HNOI2010]BOUNCE 弹飞绵羊 洛谷 P3203
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。