P3203 [HNOI2010] 弹飞绵羊 题解

link T3 desu

这道题有两种做法：分块和 LCT。LCT 很无脑，这里只讲分块。

先对整个数组分块，块长取 $\sqrt n$。

分完块后维护两个东西：

1. jumpc[i]：计算每个点跳出这个块需要多少步

2. jumpp[i]：计算每个点跳出这个块会去到哪里

显然的，计算答案只需要跳 $\sqrt n$ 个块即可。主要讲一下 update 操作。

我们考虑建出每个块内弹力器往下一个弹力器的边。如果跳出块就不建。

显然图是 DAG。

当修改一个点 $p$ 的弹力系数时，必然是所有 $p$ 上游的点受到牵连。

那么如何修改这些值？

显然有新的 jumpc[p]=(p+val>r)?(1):(jumpc[p+val]+1)，减去原来的 jumpc[p] 可以得到这些点 jumpc 的 delta，
然后 jumpp[p] 也是类似的，直接赋值即可。

可以 dfs $p$ 上游的点，暴力修改，单次复杂度为 $\sqrt n$。

---

说句鲜花：由于 update 操作常数比 query 常数要大，所以可以缩小一点块长。（不过一点效果没有就是了）

分块代码：

int n;
ll a[maxn];
void input(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
}

int B;
struct Block{
	int l,r,len;
	Block(){}
	Block(int l,int r,int len):l(l),r(r),len(len){}
}bk[maxn];
int m;
int inbk[maxn];
void calc_bk(){
	B=floor(sqrtf(n)+0.45);
	for(int l=1;l<=n;l+=B){
		int r=min(n,l+B-1);
		bk[++m]=Block(l,r,r-l+1);
		for(int j=l;j<=r;++j) inbk[j]=m;
	}
}

int jumpc[maxn];//计算每个点跳出这个块需要多少步
ll jumpp[maxn];//计算每个点跳出这个块会去到哪里

int edge[maxn];
unordered_set<int> needge[maxn];
void calc_jumpout(){
	for(int b=1;b<=m;++b){
		int l=bk[b].l,r=bk[b].r;
		for(int i=l;i<=r;++i){
			int now=i;
			while(now<=r) now+=a[now],++jumpc[i];
			jumpp[i]=now;

			if(i+a[i]<=r){
				edge[i]=i+a[i];
				needge[i+a[i]].insert(i);
			}
		}
	}
}

void dfs(int x,ll val,int endp){
	jumpc[x]+=val;
	jumpp[x]=endp;
	for(auto y: needge[x]){
		dfs(y,val,endp);
	}
}

void update(int p,ll val){
	int b=inbk[p];
	int l=bk[b].l,r=bk[b].r;

	ll stepbefore=jumpc[p],stepafter=(p+val>r)?(1):(jumpc[p+val]+1);
	int endp=(p+val>r)?(p+val):(jumpp[p+val]);
	dfs(p,-stepbefore+stepafter,endp);
	
	if(edge[p]) needge[edge[p]].erase(p);
	edge[p]=(p+val>r)?(0):(p+val);
	if(edge[p]) needge[edge[p]].insert(p);
}


int go(ll now){
	int res=0;
	while(now<=n){
		res+=jumpc[now];
		now=jumpp[now];
	}
	return res;
}

int q;
void ask(){
	q=read();
	for(int i=1;i<=q;++i){
		int op=read();
		if(op==1){
			int st=read()+1;
			printf("%d\n",go(st));
		}
		else{
			int p=read()+1;ll val=read();
			update(p,val);
		}
	}
}

int main(){
	input();
	calc_bk();
	calc_jumpout();
	ask();
	return 0;
}

林克卡特树做法：

int n;
ll a[maxn];
void input(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
}

struct Lct{
    /*awa*/
}lct;

void link_edge(){
	for(int i=1;i<=n;++i){
		int to=i+a[i];
		if(to>n) lct.link(i,n+1);
		else lct.link(i,i+a[i]);
		lct.makeroot(i);
		lct.t[i].val=1;//给每一个点赋一个1的权值，可以避免n+1
	}
}

int q;
void ask(){
	q=read();
	for(int i=1;i<=q;++i){
		int op=read();
		if(op==1){
			int st=read()+1;
			lct.split(st,n+1);
			printf("%lld\n",lct.t[n+1].sum);
		}
		else{
			int p=read()+1;ll val=read();
			if(p+a[p]<=n) lct.cut(p,p+a[p]);
			else lct.cut(p,n+1);
			if(p+val<=n) lct.link(p,p+val);
			else lct.link(p,n+1);
			a[p]=val;
		}
	}
}

int main(){
	input();
	link_edge();
	ask();
	return 0;
}

没了。

哦我有个sub入口你要不要