玄关求助大佬QWQ
查看原帖
玄关求助大佬QWQ
1195678
wky2011楼主2025/1/23 18:36

献上丑陋的代码~~自我感觉函数写的没问题但样例都过不了

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 2000005
int n,a[N],sum[N<<2],mx[N<<2];//四倍空间;
bool tag[N<<2];
inline int ls(int x){
	return x<<1;
} 
inline int rs(int x){
	return x<<1|1;
}
inline void add(int x,int l,int r,int k){
	sum[x]+=k*(l-r+1);
	mx[x]+=k;
	tag[x]+=k;
}
inline void pushup(int x){//左二子+右二子 =自己
//通过儿子找自己 
	sum[x]=sum[ls(x)]+sum[rs(x)];
	mx[x]=max(mx[ls(x)],mx[rs(x)]);
}
inline void pushdown(int x,int l,int r){
	int m=(l+r)>>1;
	pushdown(x,l,r);
//	if(tag[x]!=0){
		add(ls(x),l,m,tag[x]);
		add(rs(x),m+1,r,tag[x]);
//	}
tag[x]=0;
}
inline void build(int x,int l,int r){
	if(l==r){
		sum[x]=mx[x]=a[l];
		return ;
	}
//	pushdown(x,l,r); 
	int m =(l+r)>>1;
	build(ls(x),l,m);
	build(rs(x),m+1,r);
	pushup(x);
}
inline int querySum(int x,int l,int r,int L,int R){
//查询区间
//x:当前节点编号  
//l,r:当前节点维护的区间
//L,R:询问的区间 
if(L<=l&&r<=R){
	return sum[x];
}
pushdown(x,l,r);
int m=(l+r)>>1;
int ret=0;
if(L<=m)ret+=querySum(ls(x),l,m,L,R);//甩给左儿子 
if(m<R)ret+= querySum(rs(x),m+1,r,L,R);//甩给右儿子
return ret;
}
inline  int queryMax(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return mx[x];
	}
	pushdown(x,l,r);
	int m=(l+r)>>1;
	int ret=-299999999999;
	if(L<=m)ret=max(ret,queryMax(ls(x),l,m,L,R));//甩给左儿子 
	if(m<R)ret=max(ret,queryMax(rs(x),m+1,r,L,R));//甩给右儿子
	return ret;
}
inline void qjj(int x,int l,int r,int L,int R,int k){//区间加 
	if(L<=l&&r<=R){
		return add(x,l,r,k);
	}
	pushdown(x,l,r);
	int m=(l+r)>>1;
	if(L<=m)qjj(ls(x),l,m,L,R,k);
	 if(m<R)qjj(rs(x),m+1,r,L,R,k);
	 pushup(x);
}
inline void posAdd(int x,int l,int r,int p,int k){
//单点修改
//x:当前节点编号  
//l,r:当前节点维护的区间
//L,R:询问的区间 
	sum[x]+=k;
	if(l==r)return ;
	pushdown(x,l,r);
	int m=(l+r)>>1;
	if(p<=m)posAdd(ls(x),l,m,p,k);
	else posAdd(rs(x), m + 1, r, p, k);
} 
signed main(){
	int m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	build(1,1,n);
	while(m--){
		char xx;
		cin>>xx;
		int x,y;
		cin>>x>>y;
		if(xx=='1'){
			int k;
			cin>>k;
			qjj(1,x,y,1,n,k);
		}
		else{
			cout<<querySum(1,x,y,1,n)<<'\n';
		}
	}
	return 0;
 }

~~

2025/1/23 18:36
加载中...