自动搬运

查看原文

来自洛谷，原作者为

	听取MLE声一片 如果我当时做的再多一点，结局会不会不同呢？

搬运于2025-08-24 22:58:46，当前版本为作者最后更新于2024-05-19 20:43:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

数据结构题解

以下假定 $n,m,V$ 同阶。

势能线段树。注意到若无二操作，有效一操作至多会进行 $O(\sqrt n)$ 次，也就是可以对每个位置暴力修改。对于线段树上每个区间记录区间最小值，若当前区间最小值不大于 $k$ 则对其子树递归修改。直到找到每个单点，暴力修改即可。

二操作单点修改总共只会更新至多 $O(n)$ 个数，给一操作的总修改数增加 $O(n\sqrt n)$ 次，时间复杂度是正确的。

区间和用单点修改线段树的写法即可。

注意要特判 $t=0$ 的情况。

一操作至多进行 $O(n\sqrt n)$ 次单点修改，总时间复杂度为 $O(n\sqrt n\log n)$，实际达不到上界。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#include<random>
#define int long long
using namespace std;
inline 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;
}
const int N=1e5+10;
int n,m,a[N],b[N];
struct Tree{
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define mid ((l+r)>>1)
	int sum[N<<2],minn[N<<2];
	inline void pushup(int p){
		sum[p]=sum[ls]+sum[rs];
		minn[p]=min(minn[ls],minn[rs]);
	}
	void build(int p,int l,int r){
		if(l==r){
			sum[p]=a[l]+b[l];
			minn[p]=a[l]*b[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(p);
	}
	void update(int L,int R,int p,int l,int r,int k,int t){
		if(minn[p]>k)return;
		if(l==r){
			a[l]+=t;
			b[l]+=t;
			sum[p]=a[l]+b[l];
			minn[p]=a[l]*b[l];
			return;
		}
		if(L<=mid)update(L,R,ls,l,mid,k,t);
		if(R>mid) update(L,R,rs,mid+1,r,k,t);
		pushup(p);
	}
	void modify(int pos,int p,int l,int r,int x,int y){
		if(l==r){
			a[pos]=x;
			b[pos]=y;
			sum[p]=a[l]+b[l];
			minn[p]=a[l]*b[l];
			return;
		}
		if(pos<=mid)modify(pos,ls,l,mid,x,y);
		if(pos>mid) modify(pos,rs,mid+1,r,x,y);
		pushup(p);
	}
	int query(int L,int R,int p,int l,int r){
		if(L<=l&&r<=R)
			return sum[p];
		int res=0;
		if(L<=mid)res+=query(L,R,ls,l,mid);
		if(R>mid) res+=query(L,R,rs,mid+1,r);
		return res;
	}
	#undef ls
	#undef rs
	#undef mid
}T;
signed main()
{
	//freopen("020.in","r",stdin);
	//freopen("020.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		b[i]=read();
	T.build(1,1,n);
	while(m--){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),k=read(),t=read();
			if(!t)continue;
			T.update(l,r,1,1,n,k,t);
		}
		if(opt==2){
			int pos=read(),x=read(),y=read();
			T.modify(pos,1,1,n,x,y);
		}
		if(opt==3){
			int l=read(),r=read();
			cout<<T.query(l,r,1,1,n)<<'\n';
		}
	}
	return 0;
}