P7497 四方喝彩题解

Moon_Night · 2023-07-18 13:20:12 · 题解

题目戳这里

本篇题解会详细讲解本题的思考过程，虽然并不是新方法，但是讲解详细，请耐心食用。

这道题需要用用线段树实现 区间加 , 区间乘 ，区间和的查询 ，以及 锁定区间（忽略其某时间范围内的修改）。与模板有区别的地方只有最后一个功能，也就是 操作3 。我们很容易想到，线段树多维护一个封锁结束的时间，然后在修改时候判断封锁是否结束。于是我们有了：

错误解法--多维护一个封锁时间

（赶时间请跳过此部分）

我们考虑在线段树中维护一个封锁结束时间，然后这道题就变得非常简单（小看了这道题），只需在下传懒标记/修改时判断节点是否解封，决定是否进行操作。于是：

我在修改操作的if(x<=l&&r<=y)中添加了以下代码：

if(tim<=block[root]) return;
// tim 为现在的时间 block[i] 为 i 节点结束封锁时间

在判断是否进行pushdown时，我们需要分类：

未封锁的父亲，已封锁的儿子。此时显然不需要pushdown，在封锁前，就把父亲需要传给儿子的下传完了，现在父亲的懒标记里是封锁后的操作，所以不需要pushdown。
已封锁的父亲，已封锁的儿子。此时可以pushdown，在封锁后，所有不应下传的都没有下传到父亲，所以父亲能传给儿子的只有封锁前的懒标记
其余情况无需下传。

于是有以下代码：

// add 为加法懒标记，times 为乘法懒标记
// block 为封锁时间
void pushdown(ll root,ll l,ll r,ll tim){
    block[ls]=max(block[ls],block[root]);
    block[rs]=max(block[rs],block[root]);
    if(block[ls]<tim||(block[root]>=tim)){
        (tree[ls]*=times[root])%=P;
        (tree[ls]+=add[root]*(mid-l+1)%P)%=P;
        (add[ls]*=times[root])%=P;
        (add[ls]+=add[root])%=P;
        (times[ls]*=times[root])%=P;
    }
    if(block[rs]<tim||(block[root]>=tim)){
        (tree[rs]*=times[root])%=P;
        (tree[rs]+=add[root]*(r-mid)%P)%=P;
        (add[rs]*=times[root])%=P;
        (add[rs]+=add[root])%=P;
        (times[rs]*=times[root])%=P;
    }
    add[root]=0; times[root]=1;
    return;
}

看起来十分合理，然后我们再简单地维护一下block[i]

void update_block(ll root,ll l,ll r,ll x,ll y,ll tim,ll z){
    if(l>r) return;
    if(x<=l&&r<=y){
        block[root]=max(block[root],z);
        return;
    }
    pushdown(root,l,r,tim);
    if(x<=mid) update_block(ls,l,mid,x,y,tim,z);
    if(y>mid) update_block(rs,mid+1,r,x,y,tim,z);
    return;
}

然后我们高高兴兴地跑样例，然后大悲！样例二怎么 \textcolor{red}{WA} 了？！

交上去：为什么？！我们冷静思考，惊恐的发现：如果在节点 i 解封前,父节点被修改，但懒标记未下传，在解封后，父节点将懒标记传给节点 i ，那么 i 就成功地在封锁的时间被修改了！除了这个问题，还有很多问题。如： 当一个区间有一部分被修改时，区间加加的还是r-l+1个吗？我们又要多维护一个值。 那么继续修改就会像打补丁一样，十分困难，这里改完那里有问题，因为我们小看了这道题。于是，我们的尝试宣告失败。

正确解法--拆分封锁与解封操作

那么我们怎么处理 封锁区间呢 ？我们认真思考~~或参考题解~~，得到了另一个方法：将这个操作变成两个操作，封锁 + 解封 。我们来思考一下细节。

考虑一次区间加（[l,r]+=z）：

这个整区间里若有一部分还在封锁中，那么就不能将区间直接 +=z*（r-l+1） , 而是+=未封锁元素个数*z 于是，我们再维护一个未封锁元素个数。

