自动搬运

查看原文

来自洛谷，原作者为

	xu_zhihao 现役初二OIer似乎要退役了||不拿蓝勾不改签

搬运于2025-08-24 23:00:12，当前版本为作者最后更新于2024-09-28 17:59:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

• 只能说这题太模板了。

题目描述

• 什么？ $2^k$ 区间问题？那绝对得用 ST 表了。但很烦人的是这里有一个单点修改操作，若朴素 ST 表 $O(1)$ 查询，$O(n \log n)$ 修改，这复杂度是绝对过不了的。考虑均摊复杂度。

• 均摊复杂度可以使用根号分治。只用维护 $2^k\le \sqrt{N}$。区间查询使用递归求出未求部分，复杂度为 $O(\sqrt{N})$；单点修改复杂度为 $O(\sqrt{N})$。复杂度变为 $O(Q \sqrt{N})$。

upd 复杂度若有误请与我联系。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int st[200010][25];
int p[200010];
int s,t;
void Init(){
	for(int i=1;i<=n;i++){
		st[i][0]=p[i];
	}
	for(int j=1;j<=t;j++){
		for(int i=1;i<=n;i++)if(i+(1<<j)-1<=n){
			st[i][j]=abs(st[i][j-1]-st[i+(1<<(j-1))][j-1]);
		}
	}
	return;
}
int check(int l,int k){
	if(k<=t){
		return st[l][k];
	}
	int ans=abs(check(l,k-1)-check(l+(1<<(k-1)),k-1));
	return ans;
}
int Find(int l,int k){
	if(k<=t){
		int ans=st[l][k];
		return ans;
	}
	int ans=check(l,k);
	return ans;
}
void Work(int id,int r){
	st[id][0]=r;
	for(int j=1;j<=t;j++){
		int w=max(id-(1<<j)+1,1);
		for(int i=w;i<=id;i++)if(i+(1<<j)-1<=n){
			st[i][j]=abs(st[i][j-1]-st[i+(1<<(j-1))][j-1]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
	}
	s=sqrt(n);
    t=log2(s);
	Init();
	while(q--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int i,r;
			scanf("%d%d",&i,&r);
			Work(i,r);
		}
		else{
			int l,k;
			scanf("%d%d",&l,&k);
			int ans=Find(l,k);
			printf("%d\n",ans);
		}
	}
	return 0;
}