题解 P3373 【【模板】线段树 2】

· · 题解

这道题一眼看上去很简单，就是多了个区间乘和模的操作，结果写了半小时，调了2个小时才调出来……最主要的问题就是区间乘标记和区间加标记之间的关系和相互影响（刚开始没注意，一直WA）。对于每次下放标记，不难发现加标记对乘标记无影响，而乘标记会影响加标记，应该先下放乘标记，同时把加标记乘上乘标记。注意加标记每次下放后返回0，而乘标记返回1（返回0会错的很惨，一直为0）。然后对于每次操作，一定要注意模，否则很容易爆。还有就是把空间开够，不然会RE。其他的就和普通线段树模板一样。

以下为C++AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;

}//听说不写读入优化会TLE

ll n,m,p;
struct tree
{
    ll l,r,sum,x,y;//x为加标记，y为乘标记 
}tr[800100];
ll a[200100];
void build(ll id,ll l,ll r)
{
    tr[id].l=l,tr[id].r=r;
    tr[id].x=0,tr[id].y=1;
    if(tr[id].l==tr[id].r)
    {
        tr[id].sum=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    tr[id].sum=(tr[lid].sum+tr[rid].sum)%p;
    return ;
}
inline void pushdownx(ll id)//下放加标记 
{
    if(tr[id].x==0) return;
    tr[lid].x=(tr[lid].x+tr[id].x)%p;
    tr[rid].x=(tr[rid].x+tr[id].x)%p;
    tr[lid].sum=(tr[lid].sum+(tr[lid].r-tr[lid].l+1)*tr[id].x%p)%p;
    tr[rid].sum=(tr[rid].sum+(tr[rid].r-tr[rid].l+1)*tr[id].x%p)%p;
    tr[id].x=0;
    return;
}
inline void pushdowny(ll id)//下放乘标记 
{
    if(tr[id].y==1) return;
    tr[lid].y=(tr[lid].y*tr[id].y)%p;
    tr[rid].y=(tr[rid].y*tr[id].y)%p;
    tr[lid].x=(tr[lid].x*tr[id].y)%p;//加标记也要乘 
    tr[rid].x=(tr[rid].x*tr[id].y)%p;//加标记也要乘
    tr[lid].sum=tr[lid].sum*tr[id].y%p;
    tr[rid].sum=tr[rid].sum*tr[id].y%p;
    tr[id].y=1;
    return;
}
void updatex(ll id,ll l,ll r,ll val)//区间加 
{
    if(tr[id].l>r||tr[id].r<l) return;
    if(tr[id].l>=l&&tr[id].r<=r)
    {
        pushdowny(id);
        pushdownx(id);//先下放乘标记，再下放加标记，下同 
        tr[id].x=(tr[id].x+val)%p;
        tr[id].sum=(tr[id].sum+(tr[id].r-tr[id].l+1)*val%p)%p;
        return;
    }    
    pushdowny(id);
    pushdownx(id);
    updatex(lid,l,r,val);
    updatex(rid,l,r,val);
    tr[id].sum=(tr[lid].sum+tr[rid].sum)%p;
    return;
}
void updatey(ll id,ll l,ll r,ll val)//区间乘 
{
    if(tr[id].l>r||tr[id].r<l) return;
    if(tr[id].l>=l&&tr[id].r<=r)
    {
        pushdowny(id);
        pushdownx(id);
        tr[id].y=tr[id].y*val%p;
        tr[id].sum=tr[id].sum*val%p;
        return;
    }    
    pushdowny(id);
    pushdownx(id);
    updatey(lid,l,r,val);
    updatey(rid,l,r,val);
    tr[id].sum=(tr[lid].sum+tr[rid].sum)%p;
    return;
}
ll query(ll id,ll l,ll r) 
{
    if(tr[id].l>r||tr[id].r<l) return 0;
    if(tr[id].l>=l&&tr[id].r<=r)
    {
        return tr[id].sum%p;
    }    
    pushdowny(id);
    pushdownx(id);    
    tr[id].sum=(tr[lid].sum+tr[rid].sum)%p;
    return (query(lid,l,r)+query(rid,l,r))%p;
}
int main()
{
    n=read();m=read();p=read();
    for(ll i=1;i<=n;i++)
    a[i]=read();
    build(1,1,n);
    ll judge,l,r,val;
    for(ll i=1;i<=m;i++)
    {
        judge=read();l=read();r=read();
        if(judge==1)
        {
            val=read();
            updatey(1,l,r,val%p);
        }
        if(judge==2)
        {
            val=read();
            updatex(1,l,r,val%p);
        }
        if(judge==3)
        {
            ll ans=query(1,l,r)%p;
            printf("%lld\n",ans);
        }
    }
    return 0;
}