https://www.luogu.com.cn/problem/P3373
题意：给出n个数，m次操作，模q ， ai ， 三种操作：1、l , r , k 区间乘k ， 2 、 l , r , k , 区间加k ， 3 、l , r 询问区间和。
解法：线段树两个标记乘法标记mul和加法标记plu。pushdown下放加法有点特殊，需要自己身上的加法标记乘以父亲的乘法标记再加上
父亲的加法标记。
#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef long long ll ;
#define int ll
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
using namespace std;
const int N = 1e6+100;
const int maxn = 1e5+9;
int n , m , p ;
int a[maxn];
struct node{
int l , r , sum , mul , plu;
}tree[maxn<<2];
void pushup(int root){
tree[root].sum = (tree[root<<1].sum + tree[root<<1|1].sum) % p;
}
void pushdown(int root){
int k1 = tree[root].mul , k2 = tree[root].plu;
tree[root<<1].sum =(k1 * tree[root<<1].sum + k2*(tree[root<<1].r - tree[root<<1].l + 1))% p;
tree[root<<1|1].sum = (k1 * tree[root<<1|1].sum + k2*(tree[root<<1|1].r - tree[root<<1|1].l + 1))% p;
tree[root<<1].mul = tree[root<<1].mul * k1 % p ;
tree[root<<1|1].mul = tree[root<<1|1].mul * k1 % p ;
tree[root<<1].plu = (tree[root<<1].plu*k1 + k2) % p ;
tree[root<<1|1].plu = (tree[root<<1|1].plu*k1 + k2) % p ;
tree[root].mul =1 ;
tree[root].plu = 0;
}
void build(int l , int r , int root){
tree[root].l = l , tree[root].r = r , tree[root].mul = 1 , tree[root].plu = 0;
if(l == r){
tree[root].sum = a[l] % p ;
return ;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
pushup(root);
}
void update_mul(int l , int r , int root , int val){
if(tree[root].l >= l && tree[root].r <= r){
tree[root].sum = tree[root].sum * val % p;
tree[root].mul = tree[root].mul * val % p;
tree[root].plu = tree[root].plu * val % p;
return ;
}
pushdown(root);
int mid = (tree[root].l + tree[root].r) >> 1;
if(mid >= l) update_mul(l , r , root<<1 , val);
if(mid < r) update_mul(l , r , root<<1|1 , val);
pushup(root);
}
void update_plu(int l , int r , int root , int val){
if(tree[root].l >= l && tree[root].r <= r){
tree[root].sum = (tree[root].sum + (tree[root].r - tree[root].l + 1) * val) % p ;
tree[root].plu = (tree[root].plu + val) % p ;
return ;
}
pushdown(root);
int mid = (tree[root].l + tree[root].r) >> 1 ;
if(mid >= l) update_plu(l , r , root<<1 , val);
if(mid < r) update_plu(l , r , root<<1|1 , val);
pushup(root);
}
int query(int l , int r , int root){
int sum = 0 ;
if(tree[root].l >= l && tree[root].r <= r){
return tree[root].sum % p ;
}
pushdown(root);
int mid = (tree[root].l + tree[root].r) >> 1 ;
if(mid >= l) sum = (sum + query(l , r , root<<1)) % p;
if(mid < r) sum = (sum + query(l , r , root<<1|1)) % p;
return sum % p ;
}
void solve(){
scanf("%lld%lld%lld" , &n , &m , &p);
rep(i , 1 , n) scanf("%lld" , &a[i]);
build(1 , n , 1);
rep(i , 1 , m){
int t , l , r , val;
scanf("%lld%lld%lld" , &t , &l , &r);
if(t == 1){
scanf("%lld" , &val);
val %= p;
update_mul(l , r , 1 , val);
}else if(t == 2){
scanf("%lld" , &val);
val %= p ;
update_plu(l , r , 1 , val);
}
else{
cout << query(l , r , 1) << endl;
}
}
}
signed main()
{
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
//int t ;
//cin >> t ;
//while(t--){
solve();
//}
}