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

千梦羽翼 · 2018-11-03 22:51:11 · 题解

做完后Cry了，呜呜呜，擦干眼泪写题解~

咳咳...

本代码非结构体~

敲黑板啦！

今天就让本蒟蒻带领您完全解读代码吧（用蒟蒻的思维看世界~）

前言：看了一下各位大佬写的代码我是非常非常的佩服，但我看了一下大多数都使用了“结构体”（struct..）所以我就写了一份不用“结构体”的代码，简介易懂，适用于（在1s前刚刚学会正常的线段树(即区间求和和区间询问，仅仅是对于某区间加法的辣种））
准备阶段：若您一点都不了解“线段树”的话，强烈建议您先把此题目做出来：https://www.luogu.org/problemnew/show/P3372 。您可以参考这篇文档入门（请看最前面点赞数超过1000+的辣一位，作者：_皎月半洒花）：https://www.luogu.org/problemnew/solution/P3372

再谈线段树：

在线段树中，一开始我觉得最难的就是（lazy_tag延迟标记，也就是您看到的add数组，mul数组），这是什么东西啊，内心是拒绝的，我想：每次更新的时候顺便把所有的子节点全部更新不就OK了吗？但是后来再想想，这样做是很浪费滴（浪费是可耻的哦~），因为您看（见下图），当我们想要知道sum[1..6]的时候，您只需要询问1号节点即可，无论是修改还是询问，其实很多子节点如果不需要，您是没有必要去修改它的，您可以用数组（add数组，mul数组，即延迟标记）把它们暂时存储起来，当您想要用道的时候，在一起更新子节点，甚至对于多次修改时候更加巧妙，若您想两次修改区间同一个区间[1..2]时，即打了两次延迟标记，即更加节省时间，更能体现它的作用，在往下推广，即多个区间中有交集，则其中有线段树节点是被重复修改的，所以使用延迟标记等下次用到的时候再更新，所以引入了延迟标记来避免多次更新，减少浪费。所以它是一个动态（这个词是在本蒟蒻绞尽脑汁想出来的，未知是否规范）的。

再谈此题：

我们可以看道的是，题目中多了一个让区间乘法的操作，What?什么玩意，头脑顿时失了智~

等冷静下来您可以发现如下事实：（见下图）最后您需要更新对应的节点值：tr[p]=( tr[p]Xmulk+(r-l+1)Xsumk)%mo;（“X”是乘法的意思）

当然您会发现：

ll query(ll p,ll l,ll r,ll x,ll y){
    if (x<=l&&r<=y) return tr[p] ;
    pushdown(p,l,r);
    ll mid=(l+r)/2,res=0;
    if (x<=mid) res+=query(p*2,l,mid,x,y);
    if (mid<y) res+=query(p*2+1,mid+1,r,x,y);
    return res%mo;
}

在最后没有更新对应节点的值（“tr[p]=( tr[p]Xmulk+(r-l+1)Xsumk)%mo;（“X”是乘法的意思）”）：这是因为您并没有修改子节点，故无需重新计算。

ADD函数即算出对应节点应该有的值，和对应的add，mul（延迟标记）注意，此函数不仅在pushdown中被使用了一次，在以change开头的函数中均有调用。 changesum是算加法；changemul算的是乘法。

总共84行，~~因为思路过于清晰，代码过于简洁无需注释~~。

#include<bits/stdc++.h>
#define ll long long
#define N 10000005 
using namespace std;
ll a[N],tr[N*4],mo,mul[N*4],add[N*4],n,m;
void build(ll p,ll l,ll r){//我不是注释：建造
    mul[p]=1;
    if (l==r){
        tr[p]=a[l];
        return ;
    }
    ll mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tr[p]=(tr[p*2]+tr[p*2+1])%mo;
    return ;
}
void ADD(ll p,ll l,ll r,ll mulk,ll sumk){
    tr[p]=(tr[p]*mulk+(r-l+1)*sumk)%mo;
    add[p]=(add[p]*mulk+sumk)%mo;
    mul[p]=(mul[p]*mulk)%mo;
    return ;
}
void pushdown(ll p,ll l,ll r){
    ll mid=(l+r)/2;
    ADD(p*2,l,mid,mul[p],add[p]);//我不是注释：下传递两个字节点
    ADD(p*2+1,mid+1,r,mul[p],add[p]);
    add[p]=0;
    mul[p]=1;
    return ;
}
void changemul(ll p,ll l,ll r,ll x,ll y,ll v){
    if (x<=l&&r<=y){
        ADD(p,l,r,v,0);
        return ;
    }
    pushdown(p,l,r);
    ll mid=(l+r)/2;
    if (x<=mid) changemul(p*2,l,mid,x,y,v);//我不是注释：看是否还有包含的交集，下同理
    if (mid<y) changemul(p*2+1,mid+1,r,x,y,v);
    tr[p]=(tr[p*2]+tr[p*2+1])%mo;
}
void changesum(ll p,ll l,ll r,ll x,ll y,ll v){
    if (x<=l&&r<=y){
        ADD(p,l,r,1,v);
        return ;
    }
    pushdown(p,l,r);
    ll mid=(l+r)/2;
    if (x<=mid) changesum(p*2,l,mid,x,y,v);
    if (mid<y) changesum(p*2+1,mid+1,r,x,y,v);
    tr[p]=(tr[p*2]+tr[p*2+1])%mo;
}
ll query(ll p,ll l,ll r,ll x,ll y){//我不是注释：区间询问
    if (x<=l&&r<=y) return tr[p] ;
    pushdown(p,l,r);
    ll mid=(l+r)/2,res=0;
    if (x<=mid) res+=query(p*2,l,mid,x,y);
    if (mid<y) res+=query(p*2+1,mid+1,r,x,y);
    return res%mo;
}
int main(){
    scanf("%lld %lld %lld",&n,&m,&mo);//我不是注释：注意%lld
    for (ll i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    build(1,1,n);
    for (ll i=1;i<=m;i++){
        ll n1=0;ll x,y,k;
        scanf("%lld",&n1);
        if (n1==1){
            scanf("%lld %lld %lld",&x,&y,&k);
            changemul(1,1,n,x,y,k);
        }
        if (n1==2){
            scanf("%lld %lld %lld",&x,&y,&k);
            changesum(1,1,n,x,y,k);
        }
        if (n1==3){
            scanf("%lld %lld",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

蟹蟹，momoda~

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

敲黑板啦！

今天就让本 蒟蒻 带领您 完全解读代码吧（用 蒟蒻 的思维看世界~）

再谈线段树：

再谈此题：

今天就让本蒟蒻带领您完全解读代码吧（用蒟蒻的思维看世界~）