线段树2求助
查看原帖
线段树2求助
680357
Pink__ink楼主2022/12/16 18:51

一直是70分,很烦,求巨佬们帮忙调一下

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define int long long
int n,q,mod,a[MAXN];
struct node{
	int l,r,sum,add_lazy,mul_lazy;
}t[MAXN<<2];
inline void push_up(int pos){
	(t[pos].sum=t[pos*2].sum+t[pos*2+1].sum)%=mod;
}
inline void push_down(int pos){
	if(t[pos].add_lazy||t[pos].mul_lazy){
		(t[pos*2].mul_lazy*=t[pos].mul_lazy)%=mod;
		(t[pos*2].add_lazy*=t[pos].mul_lazy)%=mod;
		(t[pos*2].add_lazy+=t[pos].add_lazy)%=mod;
		(t[pos*2].sum*=t[pos].mul_lazy)%=mod;
		(t[pos*2].sum+=(t[pos].add_lazy*(t[pos*2].r-t[pos*2].l+1)))%=mod;
		(t[pos*2+1].mul_lazy*=t[pos].mul_lazy)%=mod;
		(t[pos*2+1].add_lazy*=t[pos].mul_lazy)%=mod;
		(t[pos*2+1].add_lazy+=t[pos].add_lazy)%=mod;
		(t[pos*2+1].sum*=t[pos].mul_lazy)%=mod;
		(t[pos*2+1].sum+=(t[pos].add_lazy*(t[pos*2+1].r-t[pos*2+1].l+1)))%=mod;
		t[pos].mul_lazy=1,t[pos].add_lazy=0;
	}
}
inline void build(int pos,int l,int r){
	t[pos].l=l,t[pos].r=r,t[pos].mul_lazy=1;
	if(l==r){
		t[pos].sum=a[l];
		return;
	}
	int mid=l+r>>1;
	build(pos*2,l,mid),build(pos*2+1,mid+1,r);
	push_up(pos);
}
inline void update(int pos,int l,int r,int L,int R,int x,int d){
	if(L<=l&&r<=R){
		if(x==2) (t[pos].sum+=d*(t[pos].r-t[pos].l+1))%=mod,(t[pos].add_lazy+=d)%=mod;
		else (t[pos].sum*=d)%=mod,(t[pos].mul_lazy*=d)%=mod,(t[pos].add_lazy*=d)%=mod;
		return;
	}
	push_down(pos);
	int mid=l+r>>1;
	if(L<=mid) update(pos*2,l,mid,L,R,x,d);
	if(mid<R) update(pos*2+1,mid+1,r,L,R,x,d);
	push_up(pos);
}
inline int query(int pos,int l,int r){
	if(l<=t[pos].l&&t[pos].r<=r) return t[pos].sum%mod;
	push_down(pos);
	int mid=t[pos].l+t[pos].r>>1,res=0;
	if(l<=mid) (res+=query(pos*2,l,r))%=mod;
	if(mid<r) (res+=query(pos*2+1,l,r))%=mod;
	return res%mod;
}
signed main(){
	scanf("%lld%lld%lld",&n,&q,&mod);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while(q--){
		int op,l,r;
		scanf("%lld",&op);
		if(op==1||op==2){
			int l,r,d;
			scanf("%lld%lld%lld",&l,&r,&d);
			update(1,1,n,l,r,op,d);
		} 
		else{
			int l,r;
			scanf("%lld%lld",&l,&r);
			printf("%lld\n",query(1,l,r)%mod);
		}
	}
	return 0;
}
```cpp
2022/12/16 18:51
加载中...