首页 > 代码库 > BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊（分块）
BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊（分块）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2002
【题目大意】
给出一片森林，操作允许更改一个节点的父亲，查询一个节点的深度。
父亲节点的编号一定大于子节点
【题解】
我们将所有的节点按照序号分块，记录其到下一个分块的深度，
以及其可以跳到下一个分块的位置，
那么修改节点的父亲对于所存储的数据的影响就被缩小到一个块内，单次修改sqrt(n)。
动态树做法：链接
【代码】
#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int N=200010;int n,m,op,pos[N],block,l[N],r[N],K[N],d[N],nxt[N];int cal(int x){for(int res=0;;x=nxt[x]){res+=d[x];if(!nxt[x])return res;}}int main(){ scanf("%d",&n); block=sqrt(n+0.5); for(int i=1;i<=n;i++)scanf("%d",&K[i]); if(n%block)m=n/block+1; else m=n/block; for(int i=1;i<=m;i++)l[i]=(i-1)*block+1,r[i]=i*block; r[m]=n; for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1; for(int i=n;i;i--){ if(i+K[i]>n)d[i]=1; else if(pos[i]==pos[i+K[i]])d[i]=d[i+K[i]]+1,nxt[i]=nxt[i+K[i]]; else d[i]=1,nxt[i]=i+K[i]; }scanf("%d",&op); while(op--){ int u,x,y; scanf("%d%d",&u,&x);x++; if(u==1)printf("%d\n",cal(x)); else{ scanf("%d",&y); K[x]=y; for(int i=x;i>=l[pos[x]];i--)if(pos[i]==pos[i+K[i]]){ d[i]=d[i+K[i]]+1; nxt[i]=nxt[i+K[i]]; }else d[i]=1,nxt[i]=i+K[i]; } }return 0;}BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊（分块）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。