自动搬运

查看原文

来自洛谷，原作者为

	ADay Overrated.

搬运于2025-08-24 22:36:32，当前版本为作者最后更新于2023-09-08 11:16:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

更逊的阅读体验

不知道为什么这道题还没有题解。

Solution

对于操作 $1$，由于 $K\le 10$，直接暴力单点修改即可。
而操作 $2$ 的询问，不难发现，最后结果的呈现形式是

$$1\times A_l+2\times A_{l+1}+3\times A_{l+2}+\ldots+3\times A_{r-2}+2\times A_{r-1}+1\times A_r $$

其中中间可能有一段系数均为 $m$ 的项。那么为了维护这样的形式，我们不仅要维护 $\sum A_i$，还要维护 $\sum i\times A_i$，这样 $1\times A_l+2\times A_{l+1}+3\times A_{l+2}+\ldots$ 就可以变为 $\sum\limits_{i=l}^{l+m-1}i\times A_i -(l-1)\times\sum\limits_{i=l}^{l+m-1}A_i$ 而直接计算了。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int n,K,Q,t[11];
ll a[N],sum[N<<2],isum[N<<2];
void pushup(int u){sum[u]=sum[u<<1]+sum[u<<1|1],isum[u]=isum[u<<1]+isum[u<<1|1];}
void build(int u,int l,int r){
	if(l==r)return sum[u]=a[l],isum[u]=1ll*l*a[l],void();
	int mid=(l+r)/2;
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
	pushup(u);
}
void upd(int p,ll k,int u=1,int l=1,int r=n){
	if(l==r)return sum[u]=k,isum[u]=1ll*l*k,void();
	int mid=(l+r)/2;
	p<=mid?upd(p,k,u<<1,l,mid):upd(p,k,u<<1|1,mid+1,r);
	pushup(u);
}
ll ask(ll *S,int p,int q,int u=1,int l=1,int r=n){
	if(p>q)return 0;
	if(p<=l&&r<=q)return S[u];
	int mid=(l+r)/2;ll res=0;
	if(p<=mid)res+=ask(S,p,q,u<<1,l,mid);
	if(q>mid)res+=ask(S,p,q,u<<1|1,mid+1,r);
	return res;
}
int main(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	build(1,1,n);
	scanf("%d",&Q);
	for(int T=1,o;T<=Q;T++){
		scanf("%d",&o);
		if(o==1){
			for(int i=1;i<=K;i++)scanf("%d",t+i);
			ll at1=a[t[1]];
			for(int i=1;i<K;i++)upd(t[i],a[t[i]]=a[t[i+1]]);
			upd(t[K],a[t[K]]=at1);
		}else{
			ll l,r,m;
			scanf("%lld%lld%lld",&l,&r,&m);
			int len=r-l+1;ll res=0;
			if(len<m){puts("0");continue;}
			else if(len==1){printf("%lld\n",ask(sum,l,r));continue;}
			res=m*ask(sum,l,r);
			res+=ask(isum,l,l+m-1)-(l+m-1)*ask(sum,l,l+m-1);
			res+=(r-m+1)*ask(sum,r-m+1,r)-ask(isum,r-m+1,r);
			printf("%lld\n",res);
		}
	}
	return 0;
}