考虑一次区间乘（[l,r]*=z）:

这个整区间里若有一部分还在封锁中，那么就不能直接*=z，而是只把未封锁的部分*=z，而为了复杂度，我们不可能现场统计未封锁元素的和，于是我们决定分开维护封锁部分的区间和，未封锁部分的区间和。

然后，考虑多个封锁操作重叠：

我们不是很愿意将封锁操作合并，这很麻烦，于是就直接将多个封锁叠加，等到没有一个封锁才继续下传操作。所以维护的 封锁情况 不应该是 0/1 而是 --/++。

至此，我们要维护的所有东西如下：

struct segment{ 
    ll one,two,len,add,times,block; 
    /*
    one 代表未封锁的和
    two 代表封锁区域的和
    len 代表未封锁元素个数
    add 为加法懒标记     times为乘法懒标记
    block 为目前被封锁次数
    */
};

想自己尝试的同志可以先自己去写代码了。

接下来，配合代码食用，详细的注释与~~有些晦涩难懂的~~代码结合，比口述好理解得多。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define ls (2*root)
#define rs (2*root+1)
#define mid (l+((r-l)>>1))

using std::cin; using std::cout;
using std::max; using std::swap;
using std::vector; typedef long long ll;
const ll N=2e5+5,P=1e9+7;

struct Block{ ll l,r; }; // 封锁的区间

ll n,m,a[N];  
vector<Block> que[N]; // que[i]保存在 i 时刻，需要解封的区间

