描述


http://www.lydsy.com/JudgeOnline/problem.php?id=2002

一列n个数,a[i]表示向后a[i]个,问第k个数进行多少次向后跳跃会飞出去.

分析


i连向i+a[i],那么我们建立一个森林,i是i+a[i]的一个子节点,如果i+a[i]>n,那么i连向null.这样对于节点k,问多少次飞出去,就是向上走多少个到null,也就是深度是多少,直接LCt处理.

注意:

1.这里的link并不以LCT中普遍的link.普通的link是将两个不想连的点连在一起,这样两棵树也就连在了一起.这里的link其实是改变父亲节点的意思.

 #include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,m; struct node{
node* ch[],* pa;
int s;
node(node* t){ s=; ch[]=ch[]=pa=t; }
bool d(){ return pa->ch[]==this; }
bool c(){ return pa->ch[]==this||pa->ch[]==this; }
void setc(node* x,bool d){ ch[d]=x; x->pa=this; }
void push_up(){ s=ch[]->s+ch[]->s+; }
}* null,* t[maxn];
void rot(node* x){
node* pa=x->pa; bool d=x->d();
if(pa->c()) pa->pa->setc(x,pa->d());
else x->pa=pa->pa;
pa->setc(x->ch[!d],d);
x->setc(pa,!d);
pa->push_up();
}
void splay(node* x){
while(x->c())
if(!x->pa->c()) rot(x);
else x->d()==x->pa->d()?(rot(x->pa),rot(x)):(rot(x),rot(x));
x->push_up();
}
void access(node* x){
node* t=x;
for(node* y=null;x!=null;y=x, x=x->pa){
splay(x);
x->ch[]=y;
}
splay(t);
}
void link(node* x,node* y){
access(x);
x->ch[]->pa=null; x->ch[]=null; x->pa=y; x->push_up();
}
int main(){
null=new node(NULL); null->s=;
scanf("%d",&n);
for(int i=;i<n;i++) t[i]=new node(null);
for(int i=;i<n;i++){
int k; scanf("%d",&k);
if(i+k<n) t[i]->pa=t[i+k];
}
scanf("%d",&m);
for(int i=;i<=m;i++){
int q,x,y;
scanf("%d%d",&q,&x);
if(q==){
access(t[x]);
printf("%d\n",t[x]->s);
}
else{
scanf("%d",&y);
if(x+y<n) link(t[x],t[x+y]);
else link(t[x],null);
}
}
return ;
}

最新文章

  1. [译]MVC网站教程(一):多语言网站框架
  2. 基于OpenCv的人脸检测、识别系统学习制作笔记之一
  3. Cocos2d-x SpriteFrameCache的使用
  4. oracle用户创建及权限设置
  5. CentOS下安装gns3
  6. CentOS7安装Puppet+GitLab+Bind
  7. 【转】掌握java枚举类型(enum type)
  8. packets
  9. [OpenCV]在显示窗口中截图
  10. FFmpeg源代码简单分析:avcodec_encode_video()
  11. mysql获取某个表中除了某个字段名外的所有字段名
  12. 获取subgrid中的数据并修改,含添加刷新列表的事件
  13. python生成linux命令行工具
  14. oracle多个单引号的处理
  15. c# WinFo判断当前程序是否已经启动或存在的几种方式
  16. 为什么在python中推荐使用多进程而不是多线程(转载)
  17. mongodb副本集的从库永久性设置setSlaveOk
  18. 折腾了好久,thinkphp5打开提示加载failed to open stream: No such file or directory in think start.php
  19. Linux下查看Raid磁盘阵列信息的方法
  20. python学习——面向对象的三大特性

热门文章

  1. js中对闭包的理解
  2. [转载]《STL源码剖析》阅读笔记之 迭代器及traits编程技法
  3. HDOJ 1176 免费馅饼 -- 动态规划
  4. javascript之变量、作用域、作用域链
  5. tomcat错误信息解决方案 严重:StandardServer.await:
  6. php生成随机产生六位数密码的代码
  7. Oracle 事务相关的一些测试
  8. uCGUI字符串显示过程分析和uCGUI字库的组建
  9. 正则表达式中的\n
  10. Linux df 命令