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

Mys_C_K · 2017-03-17 21:06:51 · 题解

非常恶心的debug个了一个周，最后发现是加乘合并的时候少写了！！！QWQ

(ax+b)*c+d=a*c*x+b*c+d，区间和的更新略过，乘法标记*c，加法标记*c+d!!!

附上丑陋的代码：

//luogu P3373
#include<cstdio>
#include<cstring>
#define ull long long int
using namespace std;
struct segment{
    ull plus_tag,times_tag,sumn;
    int lef,rig;
    segment *tc,*rc;
}*root;
int n,m;ull mod;
inline int push_up(segment* &rt)
{
    rt->sumn=(rt->tc->sumn+rt->rc->sumn)%mod;
    return 0;
}
inline int update_tags(segment* &rt,ull ptag,ull ttag)
{
    int s=rt->lef,t=rt->rig;
    rt->times_tag=rt->times_tag*ttag%mod;
    rt->plus_tag=(rt->plus_tag*ttag+ptag)%mod;
    rt->sumn=(rt->sumn*ttag+ptag*(t-s+1))%mod;
    return 0;
}
inline int push_down(segment* &rt)
{
    update_tags(rt->tc,rt->plus_tag,rt->times_tag);
    update_tags(rt->rc,rt->plus_tag,rt->times_tag);
    rt->plus_tag=0;rt->times_tag=1;return 0;
}
int build_segment(segment* &rt,int lef,int rig)
{
    rt=new segment;
    rt->lef=lef;rt->rig=rig;
    rt->plus_tag=0;rt->times_tag=1;
    if(lef==rig)
    {
        scanf("%lld",&rt->sumn);
        return 0;
    }
    int mid=(lef+rig)/2;
    build_segment(rt->tc,lef,mid);
    build_segment(rt->rc,mid+1,rig);
    push_up(rt);return 0;
}
int plus_segment(segment* &rt,int s,int t,ull val)
{
    int lef=rt->lef,rig=rt->rig;
    if(s<=lef&&rig<=t)
    {
        rt->plus_tag=(rt->plus_tag+val)%mod;
        rt->sumn=((ull)(rig-lef+1)*val%mod+rt->sumn)%mod;
        return 0;
    }
    if(rt->plus_tag!=0||rt->times_tag!=1) push_down(rt);
    int mid=(lef+rig)/2;
    if(s<=mid) plus_segment(rt->tc,s,t,val);
    if(mid<t) plus_segment(rt->rc,s,t,val);
    push_up(rt);return 0;
}
int times_segment(segment* &rt,int s,int t,ull val)
{
    int lef=rt->lef,rig=rt->rig;
    if(s<=lef&&rig<=t)
    {
        rt->times_tag=val*rt->times_tag%mod;
        rt->plus_tag=val*rt->plus_tag%mod;
        rt->sumn=rt->sumn*val%mod;
        return 0;
    }
    if(rt->plus_tag!=0||rt->times_tag!=1) push_down(rt);
    int mid=(lef+rig)/2;
    if(s<=mid) times_segment(rt->tc,s,t,val);
    if(mid<t) times_segment(rt->rc,s,t,val);
    push_up(rt);return 0;
}
ull query_segment(segment* &rt,int s,int t)
{
    int lef=rt->lef,rig=rt->rig;
    if(s<=lef&&rig<=t) return rt->sumn%mod;
    if(rt->plus_tag!=0||rt->times_tag!=1) push_down(rt);
    int mid=(lef+rig)/2;ull ans=0;
    if(s<=mid) ans=(ans+query_segment(rt->tc,s,t))%mod;
    if(mid<t) ans=(ans+query_segment(rt->rc,s,t))%mod;
    push_up(rt);return ans%mod;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&mod);
    build_segment(root,1,n);
    int opt,u,v;
    ull val;
    while(m--)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%lld",&u,&v,&val);
            times_segment(root,u,v,val);
        }
        else if(opt==2)
        {
            scanf("%d%d%lld",&u,&v,&val);
            plus_segment(root,u,v,val);
        }
        else{
            scanf("%d%d",&u,&v);
            printf("%lld\n",query_segment(root,u,v)%mod);
        }
    }
    return 0;
}