某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Input
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4 1 2 1 1 3 1 1 2 1 1 1 1
Sample Output
2 3
Hint
C++版本一
分块
直接跳的话复杂度是O(nm)，显然是无法接受的。显然我们无法优化询问这个m，那么如何从n入手优化呢？
如果跳的次数能有效减少，那么对于时间的优化是巨大的，所以我们考虑预处理一下从某个点跳到某个点需要几步
最直接的思考，倒着递推O(n)，预处理每个点跳到终点要几步？对于修改较少的输入时可以接受的，可是一旦修改的次数增多，复杂度还是O(nm)，
那么取折衷的方案是，我们考虑把n个数字分成若干段，每一段的大小是sqrt(n)，然后预处理每一个点跳到另外的位置（该位置属于另一个区块，也有可能是不相邻的区块，因为一步可能跳很远，比一块的大小还远），以及从这个点到另一个块的那个位置需要的步数。这要查询的时候最多只要sqrt(n)的跳跃就能出结果。对于修改，我们只需要修改要修改的那个点属于的块中每个点跳到另外块的位置以及需要的步数即可，因为每个块只有sqrt(n)个点，所以总体复杂度为O(m*sqrt(n))。
#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <stdio.h>
using namespace std;
const int N=200000+100;
int n,m,sq,num;
int a[N],bl[N],c[N],b[N], l[N], r[N];
int main()
{
while(~scanf("%d",&n)){
sq=sqrt(n);
num = n / sq;
if(n % sq) num++;//不能整除加1
//块的范围
for(int i = 1; i <= num; i++){
l[i] = (i - 1) * sq + 1;
r[i] = i * sq;
}
r[num] = n;
for(int i=1;i<=n;i++){
bl[i]=(i-1)/sq+1;
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--){
b[i]=i+a[i];
c[i]=1;
if (b[i]<=n&&bl[i]==bl[b[i]]){
c[i]=c[b[i]]+1;
b[i]=b[b[i]];
}
//printf("%d %d\n",b[i],c[i]);
}
scanf("%d",&m);
int i,j,k;
while(m--){
scanf("%d",&i);
if(i==1){
scanf("%d",&j);
j++;
int ans=0;
while (n>=j){
ans+=c[j];
j=b[j];
}
printf("%d\n",ans);
}else{
scanf("%d%d",&j,&k);
int I=j+1;
a[I]=k;
for(int t=r[bl[I]];t>=l[bl[I]];t--){
b[t]=t+a[t];
c[t]=1;
if(b[t]<=n&&bl[t]==bl[b[t]]){
c[t]=c[b[t]]+1;
b[t]=b[b[t]];
}
//printf("%d %d\n",b[i],c[i]);
}
}
}
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
LCT
Link−Cut−TreeLink−Cut−Tree 的模板题，当然这个模板没有那么裸，操作也没有那么多啦……
话说LCTLCT确是一个很恶心的板子，我曾以为平衡树就是极致的恶心了，没想到LCTLCT刷新了我对代码的印象的上界（曾经是二逼平衡树），但是弹飞绵羊不是很长（130130左右），真正恶心的板子在这里
Sone1Sone1
还没写，估计有200+200+
回到弹飞绵羊，我们可以定义一个虚拟节点n+1n+1，表示被弹飞。而如果节点ii能够弹到jj（弹飞就设为n+1n+1），就将ii设为jj的儿子。因为每个ii都只有一个父亲，并且它的父亲编号一定比ii大，最终都会汇向n+1n+1，所以可以发现，这其实是一棵有根树。
那么显然，修改操作就是修改父亲，查询操作就是查询深度。而修改父亲和查询深度都是LCTLCT很拿手的，我们就这样做出来了。
PS:PS:查询深度时，先Access(x)Access(x)，让n+1n+1到xx变成一棵SplaySplay，然后Splay(x)Splay(x)，让xx变成根，这时size[x]−1size[x]−1就是xx的深度了，所以还要维护一个sizesize数组
然后就是代码了，这次加了注释，就可以看懂了~
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 200005
int n,m,K[N];
char S[10];
namespace LCT
{
int cnt,ch[N][2],fa[N],dt[N],siz[N];
bool rv[N],tp[N];
//节点个数 儿子 父亲 翻转懒标记 数据 是否为根
inline void Push_Down(int x)//懒标记下传
{
if(rv[x])
{
rv[x]=0;
swap(ch[x][0],ch[x][1]);
if(ch[x][0])rv[ch[x][0]]^=1;
if(ch[x][1])rv[ch[x][1]]^=1;
}
}
inline void Push_Up(int x)//标记上传
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
inline void Rotate(int x)//万能旋转
{
int y=fa[x],z=fa[fa[x]];
if(!y||tp[x])return;
int wh=(x==ch[y][1]);
Push_Down(x);
ch[y][wh]=ch[x][!wh];
if(ch[y][wh])fa[ch[y][wh]]=y;
ch[x][!wh]=y;
fa[y]=x;
if(!tp[y])ch[z][y==ch[z][1]]=x;
fa[x]=z;
tp[x]=tp[y],tp[y]=0;
rv[x]=rv[y],rv[y]=0;
Push_Up(y);
}
inline void Splay(int x)//翻转至根
{
Push_Down(x);Push_Up(x);
for(;!tp[x];Rotate(x))
{
int y=fa[x];
if(!tp[y])
{
int z=fa[y];
if((x==ch[y][1])==(y==ch[z][1]))Rotate(y);
else Rotate(x);
}
}
Push_Down(x);Push_Up(x);
}
inline int Access(int x)//LCT的象征
{
int last=0;
while(x)
{
Splay(x);
if(ch[x][1])tp[ch[x][1]]=1;
ch[x][1]=last;
if(last)tp[last]=0;
Push_Up(x);
last=x;
x=fa[x];
}
return last;
}
inline void Beroot(int x)//换根
{
Access(x);
Splay(x);
rv[x]^=1;
Push_Down(x);
Push_Up(x);
}
inline void Link(int u,int v)//链接(u->v)
{
Beroot(u);
Access(v);
fa[u]=v,tp[u]=1;
}
inline void Cut(int u,int v)//删除(u->v)
{
Beroot(u);
Splay(v);
if(fa[v]==u)
fa[v]=0;
else
fa[u]=ch[v][0]=0,tp[u]=1;
Push_Up(v);Push_Up(u);
Push_Up(v);Push_Up(u);
}
inline void Link_Cut(int u,int v,int w)//删除(u->v)并链接(u->w)
{
Cut(u,v);
Link(u,w);
}
inline int Find_Root(int x)//找根
{
Access(x);
Splay(x);
while(ch[x][0])
{
Push_Down(x);
x=ch[x][0];
}
return x;
}
inline bool Query_Linked(int u,int v)//判断是否连通
{
return Find_Root(u)==Find_Root(v);
}
inline int Query_Deep(int x)//求深度
{
Access(x);
Splay(x);
return siz[x]-1;
}
inline void Init(int n)//初始化
{
cnt=n;
memset(ch,0,sizeof(ch));
memset(fa,0,sizeof(fa));
memset(dt,0,sizeof(dt));
memset(tp,1,sizeof(tp));
memset(rv,0,sizeof(rv));
for(int i=1;i<=n;i++)
siz[i]=1;
}
}
int Read()
{
int p=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar();
return p;
}
void Solve()
{
for(int i=1;i<=m;i++)
{
int opt;
opt=Read();
if(opt==1)
{
int p=Read();
printf("%d\n",LCT::Query_Deep(p+1));
}
else
{
int a=Read(),b=Read();
a++;
LCT::Link_Cut(a,min(a+K[a],n+1),min(a+b,n+1));
LCT::Beroot(n+1);
K[a]=b;
}
}
}
void Init()
{
n=Read();
LCT::Init(n+1);
for(int i=1;i<=n;i++)
{
K[i]=Read();
LCT::Link(i,min(i+K[i],n+1));
}
LCT::Beroot(n+1);
m=Read();
}
int main()
{
Init();
Solve();
}
京公网安备 11010502036488号