struct segment{ 
    ll one,two,len,add,times,block; 
    /*
    one 代表未封锁的和
    two 代表封锁区域的和
    len 代表未封锁元素个数
    add 为加法懒标记     times为乘法懒标记
    block 为目前被封锁次数
    */
};
struct Segment_Tree{
    segment tr[4*N];
    void pushdown(ll root){ // 下传懒标记
        if(tr[ls].block==0){ // 若整个区间被封锁，不能下传懒标记
            tr[ls].one=(tr[ls].one*tr[root].times%P+tr[root].add*tr[ls].len%P)%P;
            tr[ls].add=(tr[ls].add*tr[root].times%P+tr[root].add)%P;
            tr[ls].times=(tr[ls].times*tr[root].times)%P;
        }
        if(tr[rs].block==0){
            tr[rs].one=(tr[rs].one*tr[root].times%P+tr[root].add*tr[rs].len%P)%P;
            tr[rs].add=(tr[rs].add*tr[root].times%P+tr[root].add)%P;
            tr[rs].times=(tr[rs].times*tr[root].times)%P;
        }
        tr[root].add=0,tr[root].times=1;
        return;
    }
    void pushup(ll root){ // 子节点更新父亲
        if(tr[root].block==0){ // 若整个区间被封锁，那么子节点的one没有被修改，不能更新父亲
            tr[root].one=(tr[ls].one+tr[rs].one)%P;
            tr[root].two=(tr[ls].two+tr[rs].two)%P;
            tr[root].len=tr[ls].len+tr[rs].len;
        }// 不过在add等函数中，tr[root].block>0已经return了
        return;
    }
    void build(ll root,ll l,ll r){  // 初始化
        if(l>r) return; 
        tr[root].times=1; // 不要忘了把乘法懒标记初始化
        if(l==r){
            tr[root].one=a[l]%P;
            tr[root].len=1; // 一定不要忘初始未封锁元素个数
            return;
        }
        build(ls,l,mid); build(rs,mid+1,r);
        pushup(root);
        return;
    }
    void add(ll root,ll l,ll r,ll x,ll y,ll z){ // 区间加
        if(l>r||tr[root].block) return;
        if(x<=l&&r<=y){
            tr[root].one=(tr[root].one+tr[root].len*z%P)%P;
            tr[root].add=(tr[root].add+z)%P;
            return;
        } pushdown(root);
        if(x<=mid) add(ls,l,mid,x,y,z);
        if(y>mid) add(rs,mid+1,r,x,y,z);
        return pushup(root);
    }
    void times(ll root,ll l,ll r,ll x,ll y,ll z){ // 区间乘
        if(l>r||tr[root].block) return;
        if(x<=l&&r<=y){
            tr[root].one=(tr[root].one*z)%P;
            tr[root].add=(tr[root].add*z)%P;
            tr[root].times=(tr[root].times*z)%P;
            return;
        } pushdown(root);
        if(x<=mid) times(ls,l,mid,x,y,z);
        if(y>mid) times(rs,mid+1,r,x,y,z);
        return pushup(root);
    }
    void block(ll root,ll l,ll r,ll x,ll y){ // 封锁区间
        if(l>r) return;
        if(x<=l&&r<=y){
            if(l!=r) pushdown(root);
            if(tr[root].block==0){ // 第一次封锁
                tr[root].two=(tr[root].two+tr[root].one)%P;  tr[root].one=0;
                // 封锁整个区间，所以把所有和记到two里，one清零
                tr[root].len=0; // 解锁元素个数为零了          
            }
            ++tr[root].block; // 封锁次数+1，后面解锁时不要改回零，而是-1
            return;
        } pushdown(root);
        if(x<=mid) block(ls,l,mid,x,y);
        if(y>mid) block(rs,mid+1,r,x,y);
        return pushup(root);
    }
    void deblock(ll root,ll l,ll r,ll x,ll y){ //解封区间
        if(l>r) return;
        if(x<=l&&r<=y){
            --tr[root].block;  // 呼应上文++，解除一重封锁
            if(tr[root].block==0){ // 若已经全部解封
                if(l==r) swap(tr[root].one,tr[root].two),tr[root].len=1; // 由于整体解封，原来未解封的变成解封的，没有未解封的元素，因为这里是叶节点所以len=1
                else pushup(root); // 若不是叶节点接受子节点信息即可
            }
            return;
        } pushdown(root);
        if(x<=mid) deblock(ls,l,mid,x,y);
        if(y>mid) deblock(rs,mid+1,r,x,y);
        return pushup(root);
    }
    ll inque(ll root,ll l,ll r,ll x,ll y){ //询问，函数名有点奇怪，但是我习惯了
        if(l>r) return 0;
        if(x<=l&&r<=y) return (tr[root].one+tr[root].two)%P; // 询问整个区间的和，自然包括解封的和未解封的
        pushdown(root); ll ret=0;
        if(x<=mid) ret=inque(ls,l,mid,x,y)%P;
        if(y>mid) ret=(ret+inque(rs,mid+1,r,x,y))%P;
        return ret;
    }
} tree;

int main(){
    std::ios::sync_with_stdio(0); 
    cin>>n>>m; for(ll i=1;i<=n;cin>>a[i],++i);  // 码风较奇怪……
    tree.build(1,1,n);
    for(ll i=1,type,l,r,x;i<=m;++i){
        cin>>type>>l>>r;
        if(type==4){
            cout<<tree.inque(1,1,n,l,r)<<"\n";
            for(Block &j:que[i]) tree.deblock(1,1,n,j.l,j.r); // continue 前，一定要把操作做完啊啊啊，卡了我好久
            continue;
        }  cin>>x;
        if(type==1) tree.add(1,1,n,l,r,x);
        else if(type==2) tree.times(1,1,n,l,r,x);
        else{
            tree.block(1,1,n,l,r);
            que[i+x].push_back({l,r}); // 记录每一次解封操作
        }
        for(Block &j:que[i]) tree.deblock(1,1,n,j.l,j.r); // 于所有操作之后解封，因为 i+x 时刻也是被封锁的
    }
    return 0;
}

然后，就结束了。。感谢看到这里，不喜勿喷。

这道题是一道很有趣的题，希望大家，学习愉快。。。。

其余参考 littleKtian 巨佬的题解

P7497 四方喝彩 题解

题目戳这里

错误解法--多维护一个封锁时间

正确解法--拆分封锁与解封操作

P7497 四方喝彩题解