LG8024 题解

· · 题解

LG8024 [ONTAK2015] Stumilowy sad 题解

因为不会势能分析，不知道大部分题解的方法的复杂度是多少，于是写了一个严格 O(n\log n) 的做法。

此外，这题不区间加和维护区间最大值的话就是这题。

题意

一个长度为 n 的序列 a。进行 4 种操作

  • 操作 1 ：将 [l,r] 的所有数 +c
  • 操作 2 ：将 [l,r] 的所有数对 h 取 \min
  • 操作 3 ：将 [l,r] 的所有数对 h 取 \max
  • 操作 4 ：查询 [l,r] 内数的最大值
1\leq n\leq 5\times 10^5,1\leq a_i\leq 10^9,0\leq |c|\leq 500,1\leq h\leq 10^9

题解

对于这种题目一般考虑使用线段树。

对于线段树上的每一个节点，维护以下四个信息：

1.建树

初始时所有节点的 ctag=+\infty,btag=-\infty，比较好理解。

void buildtree(int p,int l,int r){
    t[p].left=l,t[p].right=r;//我的习惯写法，维护线段两端的位置，比较常规
    t[p].ctag=INF,t[p].btag=-INF;
    if(l==r){t[p].maxv=a[l];return;}
    int mid=(l+r)>>1;
    buildtree(ls,l,mid);buildtree(rs,mid+1,r);
    pushup(p);
}

2.区间加

因为每个数都加 c，所以即使之前所有的数都对 h 取了最大值或最小值，现在这个最大值或最小值也变成了 h+c。对于下传标记，就相当于都 +c。

inline void pushtag(int p,ll x){
    t[p].maxv+=x;t[p].tag+=x;
    if(t[p].ctag<INF)t[p].ctag+=x;
    if(t[p].btag>-INF)t[p].btag+=x;
}
void update_plus(int p,int l,int r,ll c){
    if(l<=t[p].left&&t[p].right<=r)
        return pushtag(p,c),void();
    pushdown(p);
    if(l<=t[ls].right)update_plus(ls,l,r,c);
    if(r>=t[rs].left)update_plus(rs,l,r,c);
    pushup(p);
}

3.区间取 \min

对于 $btag$ 而言，如果 $btag>h$，那么取 $\max$ 变大的值也会对 $h$ 取 $\min$。如果 $btag<h$ 那么取 $\max$ 变大的值也不会因为对 $h$ 取 $\min$ 收到影响。（感觉在说废话，其实也很好理解） ```cpp inline void pushctag(int p,ll x){ t[p].maxv=min(t[p].maxv,x); t[p].btag=min(t[p].btag,x); t[p].ctag=min(t[p].ctag,x); } void update_cut(int p,int l,int r,ll h){ if(l<=t[p].left&&t[p].right<=r) return pushctag(p,h); pushdown(p); if(l<=t[ls].right)update_cut(ls,l,r,h); if(r>=t[rs].left)update_cut(rs,l,r,h); pushup(p); } ``` #### 4.区间取 $\max

原理和区间取 \min 类似。

inline void pushbtag(int p,ll x){
    t[p].maxv=max(t[p].maxv,x);
    t[p].btag=max(t[p].btag,x);
    t[p].ctag=max(t[p].ctag,x);
}
void update_build(int p,int l,int r,ll h){
    if(l<=t[p].left&&t[p].right<=r)
        return pushbtag(p,h);
    pushdown(p);
    if(l<=t[ls].right)update_build(ls,l,r,h);
    if(r>=t[rs].left)update_build(rs,l,r,h);
    pushup(p);
}

5.上传信息

inline void pushup(int p){
    t[p].maxv=max(t[ls].maxv,t[rs].maxv);
}

6.下传标记

原理就是用父亲节点的标记对子节点的每种信息分别进行修改，和修改操作相同，所以子操作也可以用三个修改函数（分别对应更新 tag,ctag,btag）来写，这样子代码量会大大减少，也会清晰很多。

inline void pushdown(int p){
    pushtag(ls,t[p].tag);pushtag(rs,t[p].tag);
    pushbtag(ls,t[p].btag);pushbtag(rs,t[p].btag);
    pushctag(ls,t[p].ctag);pushctag(rs,t[p].ctag);
    t[p].tag=0,t[p].btag=-INF,t[p].ctag=INF;
}

7.查询最大值

ll query_max(int p,int l,int r){
    if(l<=t[p].left&&t[p].right<=r)
        return t[p].maxv;
    pushdown(p);ll tmp=-INF;
    if(l<=t[ls].right)tmp=max(tmp,query_max(ls,l,r));
    if(r>=t[rs].left)tmp=max(tmp,query_max(rs,l,r));
    return tmp;
}

完整代码就不贴了。

后记

之前题解有些地方格式和内容写错了，现已修改。

同时把代码改成了使用函数完成对信息的修改，这样更加简洁。