在线段树中

void pushdown(int u,int l,int r){
	int m=(l+r)>>1;
	mark(u*2,l,m,lza[u],2);
	mark(u*2,l,m,lzm[u],1);
	mark(u*2+1,m+1,r,lza[u],2);
	mark(u*2+1,m+1,r,lzm[u],1);
	lzm[u]=1;
	lza[u]=0;
}

是错的

void pushdown(int u,int l,int r){
	int m=(l+r)>>1;
	mark(u*2,l,m,lzm[u],1);
	mark(u*2,l,m,lza[u],2);
	mark(u*2+1,m+1,r,lzm[u],1);
	mark(u*2+1,m+1,r,lza[u],2);
	lza[u]=0;
	lzm[u]=1;
}

是对的

为什么???

完整AC code

题目

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+10;
#define int long long
int n,q,mod,x,y,k,a[N],opt;
int w[N],lzm[N],lza[N];
void pushup(int u){
	w[u]=(w[u*2]+w[u*2+1])%mod;
}
void build(int u,int l,int r){
	if(l==r){
		w[u]=a[l];
		return ;
	}
	lzm[u]=1;
	int m=(l+r)>>1;
	build(u*2,l,m);
	build(u*2+1,m+1,r);
	pushup(u);
}
bool in(int l,int r,int x,int y){
	return (x<=l)&&(y>=r);
}
bool out(int l,int r,int x,int y){
	return (x>r)||(y<l);
}
void mark(int u,int l,int r,int p,int op){
	if(op==1){
		(lzm[u]*=p)%=mod;
		(lza[u]*=p)%=mod;
		(w[u]*=p)%=mod;
	}
	else {
		(lza[u]+=p)%=mod;
		(w[u]+=(r-l+1)*p)%=mod;
	}
}
void pushdown(int u,int l,int r){
	int m=(l+r)>>1;
	mark(u*2,l,m,lzm[u],1);
	mark(u*2,l,m,lza[u],2);
	mark(u*2+1,m+1,r,lzm[u],1);
	mark(u*2+1,m+1,r,lza[u],2);
	lza[u]=0;
	lzm[u]=1;
}
int query(int u,int l,int r,int x,int y){
	if(in(l,r,x,y)){
		return w[u];
	}
	else if(!out(l,r,x,y)){
		int m=(l+r)>>1;
		pushdown(u,l,r);
		return (query(u*2,l,m,x,y)%mod+query(u*2+1,m+1,r,x,y)%mod)%mod;
	}
	else return 0;
}
void update(int u,int l,int r,int x,int y,int p,int op){
	if(in(l,r,x,y)){
		mark(u,l,r,p,op);
	}
	else if(!out(l,r,x,y)){
		int m=(l+r)>>1;
		pushdown(u,l,r);
		update(u*2,l,m,x,y,p,op);
		update(u*2+1,m+1,r,x,y,p,op);
		pushup(u);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		cin>>opt;
		if(opt==1){
			cin>>x>>y>>k;
			update(1,1,n,x,y,k,1);
		}
		else if(opt==2){
			cin>>x>>y>>k;
			update(1,1,n,x,y,k,2);
		}
		else {
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}