Day1 单调数据结构

提高1/2 单调数据结构

---

基本

单调数据结构，顾名思义具有单调性，比如说递增/递减。单调栈和单调队列秉持着如果一个人比你小，还比你强，那你就没用了的原则。

单调栈

以上午的模板题为例：

给出项数为 $n$ 的整数数列 $a_{1\dots n}$，定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 $f(i)=\min j(i<j\le n,a_j>a_i)$。若不存在，则 $f(i)=0$。

开一个单调栈，内部值单调递减；如果新进来一个值 $x$，当前栈顶 $top<x$，则说明 $x$ 就是 $top$ 后第一个比自己大的元素，并将其弹出；否则 $top$ 早就被计算答案后弹出了。重复这个过程直至栈空或 $top\ge x$ 后将 $x$​ 压入栈中。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 5;
int n,top,ans[maxn]; pair<int,int> st[maxn];
int main() {
    scanf("%d",&n);
    for (int i = 1,x;i <= n;i ++) {
        scanf("%d",&x);
        while (top && st[top].first < x)
            ans[st[top].second] = i, top --;
        st[++ top] = {x,i};
    }
    for (int i = 1;i <= n;i ++)
        printf("%d\n",ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

单调队列

对于单调队列相对复杂一些。仍以课上例题（简化后）为例：

给定一个长度为 $n$ 的数组 $a$，求其中每个长度为 $k$ 的区间中的最大值。

开一个单调队列，内部值单调递减；假设当前区间为 $[l,l+k-1]$，则这个队列中队头小于 $l$ 的元素对现在和以后的答案都不会产生影响，将它们出队；对于上一个区间 $[l-1,l+k-2]$ 而言多的元素为 $a_{l+k-1}$，如果队尾 $tail<a_{l+k-1}$，因为 $tail$ 比 $l+k-1$ 更加靠前，而值却不如后者大，则 $tail$ 就不会再影响后面的答案了，将 $tail$ 出队。重复这个过程直至队空或 $tail<a_{l+k-1}$ 后将 $a_{l+k-1}$ 入队。此时 $[l,l+k-1]$ 中的最大值即为队头 $head$（单调递减）。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 5;
int a[maxn],n,k,head = 1,tail = 0,q[maxn];
int main() {
    scanf("%d%d",&n,&k);
    for (int i = 1,x;i <= n;i ++) 
        scanf("%d",&a[i]);
    for (int i = 1;i <= n;i ++) {
        while (head <= tail && q[head] < i - k + 1) head ++;
        while (head <= tail && a[q[tail]] < a[i]) tail --;
        q[++ tail] = a[i];
        if (i >= k) printf("%d ",q[head]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

上午

【模板】单调栈

如上所述。

动物园的等待

很显然如果 $x$ 比 $y$ 高，且在 $y$ 的后面，则 $x$ 后的人都无法看到 $y$ 。所以考虑维护一个单调栈，栈中人的高度单调递减。每次进来一个人，其身高为 $h$ ，如果栈顶 $top<h$ ，那么只有这两个人是互相看得到的，而后面的人都会因为 $h$ 挡住而看不到 $top$，于是答案加一并将 $top$ 弹出；重复操作直到栈空或栈顶小于 $h$ ，此时如果栈不空，则这个人和 $top$ 是可以互相看到的，答案也加一。然后将 $h$ 压入栈中。

但细节部分还要考虑一种特殊情况：身高相等。身高相等的人互相都能看得到，而这些人可以对答案产生人数总和的贡献。所以可以把一群相邻的身高相等的一群人看作一个整体。令一群人共有 $siz$ 个人，如果他们被出栈了，则可以对答案产生 $siz$ 的贡献；而如果一个人被压入栈中后发现，栈中前一个元素是与自己身高相同的一群人（有 $siz$ 个人），则能对答案产生 $siz$ 的贡献。

可是如果发现自己前面是一群人但身高更高，则只能产生 $1$ 的贡献（因为两人中间的任何人都不能更高，也就是自己只能看到这群人中离自己最近的那个人）。

雨点

$O(n\log n)$ 做法

二分花盆长度 $W$ ，然后把雨点按照 $x$ 坐标排序，则 check 的部分即为求长度为 $W$ 的区间中最大值与最小值之差，并判断是否大于等于 $D$ 即可。用单调队列滑动窗口判最大 & 最小直接解决。

$O(n)$ 做法

考虑枚举并固定花盆左端点 $L$，从小到大枚举右端点 $R$，单调队列维护 $[L,R]$ 中雨滴 $y$ 坐标的最大/小值；如果发现某一时刻将 $R$ 加入单调队列中后，最大值减最小值大于等于 $D$ 了，即满足了题目的条件，则此时 $[L,R]$ 就是一个可能的答案；可此时如果用原来的 $L$ 继续把 $R$ 向后移，雨滴的最早/最晚落下的时间只会越来越长（不会更优），花盆长度也会越来越长。

假设当前左端点为 $L$，发现一个可行的右端点 $R$，那么对于将 $L+1$ 作为左端点，其右端点只会 $>R$（感性理解一下，否则当左端点为 $L$ 时直接选这个更靠前的 $R$ 作为右端点会更优）。然后时间复杂度就降到了 $O(n)$，$L,R$ 只会向右移。

// 核心部分，q 单调递增，q1 单调递减。
for (int L = 1;L <= n && R <= n;L ++) {
    while (l <= r && a[q[l]].x < a[L].x) l ++;
    while (l1 <= r1 && a[q1[l1]].x < a[L].x) l1 ++;
    for (;R <= n && a[q1[l1]].y - a[q[l]].y < d;R ++) {
        while (l <= r && a[q[r]].y >= a[R].y) r --;
        while (l1 <= r1 && a[q1[r1]].y <= a[R].y) r1 --;
        q[++ r] = q1[++ r1] = R;
    }
    if (a[q1[l1]].y - a[q[l]].y >= d)
        ans = min(ans,a[R - 1].x - a[L].x);
}
1
2
3
4
5
6
7
8
9
10
11
12

jxcakak

这题用二维线段树会 TLE70pts

单调队列做法即为：把每一行以每个点为起点，长度为 $n$ 的区间中的最大/小值先逐个用单调队列算下来；然后在列上再用单调队列去滑。码量特别大。所以不如二维st表，然后我就这么过了

泽泽在英国

显然如果以 $i$ 号建筑物的高度 $h_i$ 为矩形的宽，则矩形的长即为 $i$ 左右两边最近的比 $h_i$ 小的建筑物之间。然后就可以用单调栈维护了。可以两遍单调栈，也可以跑完一次后照着栈中剩余元素算出另一边。

下午

仓鼠窝

如果我们固定完整矩阵的右下角，则能产生贡献的矩阵会受到附近 $0$ 的影响；而如果靠左的 $0$ 比靠右的 $0$ 更高，则这个靠左的 $0$ 就不会成为决策点（当前不影响答案，毕竟矩形不能拐弯）。所以我们固定一个右下角，用单调栈维护比该点所在行高的，会对答案产生影响的 $0$ 的位置。设当前右下角为 $(u,v)$，一个可用的左上角为 $(x,y)$，则这个新矩阵对答案产生的贡献即为 $(x-u)\times (y-v)$。当然 $(u,v)$ 也可以直接继承在栈中自己下面那个点的答案，可以自行画图理解。

消防

~~根据课上的暴论，~~最终的链一定在树的直径上。因为对于树上的任意一点，距离其最远的点一定是直径上的点。所以就可以在直径上把长度 $\le s$ 的区间（链）用单调队列枚举。

考虑选定的一个区间（一条链），如何求其他所有点到这条链。我们设直径为 $u\to v$，当前枚举的链为 $[L,R]$。

• 对于直径上的点：显然 $u$ 和 $v$ （直径的两端）到达 $[L,R]$ 的距离是直径上点到 $[L,R]$ 的距离中最大的。可以用前缀和去维护这个两端的距离。
• 对于直径外的点：只有该点到 $[L,R]$ 上的某点 $x$ 的距离，是所有直径外的点到 $x$ 的距离中最大的时，该点才会可能对答案产生影响。可以先算出每个直径上的点距离其最远的点的距离 $dis$，然后开一个单调队列维护 $[L,R]$ 中 $dis$ 的最大值。
• 本轮答案即为上两种情况取较大值。

所以先跑出直径上的点（两遍 dfs 并记录每个直径点的父亲，后面滑动窗口时方便）；然后一遍 bfs 算出每个直径点在不经过其他直径点的情况下，能到的最远的点的距离；最后在直径上滑动窗口，如果 $[L,R]$ 中的距离（同样用前缀和）合法，那么就可以计算答案。

小奇探险

假设从前往后一次拿了 $t$ 个宝箱 $w_{1\dots t}$，则最终得到的价值即为：
$$w_1+(w_2\times k)+(w_3\times k^2)+\cdots +(w_t\times k^{t-1})$$
此时如果我们从 $w_t$ 从后往前推，设当前总价值为 $sum$，则在拿到 $w_t$ 时 $sum\leftarrow w_t$，但拿到 $w_{t-1}$ 时，我们就知道了 $w_t$ 之前至少拿了 $1$ 个宝箱，所以 $w_t$ 需要乘上一个 $k$，再加上 $w_{t-1}$，即 $sum\leftarrow sum\times k+w_{t-1}$。以此类推，当我们每从后往前拿一个宝箱时，$sum$ 都需要乘上 $k$ 再加上该宝箱的价值。

于是我们设 $f_i$ 表示当前从后往前扫到了第 $i$ 个宝箱时的最大价值，转移方程即为
f i = max ⁡ { f j × k + a i }   ( i < j ≤ i + m ) f_i=\max\{f_j\times k+a_i\}\ (i<j\le i+m) fi​=max{fj​×k+ai​} (i<j≤i+m)
可以发现 $k,a_i$ 均为定值，可以用单调队列维护出 $(i,i+m]$ 中 $f_j$ 的最大值。然后就没了。

股票交易

状态即为 $f_{i,j}$ 表示第 $i$ 天持有 $j$ 张股票。初始状态即为买多少花多少，不考虑前面的转移（其他买不到的为负无穷）。

转移分为三种情况：

• 啥都不干，即 $f_{i,j}\leftarrow f_{i-1,j}$。
• 之前交易过，现在买到了 $j$ 张：从 $(i-w-1)$ 天前，且那天持有 $k$ 张股票，进行转移，收益为 $-(j-k)\ast ap$，其中 $j-as\le k<j$。方程即为 $f_{i,j}=max(f_{i-w-1,k}-(j-k)\ast ap)$。
• 之前交易过，现在卖到了 $j$ 张：从 $(i-w-1)$ 天前，且那天持有 $k$ 张股票，进行转移，收益为 $(k-j)\ast bp$，其中 $j<k\le j+bs$。方程即为 $f_{i,j}=max(f_{i-w-1,k}+(k-j)\ast bp)$。

后两种情况方程可以转化为可以单调性优化的形式：

• $f_{i,j}=\max (f_{i-w-1,k}+k\ast ap)-j\ast ap(j-as\le k<j)$
• $f_{i,j}=\max (f_{i-w-1,k}+k\ast bp)-j\ast bp(j+bs\ge k>j)$

2,3 的转移顺序是相反的（状态之间的依赖关系相反）。

国旗计划

其实这题不需要用到单调数据结构

首先破环成链。因为各个区间不包含，所以在按照区间左端点排序后，右端点也是单调的。然后就可以用双指针求出每个区间后接的最优的区间。在知道每个区间的下一个区间后，就可以用倍增思想加速在环上跳的过程。对于 $[L,R]$ 这个区间必须选的情况下（已经破环成链），结束条件即为右端点 $\ge L+m$。答案记得 $+2$​。

课后题

排序游戏

因为所有操作的左端点都固定为 $1$，所以先操作的小区间会被后操作的大区间覆盖。所以我们用一个单调栈把无效操作全部去除，最终栈里剩下从上至下右端点单调递减的操作。没被操作过的部分不变，将原序列 $a$ 从小到大排序。我们按照栈中操作从下至上（也就是右端点逐渐变大）进行处理。每次就可以固定前后两个操作之间的值。

// 核心代码
for (int i = st[1].second + 1;i <= n;i ++) ans[i] = a[i]; // 没有产生变化的区间
nowr = st[1].second; // 上一个操作右端点
sort(a + 1,a + st[1].second + 1); 
for (int i = 1;i <= st[1].second;i ++) q[++ r] = a[i];
for (int i = 2;i <= top;i ++) {
    if (st[i - 1].first == 1) { // 这一段是升序，从头取
        for (int j = nowr;j > st[i].second;j --)
            ans[j] = q[r --];
    } else { // 这一段是降序，从尾取
        for (int j = nowr;j > st[i].second;j --)
            ans[j] = q[l ++];
    }
    nowr = st[i].second;
}
for (int i = nowr;i > 0;i --) // 最后剩下的
    ans[i] = q[st[top].first == 1 ? r -- : l ++];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

信号传输/魔王降临

开了题解视频了所以偷个懒