-
-
-
-
-
- 喜聞樂見的分塊大法
- 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 ;
}