洛谷 P2023 维护序列 题解

题面

注意一个细节，查询和更新都需要pushdown();

#include <bits/stdc++.h>

#define int long long

using namespace std;

int n,m,p;

int a[];

struct ha{

    long long v;

    long long mul;

    long long add;

}tree[];

void build(int k,int l,int r)

{

    tree[k].mul=;

    tree[k].add=;

    if(l==r){

        tree[k].v=a[l];

    }

    else{

        int mid=(l+r)/;

        build(k<<,l,mid);

        build(k<<|,mid+,r);

        tree[k].v=tree[k<<].v+tree[k<<|].v;

    }

    tree[k].v%=p;

    return;

}

void pushdown(int k,int l,int r)

{

    int mid=(l+r)/;

    tree[k<<].v=(tree[k<<].v*tree[k].mul+tree[k].add*(mid-l+))%p;

    tree[k<<|].v=(tree[k<<|].v*tree[k].mul+tree[k].add*(r-mid))%p;

    tree[k<<].mul=(tree[k<<].mul*tree[k].mul)%p;

    tree[k<<|].mul=(tree[k<<|].mul*tree[k].mul)%p;

    tree[k<<].add=(tree[k<<].add*tree[k].mul+tree[k].add)%p;

    tree[k<<|].add=(tree[k<<|].add*tree[k].mul+tree[k].add)%p;

    tree[k].mul=;

    tree[k].add=;

    return;

}

void muladd(int k,int l,int r,int x,int y,int goal)

{

    if(y<l||x>r){

        return;

    }

    if(x<=l&&r<=y){

        tree[k].v=(tree[k].v*goal)%p;

        tree[k].mul=(tree[k].mul*goal)%p;

        tree[k].add=(tree[k].add*goal)%p;

        return;

    }

    pushdown(k,l,r);

    int mid=(l+r)/;

    muladd(k<<,l,mid,x,y,goal);

    muladd(k<<|,mid+,r,x,y,goal);

    tree[k].v=(tree[k<<].v+tree[k<<|].v)%p;

    return;

}

void addadd(int k,int l,int r,int x,int y,int goal)

{

    if(x>r||y<l){

        return;

    }

    if(x<=l&&y>=r){

        tree[k].add=(tree[k].add+goal)%p;

        tree[k].v=(tree[k].v+goal*(r-l+))%p;

        return;

    }

    pushdown(k,l,r);

    int mid=(l+r)/;

    addadd(k<<,l,mid,x,y,goal);

    addadd(k<<|,mid+,r,x,y,goal);

    tree[k].v=(tree[k<<].v+tree[k<<|].v)%p;

    return;

}

int ask(int k,int l,int r,int x,int y)

{

    if(x>r||y<l){

        return ;

    }

    if(x<=l&&y>=r){

        return tree[k].v;

    }

    pushdown(k,l,r);

    int mid=(l+r)/;

    return (ask(k<<,l,mid,x,y)+ask(k<<|,mid+,r,x,y))%p;

}

signed main()

{

    cin>>n>>p;

    for(int i=;i<=n;i++){

        cin>>a[i];

    }

    build(,,n);

    cin>>m;

    for(int i=;i<=m;i++){

        int type;

        cin>>type;

        if(type==){

            int x,y,v;

            cin>>x>>y>>v;

            muladd(,,n,x,y,v);

        }

        else if(type==){

            int x,y,v;

            cin>>x>>y>>v;

            addadd(,,n,x,y,v);

        }

        else{

            int x,y;

            cin>>x>>y;

            cout<<ask(,,n,x,y)<<endl;

        }

    }

}