传送门
【题目分析】
RT，就是线段树的模板，支持区间乘、区间加、区间求和。
很有意思的一点是两个标记的下传，解决了就行了。
然后这道题，作为AHOI，竟然是个裸的模板！（可能年份久远的原因吧。。。）两个一毛一样嘛！
【代码~】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=5e5+10;
struct Tree{
LL l,r;
LL sum,add,mul;
}tr[MAXN<<2];
LL n,q,mod;
LL a[MAXN];
LL Read()
{
LL i=0,f=1;
char c;
for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void sc(LL x)
{
if(x>=10)
sc(x/10);
putchar(x%10+48);
}
void push_up(LL root)
{
tr[root].sum=(tr[root<<1].sum+tr[root<<1|1].sum)%mod;
}
void push_down(LL root)
{
if(tr[root].mul!=1||tr[root].add)
{
LL mid=tr[root].l+tr[root].r>>1;
tr[root<<1].sum=(tr[root<<1].sum*tr[root].mul+tr[root].add*(mid-tr[root].l+1))%mod;
tr[root<<1|1].sum=(tr[root<<1|1].sum*tr[root].mul+tr[root].add*(tr[root].r-mid))%mod;
tr[root<<1].add=(tr[root<<1].add*tr[root].mul+tr[root].add)%mod;
tr[root<<1|1].add=(tr[root<<1|1].add*tr[root].mul+tr[root].add)%mod;
tr[root<<1].mul=(tr[root<<1].mul*tr[root].mul)%mod;
tr[root<<1|1].mul=(tr[root<<1|1].mul*tr[root].mul)%mod;
tr[root].add=0;
tr[root].mul=1;
}
}
void build(LL root,LL l,LL r)
{
tr[root].mul=1;
tr[root].l=l;
tr[root].r=r;
if(l==r)
{
tr[root].sum=a[l];
return ;
}
LL mid=l+r>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
push_up(root);
}
void update1(LL root,LL l,LL r,LL L,LL R,LL key)
{
push_down(root);
if(r<L||l>R)
return ;
if(L<=l&&r<=R)
{
tr[root].add=(tr[root].add+key)%mod;
tr[root].sum=(tr[root].sum+key*(r-l+1))%mod;
return ;
}
LL mid=l+r>>1;
if(R<=mid)
update1(root<<1,l,mid,L,R,key);
else
{
if(L>mid)
update1(root<<1|1,mid+1,r,L,R,key);
else
update1(root<<1,l,mid,L,mid,key),update1(root<<1|1,mid+1,r,mid+1,R,key);
}
push_up(root);
}
void update2(LL root,LL l,LL r,LL L,LL R,LL key)
{
push_down(root);
if(r<L||l>R)
return ;
if(L<=l&&r<=R)
{
tr[root].mul=(tr[root].mul*key)%mod;
tr[root].sum=(tr[root].sum*key)%mod;
return ;
}
LL mid=l+r>>1;
if(R<=mid)
update2(root<<1,l,mid,L,R,key);
else
{
if(L>mid)
update2(root<<1|1,mid+1,r,L,R,key);
else
update2(root<<1,l,mid,L,mid,key),update2(root<<1|1,mid+1,r,mid+1,R,key);
}
push_up(root);
}
LL query(LL root,LL l,LL r,LL L,LL R)
{
push_down(root);
if(l>R||r<L)
return 0;
if(L<=l&&r<=R)
return tr[root].sum;
LL mid=l+r>>1;
if(R<=mid)
return query(root<<1,l,mid,L,R);
else
{
if(L>mid)
return query(root<<1|1,mid+1,r,L,R);
else
return query(root<<1,l,mid,L,mid)+query(root<<1|1,mid+1,r,mid+1,R);
}
}
int main()
{
n=Read(),mod=Read();
for(LL i=1;i<=n;++i)
a[i]=Read();
build(1,1,n);
q=Read();
while(q--)
{
LL cz=Read(),l=Read(),r=Read();
if(cz==1)
{
LL val=Read();
update2(1,1,n,l,r,val);
}
else
{
if(cz==2)
{
LL val=Read();
update1(1,1,n,l,r,val);
}
else
sc(query(1,1,n,l,r)%mod),puts("");
}
}
return 0;
}
