浅谈 ST 表与二分的结合

· · 算法·理论

转载请在文章显著处注明出处。

前言

很久以前就有这个想法了,做了几道题发现没有题解这么写,便想把想法分享出来。

本篇文章修改记录:

主要算法

ST 表

P3865 【模板】ST 表

简单讲一下。以最小值为例。

ST 表是基于倍增思想的一种方法,适合 RMQ 问题。

定义 f_{i,j}[i,i+2^j-1] 这个区间的最小值,显然区间长度为 2^j。初始 f_{i,0}=a_i

预处理:将一个长度为 2^j 的一个区间分为两个长度为 2^{j-1} 的小区间,整个区间的最小值显然为两个小区间各自最小值的最小值。由此得到

f_{i,j}=\min(f_{i,j-1},f_{i+2^{j-1},j-1})
for (int j = 1; j <= 19; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = min (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

复杂度为 \mathcal O(n\log n)

查询:设查询的区间左端点为 l,右端点为 r。则可以将此区间分为两个长度为 \log(r-l+1) 的小区间(可能有重合,但不影响答案)。设 s=\log(r-l+1),得到区间 [l,r] 的最小值为 \min(f_{l,s},f_{r-2^s+1,s})

int ask (int l, int r) {
    int s = log2 (r - l + 1);
    return min (f[l][s], f[r - (1 << s) + 1][s]);
}

单次查询复杂度 \mathcal O(1)log2 函数较为高效,想要严格 \mathcal O(1) 可以预处理)。

二分查找

满足单调性即可进行二分查找,具体可见例题 P2249 【深基13.例1】查找。

结合

定义 f_{i,j}[i,i+2^j-1] 这个区间的最小值,发现 f_{i,j} 单调不增。由此可以与二分查找结合去做题。

[AGC005B] Minimum Sum

题意:给定数组 a,求 \displaystyle\ \sum_{i = 1}^n \sum_{j = i}^n \min_{i \leq k \leq j} a_k ,保证 A[1, n] 的正整数排列。

以该题作为例题进行讲解。

首先 \mathcal O(n\log n) 预处理出来 f_{i,j} 表示 [i,i+2^j-1] 这个区间中的最小值。

考虑每一个数 a_i 对答案的贡献。设以 a_i 为最小值的长度最大的区间的左端点为 L,右端点为 R。可以得到 a_i 对答案的贡献为 (i-L+1)\times (R-i+1)\times a_i

但是如何找到 LR 呢?

以找到 L 为例。设 \mathrm {ask}(x,i)[x,i] 这个区间的最小值(x\le i),发现 \mathrm {ask}(x,i) 单调不降,考虑从 i 往左边二分查找。如果 \mathrm {ask}(mid,i)<a_i,就让 l=mid+1,否则让 r=mid

找到 R 是同理的。然后就做完了。

时间复杂度 \mathcal O(n\log n)

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, f[N][22], ans;
int ask (int l, int r) { // 返回 [l,r] 的最小值
    int s = __lg (r - l + 1);
    return min (f[l][s], f[r - (1 << s) + 1][s]);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    memset (f, 0x3f, sizeof f);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> f[i][0];
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = min (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    for (int i = 1; i <= n; i++) {
        int l = 1, r = i, L, R;
        while (l < r) { // 向左查找
            int mid = (l + r) >> 1;
            if (ask (mid, i) == f[i][0]) r = mid;
            else l = mid + 1;
        }
        L = l, l = i, r = n;
        while (l < r) { // 向右查找
            int mid = (l + r + 1) >> 1;
            if (ask (i, mid) == f[i][0]) l = mid;
            else r = mid - 1;
        }
        R = l;
        ans += f[i][0] * (i - L + 1) * (R - i + 1); // 累加贡献
    }
    cout << ans;
    return 0;
}

[ABC140E] Second Sum

题意:给定一个长度为 n 的排列,对于 l<r,定义 f(l,r) 为区间 [l,r] 中的第二大数,求 \displaystyle\ \sum_{l=1}^{n-1}\ \sum_{r=l+1}^{n}f(l,r)

从上一道题中获取灵感。

考虑一个数 a_x (l\le x\le r) 在区间 [l,r] 中是第二大数有两种可能:

那就分两种情况统计,再累加贡献。

具体地,对于数 a_i,可以找到最大的区间 [l,r] 使得 a_i[l,r] 区间中最大的数。再找出最大的区间 [L,i] 使得 a_i 是该区间中第二大的数,和最大的区间 [i,R] 使得 a_i 是该区间中第二大的数。

那么 a_i 对于答案的贡献即为 a_i\times(l-L)\times (r-i+1)+a_i\times (i-l+1)\times (R-r)

那么难点在于如何找到 l,r,L,R

首先 [l,r] 可以简单地从 i 往两边二分找到,可以参照 AGC005B 的方法。根据定义,a_{l-1} > a_i,所以 L 可以通过在 [1,l-2] 上二分得到。具体地,需要找到 [1,l-2] 这个区间中从右边数第一个大于 a_i 的数。设 \mathrm {ask}(x,y)[x,y] 这个区间的最大值(x\le y),考虑从 y 往左边二分查找。如果 \mathrm {ask}(mid,y)<a_i,就让 r=mid,否则让 l=mid+1

区间最大值由 ST 表维护即可,时间复杂度 $\mathcal O(n\log n)$。 代码中细节还是挺多的,调不过的可以对比一下。 ```cpp // 为了看着方便,在每一次二分后空了一行 #include <bits/stdc++.h> #define int long long using namespace std; typedef long long LL; const int N = 1e6 + 10; int n, f[N][22], ans; int ask (int l, int r) { int s = __lg (r - l + 1); return max (f[l][s], f[r - (1 << s) + 1][s]); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> f[i][0]; for (int j = 1; j <= 19; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = max (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); for (int i = 1; i <= n; i++) { int l = 1, r = i, L, R, l1, r1; while (l < r) { int mid = (l + r) >> 1; if (ask (mid, i) == f[i][0]) r = mid; else l = mid + 1; } l1 = l; l = 1, r = max (1ll, l1 - 2); while (l < r) { int mid = (l + r) >> 1; if (ask (mid, max (mid, l1 - 2)) < f[i][0]) r = mid; else l = mid + 1; } if (f[r][0] > f[i][0] && f[r + 1][0] > f[i][0]) L = r + 1; else L = r; l = i, r = n; while (l < r) { int mid = (l + r + 1) >> 1; if (ask (i, mid) == f[i][0]) l = mid; else r = mid - 1; } r1 = l; R = l; ans += f[i][0] * (l1 - L) * (R - i + 1); // 左边第二大,右边第一大 l = min (n, r1 + 2), r = n; while (l < r) { int mid = (l + r + 1) >> 1; if (ask (min (mid, r1 + 2), mid) < f[i][0]) l = mid; else r = mid - 1; } if (f[l][0] > f[i][0] && f[l - 1][0] > f[i][0]) R = l - 1; else R = l; ans += f[i][0] * (i - l1 + 1) * (R - r1); // 左边第一大,右边第二大 } cout << ans; return 0; } ``` 大家对文章有什么好的建议欢迎在下面评论,有相关题目也可以提供,我会在修改时添加上贡献者,谢谢!