P6242 【模板】线段树 3

Utilokasteinn · 2020-06-26 14:10:03 · 题解

P6242 【模板】线段树 3

题目简介

给你一个长度为 n 的序列 a。最开始令序列 b=a。

现在进行 m 次操作，分为 5 种：

• 1 l r k：将 a_l\sim a_r 加上 k。

• 2 l r v：将 a_l\sim a_r 对 v 取最小值。

• 3 l r：求 a_l\sim a_r 的和。

• 4 l r：求 a_l\sim a_r 的最大值。

• 5 l r：求 b_l\sim b_r 的最大值。

每次操作后令 b_{i}=\max(b_{i},a_{i}) 。

思路

前置知识：只要会写线段树 1。

吉司机线段树模版题，考虑用线段树维护。（大雾）

先讲一些基础的东西，会的可以直接跳到后面。

我们从线段树 1 开始。线段树 1 的操作就是操作 1 和 3。

先考虑解决操作 4，求区间最大值。

每个节点维护一个 \tt maxn 表示该节点表示的区间的最大值。

区间加时就直接把这个 \tt maxn 加上 k。标记下传的时候也是同理。查询的时候就方便了。

现在我们解决了操作 1,3 和 4。

接下来我们尝试解决操作 5。

先引入 2 个概念：

• 区间最（小/大）值操作：将 a_l\sim a_r 中的数 a_{i} 变为 \min(a_i,v) 或 \max(a_i,v)。

显然在这题中，b_i 就是 a_i 的历史最大值，操作 2 就是区间最小值操作，操作 5 是求区间最大历史最大值。

看完上面的定义后，再来尝试解决一下。

操作 5 的瓶颈在于区间加后无法快速更新序列 b。

因为一个区间总能被若干个点表示，我们先将一个区间先简化一个节点。

我们在区间加时，会对一个区间加上 k。

若 k>0，历史最大值可能被更新。

在 k=0，相当于什么也没做。

若 k<0，历史最大值不可能被更新。

想象一下我们正在对一个节点（不是任意区间）进行疯狂的区间加，此时也就是该节点的 \tt tag 在一直被改变。

经过一次加法，这个 \tt tag 可能变大（k>0），也可能变小（k<0）。

但是我们注意到，那么在标记下传前，当前节点的儿子的值是不会变的。

那么显然，当 \tt tag 达到最大时，下传的时候才可以使儿子达到当前最大。而只有当前最大才有可能更新历史最大。

假设这个这个 \tt tag 为 \tt tag1。

那么，我们只需要再设一个 \tt tag2 来表示没下传前的最大 \tt tag1，那么下传更新序列 b 就容易了。

注意下传时的顺序，要先更新 \tt maxb 再更新 \tt maxa，先更新 \tt tag2 再更新 \tt tag1。

可以过测试点 5 和 6 的代码，再往下就是完整的代码。

这里一定要理解透，不然后面肯定都看不懂。

接下来进入正题，如何解决操作 2。

容易发现这道题的瓶颈在于进行操作 2 后，无法快速更新信息，不仅区间历史最大值更新不了，甚至连区间和都不好更新。只能递归到叶子节点，然后对其取最小值，然后返回。

这样写单次修改的时间复杂度就会达到惊人的 \mathcal{O}(n)。

那怎么办呢？

线段树显然不能直接区间取 \min。

我们可以换一个思路，可以把区间内大于 v 的数都减去一个数，使得这些数都变为 v。

因为不同的数要减去不同的数才能等于 v，显然我们不能设很多 \tt tag 来表示区间内不同的数要减去的数。

那退一步来讲，若区间内大于 v 的数只有一种，我们可以怎么做呢？

只需要维护一个 \tt tag 就行了。

那怎样才能使得区间内大于 v 的数只有一种呢？

只需要多递归几次就行了。

我们在线段树每个节点设以下 3 个变量，分别为：

因为只有在区间只有一种数大于 k 的时候我们才能快速更新，即只能在满足 \tt se <k< \tt maxn 的节点上更新。

