10pts WA求条
查看原帖
10pts WA求条
1272418
Unblocked_user楼主2024/12/14 11:10

已经用了各种方法了,从昨天晚上弄到现在都没整出来。

#include<bits/stdc++.h>
#define lid id<<1	//lid表示左儿子的编号 
#define rid id<<1|1		//rid表示右儿子二点编号 
#define int long long
using namespace std;
const int N=4e5+5,M=1e5+5;	//线段树开四倍内存 
int n,m,a[M];
int op,x,y,k;
struct qweqweqwe{	//线段树 
	int l,r;	//区间 
	int sum;	//区间累加和 
	int lazy;	//lazy标记 
}t[N];
void mt(int l,int r,int id){	//建树,确认没问题 
	t[id].l=l,t[id].r=r;
	if(l==r){
		t[id].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	mt(l,mid,lid);
	mt(mid+1,r,rid);
	t[id].sum=t[lid].sum+t[rid].sum;
}
int ask(int l,int r,int id){	//区间查询。l表示当前区间的左边,r表示当前区间的右边,id表示当前区间的编号 
	if(x<=l&&r<=y){		//如果当前区间被查询区间全包含 
		return t[id].sum;	//直接放回当前区间累加值
	}
	int mid=(l+r)>>1,res=0;		//中间点 
	if(t[id].lazy){		//懒标记下放 
		t[lid].lazy+=t[id].lazy;
		t[rid].lazy+=t[id].lazy;
		t[lid].sum+=(t[lid].r-t[lid].l+1)*t[lid].lazy;
		t[rid].sum+=(t[rid].r-t[rid].l+1)*t[rid].lazy;
		t[id].lazy=0;
	}
	if(x<=mid)res+=ask(l,mid,lid);		//向左查询 
	if(y>mid)res+=ask(mid+1,r,rid);		//向右查询 
	return res;		//返回查询到的结果 
}
void change(int l,int r,int id){	//区间修改,参数含义与 区间查询 一致 
	if(x<=l&&r<=y){		//如果当前区间被查询区间真包含 
		t[id].lazy+=k;	//添加懒标记 
		t[id].sum+=(r-l+1)*k;	//更新当前区间累加值 
		return;
	}
	int mid=(l+r)>>1;
	if(t[id].lazy){		//懒标记下放 
		t[lid].lazy+=t[id].lazy;
		t[rid].lazy+=t[id].lazy;
		t[lid].sum+=(t[lid].r-t[lid].l+1)*t[lid].lazy;
		t[rid].sum+=(t[rid].r-t[rid].l+1)*t[rid].lazy;
		t[id].lazy=0;
	}
	if(x<=mid)change(l,mid,lid);	//向左修改 
	if(y>mid)change(mid+1,r,rid);	//向右修改 
	t[id].sum=t[lid].sum+t[rid].sum;	//更新当前区间累加值 
}
signed main(){		//主函数,确定没问题 
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	mt(1,n,1);
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			change(1,n,1);
		}
		else{
			cin>>x>>y;
			cout<<ask(1,n,1)<<endl;
		}
	}
	return 0;
}
2024/12/14 11:10
加载中...