CF484E 题解

很好的数据结构题，加深了蒟蒻对于可持久化线段树的理解。

题意

给定一个序列 \(\{a_n\}\) ( \(1 \le n \le 10^5, 1 \le a_i \le 10^9\) )，有 \(m\) ( $ \le m \le 10^5$ ) 个询问，每次询问给出 \(l, r, k\)，表示询问区间 \([l, r]\) 里长度为 \(k\) 的子区间的最小值最大是多少。

题解

看到最小值最大，考虑二分答案，根据 middle 那道题的套路，将 \(\ge mid\) 的数在原序列中赋值成 \(1\)，\(< mid\) 的数在原序列中赋值成 \(0\)。于是问题转化成了：判断区间 \([l, r]\) 中有没有一个长度为 \(k\) 的子区间，满足这个子区间内的数全为 \(1\)。

这个东西不太能离线做，因为要二分。考虑在线回答，这就显然要用到可持久化线段树了。

这个时候就很容易被套路给误导了，去想该如何主席树求解这个问题，像 HH 的项链 那道题一样维护 \(pre\)，但发现是要求一个区间里面的东西，这不太好维护。实际上，可持久化线段树的不同版本不一定只建立在序列的下标上，也可以建立在权值上，这道题中，第 \(i\) 个版本的线段树维护 \(\ge i\) 的数的最长连续子段即可，也就是类似 小白逛公园 那道题一样。二分到 \(mid\) 时，查询第 \(mid\) 棵线段树中区间 \([l, r]\) 的最长连续子段长度是否 \(\ge k\) 即可。

代码很好写，时间复杂度 \(O(n \log^2 n)\)，code:

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define re(i, n) for (int i = 0; i < n; ++i)
#define pe(i, n) for (int i = n - 1; i >= 0; --i)
#define bg begin()
#define ed end()
#define alls(a) a.bg, a.ed
using namespace std;
using i64 = long long;
const int N = 1E5 + 5;
int n, m, a[N], tot, root[N];
struct segt {
    int ls[N << 5], rs[N << 5];
    struct node {
        int lb = 0, rb = 0;
        int len = 0, mx = 0;
    } t[N << 5];
    friend node operator+(node a, node b) {
        node c;
        c.len = a.len + b.len;
        c.lb = (a.len == a.lb ? a.len + b.lb : a.lb);
        c.rb = (b.len == b.rb ? b.len + a.rb : b.rb);
        c.mx = max({a.mx, b.mx, a.rb + b.lb});
        return c;
    }
    void pull(int x) {t[x] = t[ls[x]] + t[rs[x]];}
    void build(int &x, int l, int r) {
        x = ++tot;
        if (l == r) {t[x].len = 1; return ;}
        int mid = (l + r) / 2;
        build(ls[x], l, mid);
        build(rs[x], mid + 1, r);
        pull(x);
    }
    void insert(int &p, int q, int l, int r, int pos) {
        t[p = ++tot] = t[q]; ls[p] = ls[q]; rs[p] = rs[q];
        if (l == r) {t[p].lb = t[p].rb = t[p].mx = 1; return ;}
        int mid = (l + r) / 2;
        if (pos <= mid) insert(ls[p], ls[q], l, mid, pos);
        else insert(rs[p], rs[q], mid + 1, r, pos);
        pull(p);
    }
    node query(int x, int l, int r, int L, int R) {
        if (r < L || l > R || !x) return node {};
        if (l >= L && r <= R) return t[x];
        int mid = (l + r) / 2;
        return query(ls[x], l, mid, L, R) + query(rs[x], mid + 1, r, L, R);
    }
    int query(int v, int L, int R) {return query(v, 1, n, L, R).mx;}
} t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n; rep(i, 1, n) cin >> a[i];
    vector<array<int, 2>> v(n + 1);
    rep(i, 1, n) v[i] = {a[i], i};
    sort(v.bg + 1, v.ed);
    t.build(root[n + 1], 1, n);
    per(i, n, 1) t.insert(root[i], root[i + 1], 1, n, v[i][1]);
    cin >> m; while (m--) {
        int l, r, k; cin >> l >> r >> k;
        int L = 1, R = n;
        while (L < R) {
            int mid = (L + R + 1) / 2;
            if (t.query(root[mid], l, r) >= k) L = mid;
            else R = mid - 1;
        }
        cout << v[L][0] << '\n';
    }
}