题意:维护三中操作,一是区间乘,二是区间加,三是询问区间和.
分析:在线段树的板子上增加了一个区间乘操作,但其实在洛咕还是模板题额.再开一个乘法的懒标记,初始化为1,每次遇到区间乘的操作,如果是整个区间都被包含的话,那么这个区间的乘法标记,加法标记和区间和都要更新.(pushdown)操作也是一样,三个东西都要更新.
总之就是区间加只影响区间加和区间和两个东西,区间乘影响区间乘,区间加和区间和三个东西.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
ll n,m,mod,a[N];
struct XD_Tree{ll l,r,add1,add2,sum;}t[N<<2];
inline void build(int p,int l,int r){
t[p].l=l;t[p].r=r;t[p].add1=1;
if(l==r){t[p].sum=a[l];t[p].add1=1;return;}
int mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
}
inline void pushdown(int p){
if(t[p].add1!=1){
//这里如果写的大于1,那么T150分,T230分,猜测数据应该是有乘负数或者乘0的
t[p<<1].add1=(t[p<<1].add1*t[p].add1)%mod;
t[p<<1|1].add1=(t[p<<1|1].add1*t[p].add1)%mod;
t[p<<1].add2=(t[p<<1].add2*t[p].add1)%mod;
t[p<<1|1].add2=(t[p<<1|1].add2*t[p].add1)%mod;
t[p<<1].sum=(t[p<<1].sum*t[p].add1)%mod;
t[p<<1|1].sum=(t[p<<1|1].sum*t[p].add1)%mod;
t[p].add1=1;
}
if(t[p].add2){
t[p<<1].add2=(t[p<<1].add2+t[p].add2)%mod;
t[p<<1|1].add2=(t[p<<1|1].add2+t[p].add2)%mod;
t[p<<1].sum=(t[p<<1].sum+1ll*t[p].add2*(t[p<<1].r-t[p<<1].l+1)%mod)%mod;
t[p<<1|1].sum=(t[p<<1|1].sum+1ll*t[p].add2*(t[p<<1|1].r-t[p<<1|1].l+1)%mod)%mod;
t[p].add2=0;
}
}
inline void change1(int p,int ql,int qr,ll val){
int l=t[p].l,r=t[p].r;
if(ql<=l&&qr>=r){
t[p].add1=(t[p].add1*val)%mod;
t[p].add2=(t[p].add2*val)%mod;
t[p].sum=(t[p].sum*val)%mod;
return;
}
pushdown(p);int mid=(l+r)>>1;
if(ql<=mid)change1(p<<1,ql,qr,val);
if(qr>mid)change1(p<<1|1,ql,qr,val);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
}
inline void change2(int p,int ql,int qr,ll val){
int l=t[p].l,r=t[p].r;
if(ql<=l&&qr>=r){
t[p].add2=(t[p].add2+val)%mod;
t[p].sum=(t[p].sum+1ll*(r-l+1)*val%mod)%mod;
return;
}
pushdown(p);int mid=(l+r)>>1;
if(ql<=mid)change2(p<<1,ql,qr,val);
if(qr>mid)change2(p<<1|1,ql,qr,val);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
}
inline ll query(int p,int ql,int qr){
int l=t[p].l,r=t[p].r;
if(ql<=l&&qr>=r)return t[p].sum;
pushdown(p);int mid=(l+r)>>1;ll cnt=0;
if(ql<=mid)cnt=(cnt+query(p<<1,ql,qr))%mod;
if(qr>mid)cnt=(cnt+query(p<<1|1,ql,qr))%mod;
return cnt;
}
int main(){
n=read();mod=read();
for(int i=1;i<=n;++i)a[i]=read();
build(1,1,n);m=read();
while(m--){
ll opt=read(),l=read(),r=read();
if(opt==1){
ll val=read();
change1(1,l,r,val);
}
else if(opt==2){
ll val=read();
change2(1,l,r,val);
}
else if(opt==3){
printf("%lld
",query(1,l,r)%mod);
}
}
return 0;
}