分块大法好 ，刷分块落谷训练场，忽然看到这道题，大家都是什么lct裸体
我只想问问lct是啥，于是决定拿分块过这道题
先放题链接
题意很简单就不解释了
先把分块分好 ，然后记录每个位置弹过一个块的步数，记录每次弹出这个块后的位置
如果要是单点修改的将块内重构就好了
#include<bits/stdc++.h> using namespace std; const int N=2e5+6; int m,n,k,p,pos[N],size,a[N],num,outo[N],step[N]; struct node { int l,r,size,cnt; int pos; } bk[N]; 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; } void rebuild(int l,int r) { for (int i=r;i>=l;i--) if (i+a[i]>bk[pos[i]].r) {step[i]=1;outo[i]=i+a[i];} else {step[i]=step[i+a[i]]+1;outo[i]=outo[i+a[i]];} } void build() { size=sqrt(n);num=n/size; if (n%size) num++; for (int i=1;i<=num;i++) { bk[i].l=(i-1)*size+1; bk[i].r=i*size; } for (int i=1;i<=n;i++) pos[i]=(i-1)/size+1; rebuild(1,n); } void change(int x,int val) { a[x]=val; rebuild(bk[pos[x]].l,bk[pos[x]].r); } int query(int x) { int ans=step[x],y=outo[x]; for (int i=pos[x];i<=num&&y<=n;i++) { ans+=step[y];y=outo[y]; } return ans; } int main() { n=read(); for (int i=1;i<=n;i++) a[i]=read(); build(); m=read(); for (int i=1;i<=m;i++) { int opt,x,y; opt=read();x=read()+1; if (opt==1) {printf("%d\n",query(x));} if (opt==2) {y=read();change(x,y);} } return 0; }
原文：https://www.cnblogs.com/Hale522520/p/10546095.html