综上所述，解决方法就是在线段树中递归，直到该区间大于 v 的数只有一种就更新。

这样做总的时间复杂度为 \mathcal{O}(m\log^2n)，但我不会证。

因为有人说只需要设 3 个 \tt tag，这显然是不行的吧。所以再来说明一下为什么需要设 4 个 \tt tag。

在没有操作 2 的情况下，我们就设了 2 个 \tt tag，来维护整个区间。

现在加入了区间取 \min 操作。而区间取 \min 操作只会更新区间最大值。

那么我们就需要把最大值和非最大值分开来维护，故要设 4 个 \tt tag。

换句话说，如果不设 4 个 \tt tag，就更新不了非最大历史最大值的历史最大值了。

代码及其理解

首先说明，本题解主要以代码为主。个人认为代码写得很清晰，如果懂得上述思路就一定可以看懂。

先来看一下线段树每个节点需要存些什么。

以下是需要维护的 \tt tag：

具体地，\tt add3 是在未下传懒标记前最大的 \tt add1 的值，\tt add4 是在未下传懒标记前最大的 \tt add2 的值。

这 4 个 \tt tag 只要理解透了，代码就一定可以看得懂。

其他就简单了，具体详见代码。

这里需要注意，一个区间可能只有一种数，这样就没有区间严格次大值。这时我们需要给 \tt se 赋一个极小值。

建树代码如下：

