CDOJ 1597-線分樹好題(2017 UESTC Training for Data Structures C)

トランスポートゲート:CDOJ 1597
テーマ:
長さnのシーケンス、m回の操作、3つの操作をあげます.
1.区間内の各数に非負の整数を乗算します.
2.区間内の各数に非負の整数を加算.
3.一定区間の和模上Pの値を問い合わせる.
テーマ構想:
まず、この区間の和を線分木で維持することをよく考えましたが、ここには乗算が多くて、加算はよく処理されています.
実は乗算を考えてみると、乗算の怠惰な配列を追加して、更新時に新しいものと同じようにすることができます.ここの問題です.
加算と乗算の更新の順序で、私たちは先に更新の順序を確定することができて、私たちは先に乗算を更新して、加算を更新して、私たちは知っています
乗算を更新するには、前に加算がある場合は、先に乗算を加算しなければなりません.ここでは、加算された配列にそれ自体の乗算を加算することができます.
乗ろうとする数は、迷わず順番に更新できます.
ACコード:

#include
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int maxn = 1e5+100;
ll p;
int n;
ll Tree[maxn<<2],cadd[maxn<<2],cmul[maxn<<2];
void Build(int l,int r,int rt)
{
    cadd[rt] = 0;
    cmul[rt] = 1;

    if(l==r)
    {
        scanf("%lld",&Tree[rt]);
        return ;
    }
    int mid = (l+r)>>1;

    Build(lson);
    Build(rson);
    Tree[rt] = Tree[rt<<1]+Tree[rt<<1|1];
    Tree[rt]%=p;
}

void pushdown(int rt,ll m)
{
    
    //              
    cadd[rt<<1]=(cadd[rt<<1]*cmul[rt]+cadd[rt])%p;
    cadd[rt<<1|1]=(cadd[rt<<1|1]*cmul[rt]+cadd[rt])%p;

    
    //     
    cmul[rt<<1] *= cmul[rt];
    cmul[rt<<1|1] *= cmul[rt];

    cmul[rt<<1] %= p;
    cmul[rt<<1|1] %= p;

    //     
    Tree[rt<<1]=(Tree[rt<<1]*cmul[rt]+(m-m/2ll)*cadd[rt])%p;
    Tree[rt<<1|1]=(Tree[rt<<1|1]*cmul[rt]+(m/2ll)*cadd[rt])%p;

    cadd[rt] = 0;
    cmul[rt] = 1;

}

void updata(int L,int R,int l,int r,int rt ,ll c,int op)
{
    if(L<=l&&r<=R)
    {
        if(op==1)
        {
            cadd[rt] = cadd[rt]*c;
            cadd[rt]%=p;
            cmul[rt]*=c;
            cmul[rt]%=p;
            Tree[rt]*=c;
            Tree[rt]%=p;
        }
        else
        {
            cadd[rt]+=c;
            cadd[rt]%=p;
            Tree[rt]+=c*(r-l+1ll);
            Tree[rt]%=p;
        }

        return ;
    }

    pushdown(rt,r-l+1ll);

    int mid = (l+r)>>1;
    if(L<=mid)
    {
        updata(L,R,lson,c,op);
    }
    if(R>mid)
    {
        updata(L,R,rson,c,op);
    }

    Tree[rt] = (Tree[rt<<1]+Tree[rt<<1|1])%p;
}

ll quary(int L,int R,int l,int r,int rt)
{

    if(L<=l&&r<=R)return Tree[rt]%p;
    pushdown(rt,r-l+1ll);
    int mid = (l+r)>>1;
    ll res = 0;
    if(L<=mid)res+=quary(L,R,lson);
    if(R>mid)res+=quary(L,R,rson);
    return res%p;
}

int main()
{
    cin>>n>>p;
    Build(1,n,1);
    int m;
    cin>>m;
    while(m--)
    {
        int id,a,b;
        ll c;
        scanf("%d",&id);
        if(id==1)
        {
            scanf("%d%d%lld",&a,&b,&c);
            updata(a,b,1,n,1,c,1);
        }
        else if(id==2)
        {
            scanf("%d%d%lld",&a,&b,&c);
            updata(a,b,1,n,1,c,2);
        }
        else
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",quary(a,b,1,n,1));
        }
    }

    return 0;
}