-
-
-
-
-
- 喜闻乐见的分块大法
- LCT
-
-
-
-
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
这道题有两种做法，一种是分块，另一种是LCT。
喜闻乐见的分块大法
分块的思路就是把所有的点分成sqrt(n)块，对于每个点我们都记录两个信息：它走出当前分块所需的步数、它走出当前分块所走到的地方。这两个直接在分块里暴力处理。然后在统计答案时从后往前用一个类似前缀和的思路累加即可。
修改只要暴力修改分块里n及其左边的点即可。
#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,tot,ans,blo;
int a[];
struct node{
int pl,t;
}f[];
int read(){
char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
int main()
{
n=read();blo=sqrt(n);
for(int i=;i<n;i++) a[i]=read();
for(int i=n-;i>=;i--){
int nxt=i+a[i];
if(nxt>n-||nxt>=(i/blo+)*blo) f[i].t=,f[i].pl=nxt;
else f[i].t=f[nxt].t+,f[i].pl=f[nxt].pl;
}
m=read();
for(int i=;i<=m;i++){
int rec=read();
if(rec==){
int x=read();ans=;
for(int j=x;j<=n-;j=f[j].pl) ans+=f[j].t;
printf("%d\n",ans);
}
else{
int p=read(),x=read();
a[p]=x;
for(int j=p;j>=p/blo*blo;j--){
int nxt=j+a[j];
if(nxt>n-||nxt>=(j/blo+)*blo) f[j].t=,f[j].pl=nxt;
else f[j].t=f[nxt].t+,f[j].pl=f[nxt].pl;
}
}
}
return ;
}
LCT
这题用LCT的思路就会很简单，对于点x，直接link(x,to[x])即可。修改的时候就cut(x,to[x])然后link(x,new)即可。
答案就是x到n+1的路径上的点数，直接统计即可。
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int read(){
char c;int x=,y=;while(c=getchar(),(c<'0'||c>'9')&&c!='-');
if(c=='-') y=-;else x=c-'0';while(c=getchar(),c>='0'&&c<='9')
x=x*10+c-'0';return x*y;
}
struct LCT{
int son[MAXN][],val[MAXN],siz[MAXN],fa[MAXN],rev[MAXN],sta[MAXN];
void up(int k){siz[k]=siz[son[k][]]+siz[son[k][]]+val[k];}
int isroot(int k){
return son[fa[k]][]!=k&&son[fa[k]][]!=k;
}
void revers(int k){
swap(son[k][],son[k][]);
rev[k]^=;
}
void down(int k){
if(rev[k]){
revers(son[k][]);
revers(son[k][]);
rev[k]=;
}
}
void rotate(int k){
if(isroot(k)) return;
int f=fa[k],gran=fa[f],d=(son[f][]==k),w=son[k][d^];
if(!isroot(f)) son[gran][son[gran][]==f]=k;
fa[k]=gran;fa[f]=k;if(w)fa[w]=f;
son[k][d^]=f;son[f][d]=w;
up(f);up(k);
}
void splay(int k){
int y=k,z=;sta[++z]=y;
while(!isroot(y)) sta[++z]=y=fa[y];
while(z) down(sta[z--]);
while(!isroot(k)){
y=fa[k];z=fa[y];
if(!isroot(y)) rotate((son[y][]==k)^(son[z][]==y)?k:y);
rotate(k);
}
up(k);
}
void access(int k){
int x=;
do{
splay(k);son[k][]=x;up(k);x=k;k=fa[k];
}while(k);
}
void makeroot(int k){
access(k);splay(k);revers(k);
}
void split(int x,int y){
makeroot(x);access(y);splay(y);
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
void cut(int x,int y){
split(x,y);
fa[x]=son[y][]=;
up(y);
}
}T;
int n,m,go[MAXN];
int main()
{
n=read();
for(int i=;i<=n;i++) T.val[i]=;
for(int i=;i<=n;i++){
go[i]=read();
T.link(i,i+go[i]>n?n+:i+go[i]);
}
m=read();
for(int i=;i<=m;i++){
int x=read(),y=read();y++;
if(x==){
T.split(y,n+);
printf("%d\n",T.siz[n+]);
}
else{
int z=read();
T.cut(y,y+go[y]>n?n+:y+go[y]);
T.link(y,y+z>n?n+:y+z);
go[y]=z;
}
}
return ;
}