注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2002(hnoi2010)弹飞绵羊  

2013-02-21 23:10:23|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

动态树入门题

于是就敲了个LCT

 

其实分块爆搞也是可以过得而且效率不错

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 200010
#define update(p) (sum[p]=sum[son[p][0]]+sum[son[p][1]]+1)
using namespace std;
int n;
int father[MAXN],son[MAXN][2],sum[MAXN];
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
bool Root(int p){  return p!=son[father[p]][0]&&p!=son[father[p]][1];  }
void Rotate(int p,int x)
{
    int mark=p==son[x][1],y=son[p][mark^1],z=father[x];
    if(y!=0)  father[y]=x;
    if(x==son[z][0])  son[z][0]=p;
    if(x==son[z][1])  son[z][1]=p;
    son[x][mark]=y,father[x]=p,son[p][mark^1]=x,father[p]=z,update(x);
}
void Splay(int p)
{
    while(!Root(p))
    {
        int x=father[p],y=father[x];
        if(Root(x))  Rotate(p,x);
        else if((p==son[x][0])^(x==son[y][0]))  Rotate(p,x),Rotate(p,y);
        else Rotate(x,y),Rotate(p,x);
    }
    update(p);
}
void read()
{
    Read(n);
    for(int i=1,v;i<=n;i++)
    {
        Read(v);
        int next=i+v<=n?i+v:0;
        father[i]=next;
        if(next&&son[next][1]==0)  son[next][1]=i;
    }
    for(int i=1;i<=n;i++)
        if(son[i][1]==0)
            Splay(i);
}
void Access(int p)
{
    for(int v=0;p;v=p,p=father[p])
        Splay(p),son[p][1]=v,update(p);
}
void Cut(int p,int q)
{
    Access(p),Splay(p);
    father[son[p][0]]=0,father[p]=q,son[p][0]=0,update(p);
}
int Qdeep(int p)
{
    Access(p),Splay(p);
    return sum[son[p][0]]+1;
}
void Ask()
{
    int m,type,a,b;
    Read(m);
    for(int i=1;i<=m;i++)
    {
        Read(type);
        if(type==1)
        {
            Read(a);
            printf("%d\n",Qdeep(a+1));
        }
        if(type==2)
        {
            Read(a),Read(b);
            Cut(a+1,a+b+1<=n?a+b+1:0);
        }
    }
}
int main()
{
    read();
    Ask();
    return 0;
}


  评论这张
 
阅读(630)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017