题解 P3373 【【模板】线段树 2】

· · 题解

1 都乘

2 都加

3 求区间和模p的值

我看前面题解没有把加法和乘法写在一个函数里的，我就把整个修改写在一个函数里。

代码如下 见注释:

#include<bits/stdc++.h>
#define lson l,m,rt<<1  //省力省时间
#define rson m+1,r,rt<<1|1
using namespace std;
long long z[1000005<<2|1],sum[1000005<<2|1],add[1000005<<2|1],mul[1000005<<2|1]; //一般要开到4倍 不然可能爆
long long n,m,a,p;
void update(int rt)//rt表示当前的节点
{
    sum[rt] = (sum[rt<<1]+sum[rt<<1|1])%p; //sum表示线段树该节点（表示一个区间）的和，由左儿子和右儿子组成
    return;//怕在中间过程爆int 所以所有变量开成long long 然后随时取%
} 
void color(int l,int r,int rt,int x,int y)  //标记更新 我们每一次都看成把这个区间所有数 *a + b（乘a然后加上b）
{                                                     //算加法时 y变成1  ；算乘法时 x=0
    sum[rt] = ((sum[rt]*y)+(1ll*(r-l+1)*x))%p; //更新sum 
    mul[rt] = (mul[rt]*y)%p; //更新乘法标记
    add[rt] = (add[rt]*y+x)%p;//更新加法标记 别忘了乘上
    return;
} 
void push_col(int l,int r,int rt)//下放标记 rt表示当前的节点
{
    if(mul[rt]!=1 || add[rt]!=0)//判断是否有标记
    {
        int m = (l+r)>>1;//分一半 线段树思想
        color(lson,add[rt],mul[rt]); //忘了的看最上面define
        color(rson,add[rt],mul[rt]);
        add[rt] = 0; //下放完标记后 恢复初始状态
        mul[rt] = 1; 
    } 
    return;
} 
void build(int l,int r,int rt)//建树 千万注意初始化应该在if的外面 调了一个晚上就因为这个
{
    mul[rt]=1; 
    add[rt]=0;
    if(l==r)
    { 
        sum[rt] = z[l];//最下面的节点=z[最下面的左端点] 不理解的可以画一个图看下 z的输入在main 函数里
        return;
    }
    int m = (l+r)>>1;//(l+r)/2 
    build(lson);//递归建树
    build(rson);
    update(rt); //计算最初的sum
} 
void modify(int l,int r,int rt,int nowl,int nowr,int x,int y) //修改函数 nowl 和 nowr就是要修改的区间 x,y 同上
{ 
    if(nowl<=l && r<=nowr)//如果覆盖的话 就可以全部取出 区间修改思想
    {
        color(l,r,rt,x,y); 
        return; 
    } 
    if(mul[rt]!=1 || add[rt]!=0) //下放
        push_col(l,r,rt); 
    int m=(l+r)>>1;
    if(nowl<=m) //和左儿子有交集 往左儿子找
        modify(lson,nowl,nowr,x,y);
    if(m<nowr) //和右儿子有交集 往右儿子找
        modify(rson,nowl,nowr,x,y); 
    update(rt);//更新
} 
long long query(int l,int r,int rt,int nowl,int nowr)//查询函数
{
    if(nowl<=l && r<=nowr)//覆盖就返回
    {
        return (sum[rt])%p; 
    }
    if(mul[rt]!=1 || add[rt]!=0) //有标记的话需要下放 否则该点就是没有更新过的
        push_col(l,r,rt);
    int m=(l+r)>>1;
    long long ans = 0;//开long long 防止爆
    if(nowl<=m) ans+=query(lson,nowl,nowr)%p;//很好理解 找到了就加上 %p为了防爆
    if(m<nowr) ans+=query(rson,nowl,nowr)%p;
    return ans%p; 
} 
int main()
{
    long long x,y,k;
    scanf("%lld %lld %lld",&n,&m,&p);//读入 n m p
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&z[i]); //输入序列
    } 
    build(1,n,1);//建树
    for(int i=1;i<=m;i++)//while(m--) 也一样
    { 
        scanf("%d",&a);//用 case 也行
        if(a==1)//乘法 
        { 
            scanf("%lld %lld %lld",&x,&y,&k);
            modify(1,n,1,x,y,0,k); //加法处 置0
        } 
        if(a==2)//加法 
        {
            scanf("%lld %lld %lld",&x,&y,&k);
            modify(1,n,1,x,y,k,1);//乘法处 置1！！！
        } 
        if(a==3)
        {
            scanf("%lld %lld",&x,&y); 
            printf("%lld\n",(query(1,n,1,x,y))%p);//查询 输出
        } 
    } 
    return 0; 
} 
有可以优化的地方还请指教！