struct segment_tree{
    ll sum;
    int l,r,maxa,cnt,se,maxb;
    int add1,add2,add3,add4;
}s[2000005];
inline void push_up(int p)
{
    s[p].sum=s[p*2].sum+s[p*2+1].sum;
    s[p].maxa=max(s[p*2].maxa,s[p*2+1].maxa);
    s[p].maxb=max(s[p*2].maxb,s[p*2+1].maxb);
    if(s[p*2].maxa==s[p*2+1].maxa)
    {
        s[p].se=max(s[p*2].se,s[p*2+1].se);
        s[p].cnt=s[p*2].cnt+s[p*2+1].cnt;
    }
    else if(s[p*2].maxa>s[p*2+1].maxa)
    {
        s[p].se=max(s[p*2].se,s[p*2+1].maxa);
        s[p].cnt=s[p*2].cnt;
    }
    else
    {
        s[p].se=max(s[p*2].maxa,s[p*2+1].se);
        s[p].cnt=s[p*2+1].cnt;
    }
}
void build(int l,int r,int p)
{
    s[p].l=l,s[p].r=r;
    if(l==r)
    {
        s[p].sum=s[p].maxa=s[p].maxb=read();
        s[p].cnt=1,s[p].se=-2e9;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    push_up(p);
}

查询与普通的线段树无异，注意求和要开 long long。

代码如下：

ll query_sum(int p)
{
    if(l>s[p].r||r<s[p].l)return 0;
    if(l<=s[p].l&&s[p].r<=r)return s[p].sum;
    push_down(p);
    return query_sum(p*2)+query_sum(p*2+1);
}
int query_maxa(int p)
{
    if(l>s[p].r||r<s[p].l)return -2e9;
    if(l<=s[p].l&&s[p].r<=r)return s[p].maxa;
    push_down(p);
    return max(query_maxa(p*2),query_maxa(p*2+1));
}
int query_maxb(int p)
{
    if(l>s[p].r||r<s[p].l)return -2e9;
    if(l<=s[p].l&&s[p].r<=r)return s[p].maxb;
    push_down(p);
    return max(query_maxb(p*2),query_maxb(p*2+1));
}

我们先来看一下修改时要如何维护 \tt tag 以及其信息。

先是区间加修改的代码：

void update_add(int p)
{
    if(l>s[p].r||r<s[p].l)return;
    if(l<=s[p].l&&s[p].r<=r)
    {
        s[p].sum+=1ll*k*s[p].cnt+1ll*k*(s[p].r-s[p].l+1-s[p].cnt);
        s[p].maxa+=k;
        s[p].maxb=max(s[p].maxb,s[p].maxa);
        if(s[p].se!=-2e9)s[p].se+=k;
        s[p].add1+=k,s[p].add2+=k;
        s[p].add3=max(s[p].add3,s[p].add1);
        s[p].add4=max(s[p].add4,s[p].add2);
        return;
    }
    push_down(p);
    update_add(p*2),update_add(p*2+1);
    push_up(p);
}

根据 \tt tag 的定义，不难写出以上代码。

就是不管最大值还是非最大值，都加上 k，维护一下区间和。

然后 \tt tag 也不需要管是否为最大值，都加上 k。

最后记录一下未下传前最大的 \tt tag 的值是多少。

接着就是区间取 \min 的代码：

void update_min(int p)
{
    if(l>s[p].r||r<s[p].l||v>=s[p].maxa)return;
    if(l<=s[p].l&&s[p].r<=r&&s[p].se<v)
    {
        int k=s[p].maxa-v;
        s[p].sum-=1ll*s[p].cnt*k;
        s[p].maxa=v,s[p].add1-=k;
        return;
    }
    push_down(p);
    update_min(p*2),update_min(p*2+1);
    push_up(p);
}

代码做的事大致就是，先递归到一个满足 \tt se <v< \tt maxa 的节点，然后将区间最大值都变为 v，更新区间和，区间最大值以及 \tt tag。

因为只修改最大值，所以只用更新 \tt add1。因为是取 \min，所以肯定不会更新历史最大值。

最后来看一下本题的难点，push_down 是如何下传懒标记。

先放上代码：

inline void change(int k1,int k2,int k3,int k4,int p)
{
    s[p].sum+=1ll*k1*s[p].cnt+1ll*k2*(s[p].r-s[p].l+1-s[p].cnt);
    s[p].maxb=max(s[p].maxb,s[p].maxa+k3);
    s[p].maxa+=k1;
    if(s[p].se!=-2e9)s[p].se+=k2;
    s[p].add3=max(s[p].add3,s[p].add1+k3);
    s[p].add4=max(s[p].add4,s[p].add2+k4);
    s[p].add1+=k1,s[p].add2+=k2;
}
inline void push_down(int p)
{
    int maxn=max(s[p*2].maxa,s[p*2+1].maxa);
    if(s[p*2].maxa==maxn)
        change(s[p].add1,s[p].add2,s[p].add3,s[p].add4,p*2);
    else change(s[p].add2,s[p].add2,s[p].add4,s[p].add4,p*2);
    if(s[p*2+1].maxa==maxn)
        change(s[p].add1,s[p].add2,s[p].add3,s[p].add4,p*2+1);
    else change(s[p].add2,s[p].add2,s[p].add4,s[p].add4,p*2+1);
    s[p].add1=s[p].add2=s[p].add3=s[p].add4=0;
}

看着就很恶心，但其实也不难。

push_down 中是判断该区间的最大值是否位于左区间或右区间，是就下传最大值的 \tt tag，否则就下传非最大值的 \tt tag。

change 就是下传 \tt tag 以及更新儿子的信息。根据各个 \tt tag 的定义都不难写出。

注意下传的顺序。

最后记得清空 \tt tag。

如果看不懂，就把测试点 5 和 6 的代码理解透彻了再来看。

注意事项&常数优化

1. 使用快读和快写。

2. 求和开 long long。

3. 只有求和才开 long long，其他用 int。这样可以比全用 long long 快半秒左右。

4. 递归的时候参数尽量少。

5. 用一个结构体来储存树的各种信息，这样空间访问较连续，速度较快。

6. 在建树的时候读入，可以一定的节省空间和时间。

7. 加一些函数前加 inline。

8. 修改时的更新可以用 change 代替，可以减少大量码量。

9. 注意更新顺序。

其他

最后附上 AC Code，在第一篇代码的下面。

参考资料：

• 灵梦の题解。

• 灵梦の洛谷日报。

• OI-Wiki。