自动搬运

查看原文

来自洛谷，原作者为

	BigSmall_En time舟从此逝，code海寄余生

搬运于2025-08-24 22:35:15，当前版本为作者最后更新于2022-07-14 13:16:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$

题解

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

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

• $maxv$：即线段树上该线段覆盖的所有数的最大值。
• $tag$：维护区间加的懒标记，表示这个节点内的每个数 $+c$，但子树并没有更新这一信息。
• $ctag$：维护区间取 $\min$ 的懒标记，表示这个节点内的每个数对 $h$ 取 $\min$，但子树暂无更新此信息。
• $btag$：维护区间取 $\max$ 的懒标记，表示这个节点内的每个数对 $h$ 取 $\max$，但子树暂无更新此信息。

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$

$maxv\gets \min(maxv,h)$ 和 $ctag\gets \min(ctag,h)$ 比较好理解。

对于 $btag$ 而言，如果 $btag>h$，那么取 $\max$ 变大的值也会对 $h$ 取 $\min$。如果 $btag<h$ 那么取 $\max$ 变大的值也不会因为对 $h$ 取 $\min$ 收到影响。（感觉在说废话，其实也很好理解）

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;
}

完整代码就不贴了。

后记

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

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