牛客题目线段树

主要是操作三，怎么计算

那么只需要维护区间和和区间平方和即可，1/2用逆元

多个标记注意标记之间有没有影响，mod其实很简单的，但是我标记没处理好一直wa,mod乱搞一下，我mod很丑

#include<iostream>
#include<algorithm>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=1e5+9;
ll a[N];
ll n,m,mod;
struct node{
	ll val,pfval,mul,add;
}seg[N<<2];
ll tl(ll x){
	return x<<1;
}
ll tr(ll x){
	return x<<1|1;
}
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res%mod;
}
ll inv(ll x){
    return qmi(x,mod-2)%mod;
}
void pushup(int id){
	seg[id].val=(seg[tl(id)].val%mod)+(seg[tr(id)].val%mod);
	seg[id].pfval=(seg[tl(id)].pfval%mod)+(seg[tr(id)].pfval%mod);
}
void build(int id,int l,int r){
	seg[id].mul=1;
    seg[id].add=0;
	if(l==r){
		seg[id].val=a[l]%mod;
		seg[id].pfval=a[l]*a[l]%mod;
	}else{
		int mid=(l+r)>>1;
		build(tl(id),l,mid);
		build(tr(id),mid+1,r);
		pushup(id);
	}
}
bool inrange(int L,int R,int l,int r){
	return L>=l && R<=r;
}
bool outofrange(int L,int R,int l,int r){
	return L>r || l>R;
}
void maketag(int id,int l,int r,ll v,int opt){
	if(opt==1){
        v%=mod;
		seg[id].val*=v;
        seg[id].val%=mod;
        seg[id].mul*=v;
        seg[id].mul%=mod;
        v=(v%mod)*v%mod;
		seg[id].pfval*=v;
        (seg[id].add*=v)%=mod;
        seg[id].pfval%=mod;
	}else{
        v%=mod;
		seg[id].pfval+=((v%mod)*v%mod)*(r-l+1)%mod+2*(v%mod)*(seg[id].val%mod);
        seg[id].pfval%=mod;
        seg[id].val+=(r-l+1)*(v%mod);  
        seg[id].val%=mod;
		seg[id].add+=v;
        seg[id].add%=mod;
	}
}
void pushdown(int id,int l,int r){
	int mid=(l+r)>>1;
    if(seg[id].mul!=1){
        maketag(tl(id),l,mid,seg[id].mul,1);
	    maketag(tr(id),mid+1,r,seg[id].mul,1);
    }
    if(seg[id].add){
        maketag(tl(id),l,mid,seg[id].add,2);
	    maketag(tr(id),mid+1,r,seg[id].add,2);
    }
	seg[id].mul=1;
	seg[id].add=0;
}
ll querysum(int id,int L,int R,int l,int r){
	if(inrange(L,R,l,r)){
		return seg[id].val%mod;
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		return querysum(tl(id),L,mid,l,r)%mod+querysum(tr(id),mid+1,R,l,r)%mod;
	}else{
		return 0;
	}
}
ll querypfsum(int id,int L,int R,int l,int r){
	if(inrange(L,R,l,r)){
		return seg[id].pfval%mod;
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		return querypfsum(tl(id),L,mid,l,r)%mod+querypfsum(tr(id),mid+1,R,l,r)%mod;
	}else{
		return 0;
	}
}
void modifymul(int id,int L,int R,int l,int r,ll v){
	if(inrange(L,R,l,r)){
		maketag(id,L,R,v,1);
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		modifymul(tl(id),L,mid,l,r,v);
		modifymul(tr(id),mid+1,R,l,r,v);
		pushup(id);
	}
}
void modifyadd(int id,int L,int R,int l,int r,ll v){
	if(inrange(L,R,l,r)){
		maketag(id,L,R,v,2);
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		modifyadd(tl(id),L,mid,l,r,v);
		modifyadd(tr(id),mid+1,R,l,r,v);
		pushup(id);
	}
}
void solve(){
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=mod;
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            int l,r,v;
            cin>>l>>r>>v;
            modifyadd(1,1,n,l,r,v);
        }else if(opt==2){
            int l,r,v;
            cin>>l>>r>>v;
            modifymul(1,1,n,l,r,v);
        }else{
            int l,r;
            cin>>l>>r;
            ll res1=querysum(1,1,n,l,r)%mod;
            res1=res1*res1%mod;
            ll res2=querypfsum(1,1,n,l,r)%mod;
            res2%=mod;
            ll ans=(((res1-res2)%mod+mod)%mod)*inv(2)%mod;
            cout<<ans%mod<<'\n';
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}