ST表维护区间次大值

Whitely · 2023-10-01 10:47:54 · 个人记录

• 直接合并可能会出现的问题

  1 2 3 2 1

  查询此区间时需要将前四个和后四个的答案合并，两个子区间最大值和次大值均为 3 和 2，直接合并会统计两次 3，则区间次大值也会更新为3。

  具体地，若区间最大值仅出现一次且在前后两个区间的重叠部分，会统计两次，次大值会计算错误。

• 解决方法

  我们只需要判断最大值的出现次数是否为1即可，则考虑记录区间最大值最左和最右出现的位置，判断是否相等即可，仅当不相等时将次大值更新为最大值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, H = 20;
int f[N][H], f1[N][H], l[N][H], r[N][H];
void init(int n) {
    for (int j = 1; j < H; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            int t = i + (1 << (j - 1)), fl = f[i][j - 1], fr = f[t][j - 1];
            f[i][j] = max(fl, fr);
            if (fl == fr) l[i][j] = l[i][j - 1], r[i][j] = r[t][j - 1];
            else if (fl > fr) l[i][j] = l[i][j - 1], r[i][j] = r[i][j - 1];
            else l[i][j] = l[t][j - 1], r[i][j] = r[t][j - 1];
            f1[i][j] = max(f1[i][j - 1], f1[t][j - 1]);
            if (fl != fr) f1[i][j] = max(f1[i][j], min(fl, fr));
        }
    }
}
typedef pair<int, int> pii;
pii qry(int x, int y) {
    int t = log2(y - x + 1), tt = y - (1 << t) + 1, fl = f[x][t], fr = f[tt][t];
    int max1 = max(fl, fr), max2 = max(f1[x][t], f1[tt][t]);
    if (fl != fr) max2 = max(max2, min(fl, fr));
    bool mul_max1 = 0;
    if (fl == fr) mul_max1 = l[x][t] != r[tt][t];
    else if (fl > fr) mul_max1 = l[x][t] != r[x][t];
    else mul_max1 = l[tt][t] != r[tt][t];
    if (mul_max1) max2 = max1;
    return {max1, max2};
}
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> f[i][0], l[i][0] = r[i][0] = i;
    init(n);
    while (q--) {
        int x, y; cin >> x >> y;
        pii t = qry(x, y); cout << t.first << ' ' << t.second << '\n';
    }
    return 0;
}