洛谷 P3373 【模板】线段树 2 解题报告

P3373 【模板】线段树 2

题目描述

如题，已知一个数列，你需要进行下面三种操作：

1.将某区间每一个数乘上(x)

2.将某区间每一个数加上(x)

3.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含三个整数(N)、(M)、(P)，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含(N)个用空格分隔的整数，其中第(i)个数字表示数列第(i)项的初始值。

接下来(M)行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 (x) (y) (k) 含义：将区间([x,y])内每个数乘上(k)

操作2：格式：2 (x) (y) (k) 含义：将区间([x,y])内每个数加上(k)

操作3：格式：3 (x) (y) 含义：输出区间([x,y])内每个数的和对(P)取模所得的结果

输出格式：

输出包含若干行整数，即为所有操作3的结果。

说明

时空限制：1000ms,128M

好题。

我们分别维护两个(lazytag)，分别表示乘法和加法优先

不妨规定乘法优先，加法滞后

意思就是当我们(pushdown)时，总是对原区间先进行乘法操作，再进行加法操作

这样对于加法修改，我们直接做不用管乘法

对于乘法操作，我们直接对加法和乘法的(lazytag)做同样的操作即可

对于询问我们都给(pushdown)掉

Code:

#include <cstdio>
#define ls id<<1
#define rs id<<1|1
#define ll long long
const int N=100010;
ll lazymul[N<<2],lazyadd[N<<2],sum[N<<2],a[N];
ll n,m,p;
void push_downadd(ll id,ll L,ll R)
{
    if(L!=R)
    {
        ll mid=L+R>>1;
        sum[ls]=(sum[ls]+(mid+1-L)*lazyadd[id])%p;
        sum[rs]=(sum[rs]+(R-mid)*lazyadd[id])%p;
        (lazyadd[ls]+=lazyadd[id])%=p;
        (lazyadd[rs]+=lazyadd[id])%=p;
    }
    lazyadd[id]=0;
}
void push_downmul(ll id,ll L,ll R)
{
    if(lazymul[id]==1) return;
    if(L!=R)
    {
        ll mid=L+R>>1;
        sum[ls]=(sum[ls]*lazymul[id])%p;
        sum[rs]=(sum[rs]*lazymul[id])%p;
        (lazymul[ls]*=lazymul[id])%=p;
        (lazymul[rs]*=lazymul[id])%=p;
        (lazyadd[ls]*=lazymul[id])%=p;
        (lazyadd[rs]*=lazymul[id])%=p;
    }
    lazymul[id]=1;
}
void updata(ll id)
{
    sum[id]=(sum[ls]+sum[rs])%p;
}
void changemul(ll id,ll l,ll r,ll L,ll R,ll mult)
{
    push_downmul(id,L,R);
    push_downadd(id,L,R);
    if(l==L&&r==R)
    {
        sum[id]=(sum[id]*mult)%p;
        lazymul[id]=(lazymul[id]*mult)%p;
        return;
    }
    ll mid=L+R>>1;
    if(r<=mid) changemul(ls,l,r,L,mid,mult);
    else if(l>mid) changemul(rs,l,r,mid+1,R,mult);
    else changemul(ls,l,mid,L,mid,mult),changemul(rs,mid+1,r,mid+1,R,mult);
    updata(id);
}
void changeadd(ll id,ll l,ll r,ll L,ll R,ll delta)
{
    push_downmul(id,L,R);
    push_downadd(id,L,R);
    if(l==L&&r==R)
    {
        sum[id]=(sum[id]+(R+1-L)*delta)%p;
        lazyadd[id]=(lazyadd[id]+delta)%p;
        return;
    }
    ll mid=L+R>>1;
    if(r<=mid) changeadd(ls,l,r,L,mid,delta);
    else if(l>mid) changeadd(rs,l,r,mid+1,R,delta);
    else changeadd(ls,l,mid,L,mid,delta),changeadd(rs,mid+1,r,mid+1,R,delta);
    updata(id);
}
ll query(ll id,ll l,ll r,ll L,ll R)
{
    if(l==L&&r==R)
        return sum[id];
    push_downmul(id,L,R);
    push_downadd(id,L,R);
    ll mid=L+R>>1;
    if(r<=mid) return query(ls,l,r,L,mid);
    else if(l>mid) return query(rs,l,r,mid+1,R);
    else return (query(ls,l,mid,L,mid)+query(rs,mid+1,r,mid+1,R))%p;
}
void build(ll id,ll l,ll r)
{
    lazymul[id]=1;
    if(l==r)
    {
        sum[id]=a[l];
        return;
    }
    ll mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    updata(id);
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&p);
    ll opt,x,y,k;
    for(int i=1;i<=n;i++)
        scanf("%lld",a+i);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&opt,&x,&y);
        if(opt==1)
        {
            scanf("%lld",&k);
            changemul(1,x,y,1,n,k);
        }
        else if(opt==2)
        {
            scanf("%lld",&k);
            changeadd(1,x,y,1,n,k);
        }
        else
            printf("%lld
",query(1,x,y,1,n));
    }
    return 0;
}

2018.7.25