线段树2

YANZIRUI · 2024-12-19 19:40:30 · 个人记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,q,m;
int a[N];
int lazy_tag_add[4*N];
int lazy_tag_mul[4*N];
int tree[4*N];
int ls(int p)
{
    return p << 1;
}
int rs(int p)
{
    return p << 1 | 1;
}
void push_up(int p)
{
    tree[p]=tree[ls(p)]+tree[rs(p)];
    tree[p]%=m;
}
void build(int p,int l,int r)
{
    lazy_tag_add[p]=0;
    lazy_tag_mul[p]=1;
    if(l==r)
    {
        tree[p]=a[l];
        return;
    }
    int mid=(l+r) >> 1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void mul_tag(int p,int l,int r,int k)
{
    lazy_tag_mul[p]*=k;
    lazy_tag_mul[p]%=m;
    lazy_tag_add[p]*=k;
    lazy_tag_add[p]%=m;
    tree[p]*=k;
    tree[p]%=m;
}
void add_tag(int p,int l,int r,int k)
{
    lazy_tag_add[p]+=k;
    lazy_tag_add[p]%=m;
    tree[p]+=k*(r-l+1);
    tree[p]%=m;
}
void push_down_mul(int p,int l,int r)
{
    if(lazy_tag_mul[p]!=1)
    {
        int mid=(l+r) >> 1;
        mul_tag(ls(p),l,mid,lazy_tag_mul[p]);
        mul_tag(rs(p),mid+1,r,lazy_tag_mul[p]);
        lazy_tag_mul[p]=1;
    }
}
void push_down_add(int p,int l,int r)
{
    if(lazy_tag_add[p]!=0)
    {
        int mid=(l+r) >> 1;
        add_tag(ls(p),l,mid,lazy_tag_add[p]);
        add_tag(rs(p),mid+1,r,lazy_tag_add[p]);
        lazy_tag_add[p]=0;
    }
}
void push_down(int p,int l,int r)
{
    push_down_add(p,l,r);
    push_down_mul(p,l,r);
}
void updata_mul(int L,int R,int p,int l,int r,int k)
{
    if(L<=l && R>=r)
    {
        mul_tag(p,l,r,k);
        return;
    }
    push_down(p,l,r);
    int mid=(l+r) >> 1;
    if(L<=mid)updata_mul(L,R,ls(p),l,mid,k);
    if(R>mid)updata_mul(L,R,rs(p),mid+1,r,k);
    push_up(p);
}
void updata_add(int L,int R,int p,int l,int r,int k)
{
    if(L<=l && R>=r)
    {
        add_tag(p,l,r,k);
        return;
    }
    push_down(p,l,r);
    int mid=(l+r) >> 1;
    if(L<=mid)updata_add(L,R,ls(p),l,mid,k);
    if(R>mid)updata_add(L,R,rs(p),mid+1,r,k);
    push_up(p);
}
int query(int L,int R,int p,int l,int r)
{
    if(L<=l && R>=r)
    {
        return tree[p];
    }
    push_down(p,l,r);
    int sum=0;
    int mid=(l+r) >> 1;
    if(L<=mid)
    {
        sum+=query(L,R,ls(p),l,mid);
        sum%=m;
    }
    if(R>mid)
    {
        sum+=query(L,R,rs(p),mid+1,r);
        sum%=m;
    }
    return sum;
}
signed main()
{
    cin>>n>>q>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r,k;
            cin>>l>>r>>k;
            updata_mul(l,r,1,1,n,k);
        }
        else if(op==2)
        {
            int l,r,k;
            cin>>l>>r>>k;
            updata_add(l,r,1,1,n,k);
        }
        else 
        {
            int l,r;
            cin>>l>>r;
            cout<<query(l,r,1,1,n)<<endl;
        }
    }
    return 0;
}