BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊 LCT

发布时间:2017-7-1 11:29:00编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊 LCT ",主要涉及到BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊 LCT 方面的内容,对于BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊 LCT 感兴趣的同学可以参考一下。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 200010using namespace std;int n;int fa[N];int ch[N][2];int rt[N];int size[N];int rev[N];void init(){    for(int i=1;i<=n;i++)rt[i]=1,size[i]=1;}void pushup(int x){    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}void rotate(int x){    int y=fa[x],kind=ch[y][1]==x;    ch[y][kind]=ch[x][!kind];    fa[ch[x][!kind]]=y;    ch[x][!kind]=y;    fa[x]=fa[y],fa[y]=x;    if(rt[y])    {        rt[y]=0,rt[x]=1;    }else ch[fa[x]][ch[fa[x]][1]==y]=x;    pushup(y);}void splay(int x){    while(!rt[x])    {        int y=fa[x],z=fa[y];        if(rt[y]) rotate(x);        else        {            if((ch[y][1]==x)==(ch[z][1]==y))            {                rotate(y),rotate(x);            }else rotate(x),rotate(x);        }    }    pushup(x);}void access(int x){    int y=0;    while(x)    {        splay(x);        rt[ch[x][1]]=1,rt[y]=0;        ch[x][1]=y;        pushup(x);        y=x,x=fa[x];    }}void mt(int x){    access(x);    splay(x);}void link(int x,int y){    mt(x);    fa[ch[x][0]]=0;    rt[ch[x][0]]=1;    ch[x][0]=0;    fa[x]=y;    pushup(x);}int main(){    scanf("%d",&n);    init();    for(int i=1;i<=n;i++)    {        int x;        scanf("%d",&x);        if(i+x<=n)link(i,i+x);    }    int m;    scanf("%d",&m);    while(m--)    {        int jd;        scanf("%d",&jd);        switch(jd)        {            int x,y;            case 1:scanf("%d",&x);x++;mt(x);printf("%d\n",size[ch[x][0]]+1);break;            case 2:scanf("%d%d",&x,&y);x++;if(x+y>n)link(x,0);else link(x,x+y);break;        }


上一篇:Shell函数的7种用法介绍
下一篇:RSA原理说明

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款