「BZOJ2002」[HNOI2010] Bounce 弹飞绵羊

2014年7月30日16,39610

Description

某天，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

题解

6:18

表示不会动态树，于是用了个分块。。。

这题的分块思想很巧妙。。。

每个点记录跳出分块的步数以及跳到下一分块的哪个点。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,block,cnt;
int pt[200005],st[200005],K[200005],belong[200005];
int l[1005],r[1005];
inline int cal(int x)
{
	int tmp=0;
	while(1)
	{
		tmp+=st[x];
		if(!pt[x])break;
		x=pt[x];
	}
	return tmp;
}
int main()
{
	n=read();block=sqrt(n);
	for(int i=1;i<=n;i++)
	    K[i]=read();
	if(n%block)cnt=n/block+1;
	else cnt=n/block;
	for(int i=1;i<=cnt;i++)
	    l[i]=(i-1)*block+1,r[i]=i*block;
	r[cnt]=n;
	for(int i=1;i<=n;i++)
	   belong[i]=(i-1)/block+1;
	for(int i=n;i>0;i--)
	{
		if(i+K[i]>n)st[i]=1;
		else if(belong[i]==belong[i+K[i]])
		    st[i]=st[i+K[i]]+1,pt[i]=pt[i+K[i]];
		else st[i]=1,pt[i]=i+K[i];
	}
	m=read();
	for(int i=1;i<=m;i++)
	{
		int f=read(),x=read(),y;
		x++;
		if(f==1)printf("%d\n",cal(x));
		else 
		{
			y=read();K[x]=y;
			for(int i=x;i>=l[belong[x]];i--)
			    if(belong[i]==belong[i+K[i]])
		            st[i]=st[i+K[i]]+1,pt[i]=pt[i+K[i]];
		        else st[i]=1,pt[i]=i+K[i];
		}
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<cstring>

#define inf 0x7fffffff

#define ll long long

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,block,cnt;

int pt[200005],st[200005],K[200005],belong[200005];

int l[1005],r[1005];

inline int cal(int x)

{

int tmp=0;

while(1)

{

tmp+=st[x];

if(!pt[x])break;

x=pt[x];

}

return tmp;

}

int main()

{

n=read();block=sqrt(n);

for(int i=1;i<=n;i++)

K[i]=read();

if(n%block)cnt=n/block+1;

else cnt=n/block;

for(int i=1;i<=cnt;i++)

l[i]=(i-1)*block+1,r[i]=i*block;

r[cnt]=n;

for(int i=1;i<=n;i++)

belong[i]=(i-1)/block+1;

for(int i=n;i>0;i--)

{

if(i+K[i]>n)st[i]=1;

else if(belong[i]==belong[i+K[i]])

st[i]=st[i+K[i]]+1,pt[i]=pt[i+K[i]];

else st[i]=1,pt[i]=i+K[i];

}

m=read();

for(int i=1;i<=m;i++)

{

int f=read(),x=read(),y;

x++;

if(f==1)printf("%d\n",cal(x));

else

{

y=read();K[x]=y;

for(int i=x;i>=l[belong[x]];i--)

if(belong[i]==belong[i+K[i]])

st[i]=st[i+K[i]]+1,pt[i]=pt[i+K[i]];

else st[i]=1,pt[i]=i+K[i];

}

return 0;

}

7:30

其实lct一样好写T T但是为何我的常数如此大T T

只要维护子树大小即可T T

#include<iostream>
#include<cstdio>
#define N 200005
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int next[N],c[N][2],fa[N],size[N],st[N];
bool rev[N];
inline bool isroot(int k)
{
	return c[fa[k]][0]!=k&&c[fa[k]][1]!=k;
}
inline void pushup(int x)
{
	size[x]=size[c[x][0]]+size[c[x][1]]+1;
}
void pushdown(int k)
{
    int l=c[k][0],r=c[k][1];
    if(rev[k])
    {
        rev[k]^=1;rev[l]^=1;rev[r]^=1;
        swap(c[k][0],c[k][1]);
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],l,r;
    if(c[y][0]==x)l=0;else l=1;r=l^1;
    if(!isroot(y))
    {
        if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;
    }
    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
    c[y][l]=c[x][r];c[x][r]=y;
	pushup(y);pushup(x);
}
void splay(int x)
{
    int top=0;st[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])
    {
        st[++top]=fa[i];
    }
    for(int i=top;i;i--)pushdown(st[i]);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if(c[y][0]==x^c[z][0]==y)rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    int t=0;
    while(x)
    {
        splay(x);
        c[x][1]=t;
        t=x;x=fa[x];
    }
}
void rever(int x)
{
    access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
    rever(x);fa[x]=y;splay(x);
}
void cut(int x,int y)
{
    rever(x);access(y);splay(y);c[y][0]=fa[x]=0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int x=read();
		fa[i]=x+i;size[i]=1;
		if(fa[i]>n+1)fa[i]=n+1;
		next[i]=fa[i];
	}
	size[n+1]=1;
	m=read();
	for(int i=1;i<=m;i++)
	{
		int f=read();
		if(f==1)
		{
			rever(n+1);
			int x=read();x++;
			access(x);splay(x);printf("%d\n",size[c[x][0]]);
		}
		else 
		{
			int x=read(),y=read();x++;
			int t=min(n+1,x+y);
			cut(x,next[x]);link(x,t);next[x]=t;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include<iostream>

#include<cstdio>

#define N 200005

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int next[N],c[N][2],fa[N],size[N],st[N];

bool rev[N];

inline bool isroot(int k)

{

return c[fa[k]][0]!=k&&c[fa[k]][1]!=k;

}

inline void pushup(int x)

{

size[x]=size[c[x][0]]+size[c[x][1]]+1;

}

void pushdown(int k)

{

int l=c[k][0],r=c[k][1];

if(rev[k])

{

rev[k]^=1;rev[l]^=1;rev[r]^=1;

swap(c[k][0],c[k][1]);

}

void rotate(int x)

{

int y=fa[x],z=fa[y],l,r;

if(c[y][0]==x)l=0;else l=1;r=l^1;

if(!isroot(y))

{

if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;

}

fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

c[y][l]=c[x][r];c[x][r]=y;

pushup(y);pushup(x);

}

void splay(int x)

{

int top=0;st[++top]=x;

for(int i=x;!isroot(i);i=fa[i])

{

st[++top]=fa[i];

}

for(int i=top;i;i--)pushdown(st[i]);

while(!isroot(x))

{

int y=fa[x],z=fa[y];

if(!isroot(y))

{

if(c[y][0]==x^c[z][0]==y)rotate(x);

else rotate(y);

}

rotate(x);

}

void access(int x)

{

int t=0;

while(x)

{

splay(x);

c[x][1]=t;

t=x;x=fa[x];

}

void rever(int x)

{

access(x);splay(x);rev[x]^=1;

}

void link(int x,int y)

{

rever(x);fa[x]=y;splay(x);

}

void cut(int x,int y)

{

rever(x);access(y);splay(y);c[y][0]=fa[x]=0;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

fa[i]=x+i;size[i]=1;

if(fa[i]>n+1)fa[i]=n+1;

next[i]=fa[i];

}

size[n+1]=1;

m=read();

for(int i=1;i<=m;i++)

{

int f=read();

if(f==1)

{

rever(n+1);

int x=read();x++;

access(x);splay(x);printf("%d\n",size[c[x][0]]);

}

else

{

int x=read(),y=read();x++;

int t=min(n+1,x+y);

cut(x,next[x]);link(x,t);next[x]=t;

}

return 0;

}

« 「BZOJ2049」[SDOI2008] Cave 洞穴勘测「BZOJ2631」tree »

BZOJ2002 – [Hnoi2010]Bounce 弹飞绵羊 – MonKey

[…] hzwer […]

sonne2010@sina.com

是我没看清。

sonne2010@sina.com

分块：读x后，x++这句是不是要注释掉。

Johann

黄学长，你的access有问题
你在"c[x,0] = t"之后，不需要pushup更新信息吗？
这应该在一些case里会成为bug的

fuboat

Rotate时不pushdown吗？

fuboat

额……当我会了lct之后，发现这个问题好傻逼……
该pushdown的在Splay时已经Rotate完了……
真是该打……

杨倚天

发现fuboat

fuboat~love~azis

发现一只野生的boat，可以划水不 ~

sherlock__conan

活捉野生fuboat！大师球！

lyx

没权限号的悲伤

hzwer.com _ Home | http://hzwer.com

「BZOJ2002」[HNOI2010] Bounce 弹飞绵羊

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论