题解 P3373 【【模板】线段树 2】
//蛤蛤蛤蛤蛤蛤，各种常数优化懒标优化史上最快！！!（众人：不对啊还有指针呢？我：。。。咱打个题解不容易能不能忽略一下细节。。。而且搞了一个多月。。。）
//搞了1个多月，终于搞完了呜呜呜~~~
//要注意乘法分配律，因为在懒惰标记中乘法会影响加法，而加法并不会影响乘法（假装严肃。。。）
//最最重要的一点（我搞了一个多月就是因为它呜呜呜~），无论执行任何操作（建树除外），执行之前一定一定千万千万mustmust把当前节点的懒惰标记下放，因为查询时是从上向下寻找懒惰标记的，如果在每次查询不执行下放操作加法乘法先后次序就出事了（我就是错在这里的。。。呜呜呜~）
附上我V587的代码（蛤蛤蛤蛤蛤蛤）
pra\
gma GCC optimize("O3")//这是传说中的O3优化（小小吐槽一下洛谷，#pragma关键字居然不让用，弄得我还得打个“\"，还得打个换行。。。）
#include<stdio.h>
using namespace std;
int n,m;
unsigned long long p,vv[1000020],ll[2000050],rr[2000050],mm[2000050],k,jia[2000050],cheng[2000050];
char ch;
inline void iin(int &kk){
ch=getchar();
for(;ch!='-'&&(ch<48||ch>57);){
ch=getchar();
}
if(ch=='-'){
ch=getchar();
for(;ch>=48&&ch<=57;){
kk=(kk<<1)+(kk<<3)+ch-48;
ch=getchar();
}
kk=-kk;
return;
}
for(;ch>=48&&ch<=57;){
kk=(kk<<1)+(kk<<3)+ch-48;
ch=getchar();
}
}
inline void lin(unsigned long long &kk){
ch=getchar();
for(;ch!='-'&&(ch<48||ch>57);){
ch=getchar();
}
if(ch=='-'){
ch=getchar();
for(;ch>=48&&ch<=57;){
kk=(kk<<1)+(kk<<3)+ch-48;
ch=getchar();
}
kk=-kk;
return;
}
for(;ch>=48&&ch<=57;){
kk=(kk<<1)+(kk<<3)+ch-48;
ch=getchar();
}
}
unsigned long long build(int l,int r,int id){
cheng[id]=1;
if(l==r){
lin(vv[id]);//建树时的神奇优化，节约空间蛤蛤蛤蛤蛤蛤
vv[id]%=p;
ll[id]=rr[id]=mm[id]=l;
return vv[id];
}
ll[id]=l;
rr[id]=r;
int mid=(l+r)>>1;
mm[id]=mid;
return vv[id]=(build(l,mid,id<<1)+build(mid+1,r,(id<<1)|1))%p;
}
inline void low(int id){
vv[id]=(cheng[id]*vv[id]%p+jia[id]*(rr[id]-ll[id]+1)%p)%p;
int lid=id<<1,rid=(id<<1)|1;
if(cheng[id]!=1){
cheng[lid]*=cheng[id],cheng[lid]%=p;
cheng[rid]*=cheng[id],cheng[rid]%=p;
jia[lid]*=cheng[id],jia[lid]%=p;
jia[rid]*=cheng[id],jia[rid]%=p;
cheng[id]=1;
}
if(jia[id]){
jia[lid]+=jia[id],jia[lid]%=p;
jia[rid]+=jia[id],jia[rid]%=p;
jia[id]=0;
}}//神奇的下放操作 unsigned long long chengg(int l,int r,unsigned long long change,int id){
low(id);
// printf("cheng%d %d %d %d\n",l,r,id,mm[id]);
int mmm=mm[id];
if(l==ll[id]&&r==rr[id]){
unsigned long long uu=cheng[id];
cheng[id]=(cheng[id]*change)%p;
unsigned long long u=jia[id];
jia[id]=(jia[id]*change)%p;
return ((cheng[id]-uu)*vv[id]%p+(jia[id]-u)*(r-l+1)%p)%p;
}
if(mmm>=r){
unsigned long long u=chengg(l,r,change,id<<1)%p;
u%=p;
vv[id]=(vv[id]+u)%p;
return u;
}
if(mmm<l){
unsigned long long u=chengg(l,r,change,(id<<1)|1)%p;
u%=p;
vv[id]=(vv[id]+u)%p;
return u;
}
unsigned long long u=(chengg(l,mmm,change,id<<1)+chengg(mmm+1,r,change,(id<<1)|1))%p;
vv[id]=(vv[id]+u)%p;
return u;
}
void jiaa(int l,int r,unsigned long long change,int id){
low(id);
int lll=ll[id],rrr=rr[id];
if(l==lll&&r==rrr){
jia[id]=(jia[id]+change)%p;
return;
}
int mmm=mm[id];
vv[id]=(vv[id]%p+(r-l+1)*change%p)%p;
// printf("jia%d %d %d %d ",l,r,id,mm[id]);
// printf("%lld\n",vv[id]);
if(mmm>=r){
jiaa(l,r,change,id<<1);
return;
}
if(mmm<l){
jiaa(l,r,change,(id<<1)|1);
return;
}
jiaa(l,mmm,change,id<<1);
jiaa(mmm+1,r,change,(id<<1)|1);
}
unsigned long long out(int l,int r,int id){
// printf("out%d %d %d\n",l,r,id);
low(id);
// printf("a%lld ",cheng[id]);
// printf("s%lld\n",jia[id]);
// printf("%d %d %d %d\n",l,r,id,vv[id]);
if(l==ll[id]&&r==rr[id]){
return vv[id];
}
int mid=mm[id],lid=id<<1,rid=(id<<1)|1;;
if(mid>=r){
return out(l,r,lid);
}
if(mid<l){
return out(l,r,rid);
}
return (out(l,mid,lid)+out(mid+1,r,rid))%p;
}
int main(){
iin(n),iin(m),lin(p);
build(1,n,1);
int num=0,x=0,y=0;
for(int i=0;i<m;i++){
iin(num),iin(x),iin(y);
if(num>>1){
if(num&1){
printf("%llu\n",out(x,y,1)%p);
}
else{
lin(k);
jiaa(x,y,k%p,1);
k=0;
}
}
else{
lin(k);
chengg(x,y,k%p,1);
k=0;
}
num=x=y=0;
}
for(int i=1;i<=9;i++){
// printf("%lld ",vv[i]*cheng[i]+jia[i]*(rr[i]-ll[i]+1));
}
return 0;
}