首页 > 代码库 > 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