【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2002

【题目大意】

  给出一片森林,操作允许更改一个节点的父亲,查询一个节点的深度。

【题解】

  更改父亲操作直接cutf然后修改一下即可,查询深度则直接提取链然后splay一下

【代码】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int f[N],son[N][2],val[N],sum[N],tmp[N];bool rev[N];
bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}
void rev1(int x){if(!x)return;swap(son[x][0],son[x][1]);rev[x]^=1;}
void pb(int x){if(rev[x])rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;}
void up(int x){
sum[x]=val[x];
if(son[x][0])sum[x]+=sum[son[x][0]];
if(son[x][1])sum[x]+=sum[son[x][1]];
}
void rotate(int x){
int y=f[x],w=son[y][1]==x;
son[y][w]=son[x][w^1];
if(son[x][w^1])f[son[x][w^1]]=y;
if(f[y]){
int z=f[y];
if(son[z][0]==y)son[z][0]=x;else if(son[z][1]==y)son[z][1]=x;
}f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y);
}
void splay(int x){
int s=1,i=x,y;tmp[1]=i;
while(!isroot(i))tmp[++s]=i=f[i];
while(s)pb(tmp[s--]);
while(!isroot(x)){
y=f[x];
if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
rotate(x);
}up(x);
}
void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,up(x);}
void cutf(int x){access(x);splay(x);f[son[x][0]]=0;son[x][0]=0;up(x);}
int query(int x){access(x);splay(x);return sum[x];}
int n,x,y,q,op,K[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&K[i]);
if(i+K[i]>n)f[i]=0;
else f[i]=i+K[i];
val[i]=sum[i]=1;
}scanf("%d",&q);
while(q--){
scanf("%d%d",&op,&x);x++;
if(op==1)printf("%d\n",query(x));
else{
scanf("%d",&y);
if(x+y>n)y=0; else y=x+y;
K[x]=y; cutf(x); f[x]=y;
}
}return 0;
}

最新文章

  1. 【阮一峰】深入研究URL编码问题及JavaScript相应的解决方案
  2. 百度贴吧python吧抓取用户名和图片
  3. gvim如何显示html属性代码提示? vim 如何显示 javascript属性及方法提示?
  4. 安装SQL Server 2012 『企业中文版』
  5. zookeeper安装配置
  6. SpringMvc 使用poi导入导出Excel
  7. Ubuntu 14.10 下NodeJS Cannot find module &#39;npmlog&#39;
  8. HDU 1671 Phone List(字符处理)
  9. 整合spring roo,maven,mybatis,spring-flex,blazeds,mysql
  10. 【转】如何检测wifi信号强度? -- 不错
  11. JavaScript prototype.js提升JavaScript开发效率
  12. OSG消锯齿
  13. 进入MFC讲坛的前言(五)
  14. 真实故事:网站遭遇DOS攻击
  15. 【一】Swift 3.0 新浪微博项目实战 -整体框架搭建
  16. Oracle创建表空间、用户、分配权限语句
  17. Delete 命令详解
  18. IOS-企业开发人员账号&amp;amp;邓白氏码申请记录
  19. Download SQL Server Management Studio (SSMS)下载地址
  20. Windows server利用批处理脚本判断端口, 启动tomcat

热门文章

  1. php分页类及其实现原理
  2. 随意记的一点 js 笔记
  3. sass教程
  4. chrome实现全浏览器跨域ajax请求
  5. &lt;meta http-equiv=&quot;Pragma&quot; content=&quot;no-cache&quot;&gt;
  6. 移动跨平台开发框架Ionic开发一个新闻阅读APP
  7. rsyslog ~ 波浪号
  8. centos 6.7 perl 版本 This is perl 5, version 22 安装DBI DBD
  9. 什么时候css会见less
  10. Objective-C官方文档翻译 Block