题解 P3373 【【模板】线段树 2】
考虑对于x,如果先乘k1再加k2,k2对k1无影响。如果先加k1,再乘k2,（x+k1）*k2等价于(x*k2)+(k1*k2)，所以第二步的乘会对第一步的加产生影响。为了模拟出这个影响，我们在区间乘的时候应该把区间加的lazy数组也乘上相应的数。
（代码中付了调试代码便于理解lazy）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const ll maxn = 1e6;
ll n,m,p;
ll tree[maxn*4],lazy1[maxn],lazy2[maxn];
inline ll read();
void pushdown1(ll,ll,ll);
void pushdown2(ll,ll,ll);
void build(ll node,ll l,ll r)
{
if(l == r) {
tree[node] = read();
return;
}
ll mid = (l + r) >> 1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node] = (tree[node<<1] + tree[node<<1|1])%p;
}
void pushdown1(ll node,ll l,ll r)
{
if(lazy1[node] == 1) return;
ll mid = (l + r) >> 1;
lazy1[node<<1] = (lazy1[node<<1]*lazy1[node])%p;
lazy1[node<<1|1] = (lazy1[node<<1|1]*lazy1[node])%p;
lazy2[node<<1] = (lazy2[node<<1]*lazy1[node])%p;
lazy2[node<<1|1] = (lazy2[node<<1|1]*lazy1[node])%p;
tree[node<<1] = (tree[node<<1]*lazy1[node])%p;
tree[node<<1|1] = (tree[node<<1|1]*lazy1[node])%p;
lazy1[node] = 1;//一定要重置
}
void pushdown2(ll node,ll l,ll r)
{
if(lazy2[node] == 0) return;
ll mid = (l + r) >> 1;
lazy2[node<<1] = (lazy2[node<<1] + lazy2[node])%p;
lazy2[node<<1|1] = (lazy2[node<<1|1] + lazy2[node])%p;
tree[node<<1] = (tree[node<<1] + (mid - l + 1)*lazy2[node]%p)%p;
tree[node<<1|1] = (tree[node<<1|1] + (r - mid)*lazy2[node]%p)%p;
lazy2[node] = 0;//一定要重置
}
void update1(ll node,ll l,ll r,ll x,ll y,ll k)
{
if(x > r || l > y) return;
if(x <= l && r <= y) {
pushdown1(node,l,r);
pushdown2(node,l,r);
lazy1[node] = (lazy1[node]*k)%p;
tree[node] = (tree[node]*k)%p;
return;
}
pushdown1(node,l,r);
pushdown2(node,l,r);
ll mid = (l + r) >> 1;
update1(node<<1,l,mid,x,y,k);
update1(node<<1|1,mid+1,r,x,y,k);
tree[node] = (tree[node<<1] + tree[node<<1|1])%p;
}
void update2(ll node,ll l,ll r,ll x,ll y,ll k)
{
if(x > r || l > y) return;
if(x <= l && r <= y) {
pushdown1(node,l,r);
pushdown2(node,l,r);
lazy2[node] = (lazy2[node] + k)%p;
tree[node] = (tree[node] + (r - l + 1)*k%p)%p;
return;
}
pushdown1(node,l,r);
pushdown2(node,l,r);
ll mid = (l + r) >> 1;
update2(node<<1,l,mid,x,y,k);
update2(node<<1|1,mid+1,r,x,y,k);
tree[node] = (tree[node<<1] + tree[node<<1|1])%p;
}
ll Query(ll node,ll l,ll r,ll x,ll y)
{
if(x > r || l > y) return 0;
if(x <= l && r <= y) return tree[node];
ll mid = (l + r) >> 1;
pushdown1(node,l,r);
pushdown2(node,l,r);
return (Query(node<<1,l,mid,x,y) + Query(node<<1|1,mid+1,r,x,y))%p;
}
int main()
{
n = read();m = read();p = read();
for(ll i=0;i<maxn;i++) lazy1[i] = 1;
build(1,1,n);
// cout<<" "<<tree[8]<<" "<<tree[9]<<" "<<tree[5]<<" "<<tree[6]<<" "<<tree[7]<<endl;
ll p,x,y,k;
while(m-- && scanf("%lld",&p)) {
if(p == 1) {
x = read();y = read();k = read();
update1(1,1,n,x,y,k);
/* cout<<"lazy1:"<<" ";
for(int i=1;i<=9;i++) cout<<lazy1[i]<<" ";
cout<<endl;
cout<<"lazy2:"<<" ";
for(int i=1;i<=9;i++) cout<<lazy2[i]<<" ";
cout<<endl;
cout<<"tree:"<<" "<<tree[8]<<" "<<tree[9]<<" "<<tree[5]<<" "<<tree[6]<<" "<<tree[7]<<endl;*/
}
else if(p == 2) {
x = read();y = read();k = read();
update2(1,1,n,x,y,k);
/* cout<<"lazy1:"<<" ";
for(int i=1;i<=9;i++) cout<<lazy1[i]<<" ";
cout<<endl;
cout<<"lazy2:"<<" ";
for(int i=1;i<=9;i++) cout<<lazy2[i]<<" ";
cout<<endl;
cout<<"tree:"<<" "<<tree[8]<<" "<<tree[9]<<" "<<tree[5]<<" "<<tree[6]<<" "<<tree[7]<<endl;*/
}
else {
x = read();y = read();
printf("%lld\n",Query(1,1,n,x,y));
/* cout<<"lazy1:"<<" ";
for(int i=1;i<=9;i++) cout<<lazy1[i]<<" ";
cout<<endl;
cout<<"lazy2:"<<" ";
for(int i=1;i<=9;i++) cout<<lazy2[i]<<" ";
cout<<endl;
cout<<"tree:"<<" "<<tree[8]<<" "<<tree[9]<<" "<<tree[5]<<" "<<tree[6]<<" "<<tree[7]<<endl;*/
}
}
return 0;
}
inline ll read()
{
ll w=1,x=0;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;
ch = getchar();
}
while(ch <= '9' && ch >= '0') {
x = (x<<1) + (x<<3) + ch - '0';
ch = getchar();
}
return x*w;
}