原题链接

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
ll tree[410000]={0};
ll wait_mul[410000]={0};
ll wait_add[410000]={0};
ll n,p;

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

void build(ll node,ll l,ll r)
{
    if(l==r)
    {
        read(tree[node]);
        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 fresh(int node, int l, int r) {
    tree[node] = (tree[node] * wait_mul[node] % p + (r - l + 1) * wait_add[node] % p) % p;//更新为待乘值乘上固定值加上待加值
    if (l != r)
    {
        wait_mul[node * 2] = wait_mul[node * 2] * wait_mul[node] % p;
        wait_add[node * 2] = (wait_add[node * 2] * wait_mul[node] % p + wait_add[node]) % p;//向下传的时候需要给待加值和待乘值同时乘上
        wait_mul[node * 2 + 1] = wait_mul[node * 2 + 1] * wait_mul[node] % p;
        wait_add[node * 2 + 1] = (wait_add[node * 2 + 1] * wait_mul[node] % p + wait_add[node]) % p;
    }
    wait_mul[node] = 1;
    wait_add[node] = 0;
}


void mul(ll node,ll l,ll r,ll x,ll y,ll c)
{
    fresh(node,l,r);
    if(r<x||l>y)return;

    if(l>=x&&r<=y)
    {
        wait_mul[node]=wait_mul[node]*c%p;
        wait_add[node]=wait_add[node]*c%p;
        fresh(node,l,r);
        return;
    }

    ll mid=(l+r)>>1;
    mul(node<<1,l,mid,x,y,c);
    mul((node<<1)+1,mid+1,r,x,y,c);
    tree[node]=(tree[node<<1]+tree[(node<<1)+1])%p;
}

void add(ll node,ll l,ll r,ll x,ll y,ll c)
{
    fresh(node,l,r);
    if(r<x||l>y)return;

    if(l>=x&&r<=y)
    {
        wait_add[node]=(wait_add[node]+c)%p;
        fresh(node,l,r);
        return;
    }

    ll mid=(l+r)>>1;
    add(node<<1,l,mid,x,y,c);
    add((node<<1)+1,mid+1,r,x,y,c);
    tree[node]=(tree[node<<1]+tree[(node<<1)+1])%p;
}

ll query(ll node,ll l,ll r,ll x,ll y)
{
    fresh(node,l,r);
    if(r<x||l>y)return 0;
    if(l>=x&&r<=y) return tree[node];

    ll mid=(l+r)>>1;
    return (query(node<<1,l,mid,x,y)+query((node<<1)+1,mid+1,r,x,y))%p;
}

int main()
{
    fill(wait_mul, wait_mul + 410000, 1);
    read(n); read(p);

    build(1,1,n);

    ll m;
    read(m);
    while(m--)
    {
        ll op;
        read(op);
        if(op==1)
        {
            ll l,r,c;
            read(l); read(r); read(c);
            mul(1,1,n,l,r,c);
        }
        else if(op==2)
        {
            ll l,r,c;
            read(l); read(r); read(c);
            add(1,1,n,l,r,c);
        }
        else
        {
            ll l,r;
            read(l); read(r);
            write(query(1,1,n,l,r)%p); putchar('\n');
        }
    }
    return 0;
}