「2026 杭电多校 3」1007. rains

    「2026 杭电多校 3」1007. rains

    https://acm.hdu.edu.cn/contest/problem?cid=1231&pid=1007

    有一排相连的 nn 块石头,第 ii 块石头的高度为 hih_i。每当下雨时的水位高度 HH 大于 hih_i 时,第 ii 块石头就会被淹没。所有露出的石头会形成若干个连续段。

    有 QQ 次询问,每次询问给出 l,rl, r,你需要求出:只考虑区间 [l,r][l, r] 内的石头,当使得露出的石头形成至少 kk 个连续段时,下雨的水位 HH 最高是多少。

    数据范围:1≤n,Q,k≤1061 \leq n, Q, k \leq 10^6,1≤hi≤1061 \leq h_i \leq 10^6,1≤l≤r≤n1 \leq l \leq r \leq n。

    时空限制:55s / 512512MiB。

    Solution

    首先,连续段数量关于水位不单调,无法二分答案。

    当水位为 HH 时,第 ii 块石头露出当且仅当 hi≥Hh_i \geq H。从高到低枚举水位 HH,当一个询问的连续段个数第一次 ≥k\geq k 时,当前的水位 HH 即为答案。

    若某个小区间 [l2,r2][l_2, r_2] 被大区间 [l1,r1][l_1, r_1] 包含(即 l1≤l2≤r2≤r1l_1\leq l_2 \leq r_2 \leq r_1),则在任意时刻,小区间的连续段数都不超过大区间。在大区间找到答案之前,小区间肯定也找不到答案。

    所以暂时只需要考虑那些极大的,不被其他区间包含的区间,我们称这一类询问为“活跃区间”。每次找到某个活跃区间的答案时,收集新产生的活跃区间。

    活跃区间在排序后一定满足 l,rl, r 均严格升序。这方便我们统计一次修改对活跃区间的影响。不妨一开始将所有询问按照 ll 升序、rr 降序进行排序,将排序后的次序记作每个询问的编号。那么活跃区间在编号递增的同时也满足 l,rl, r 递增。

    使用一个线段树按照排序后的询问编号,维护所有询问当前的连续段数(其实只维护了活跃区间的真实值,非活跃区间的值暂且记作 −∞-\infty)。每次将一个点 pp 从淹没改成露出时,影响到的活跃区间的编号是一段区间。具体地,先排除掉活跃区间 l=rl = r 的情况,剩余情况大致分为三段区间:

    • 活跃区间以 pp 为右端点:此时若 p−1p - 1 没有露出,则这一类询问的连续段数 +1+1。
    • 活跃区间完全包含 pp(即 l<p<rl < p < r):
      • p−1p - 1 和 p+1p + 1 均没有露出,则这一类询问的连续段数 +1+1。
      • p−1p - 1 和 p+1p + 1 均已经露出,则这一类询问的连续段数 −1-1。
      • 其余情况,这一类询问的答案不变。
    • 活跃区间以 pp 为左端点:此时若 p+1p + 1 没有露出,则这一类询问的连续段数 +1+1。

    所以每次修改对活跃区间的贡献,都可以使用线段树区间加实现。

    处理完同一高度的所有修改后,不断地检查线段树的最大值是否 ≥k\geq k。若某个活跃区间找到了答案,就要去收集删除当前活跃区间后所产生的新活跃区间,新活跃区间需要初始化其当前的连续段数,所以我们还需要额外使用一个树状数组,快速计算一个区间当前的连续段数。

    如何收集新活跃区间?

    将所有询问按照 ll 升序、rr 降序进行排序,一个尚未回答的询问是活跃区间,当且仅当其右端点严格大于它前面所有尚未回答的询问的右端点(即其右端点为严格前缀最大值)。

    当一个活跃区间得到答案并被删除后,只有它与下一个活跃区间之间的询问可能变成活跃区间。

    额外使用一个线段树,支持查询一个前缀内右端点最大的询问。从右往左处理,每次找到当前前缀内右端点最大的询问,将其加入活跃区间。然后继续考察其编号左侧的询问,不断重复该过程,直到找到的询问位于被删除询问的编号左侧。这样筛选出的询问,恰好为这段范围内所有右端点为严格前缀最大值的询问,即为新活跃区间。

    时间复杂度 O((n+Q)log⁡(n+Q))\mathcal{O}((n + Q)\log(n + Q))。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int inf = 0x3f3f3f3f;
    
    const int N = 1000100, MaxQ = 1000100;
    
    const int V = 1e6;
    const int MaxV = V + 10;
    
    int n, Q, k;
    std::vector<int> pos[MaxV];
    
    int up[N];
    
    struct Query {
        int l, r, id;
    } qry[MaxQ];
    
    namespace SGT {
        struct node {
            std::pair<int, int> info;
            int add;
            void mk_add(int x) {
                info.first += x;
                add += x;
            }
        } t[MaxQ * 4];
    
        void upd(int p) {
            t[p].info = std::max(t[p * 2].info, t[p * 2 + 1].info);
        }
    
        void spread(int p) {
            if (t[p].add) {
                t[p * 2].mk_add(t[p].add), t[p * 2 + 1].mk_add(t[p].add);
                t[p].add = 0;
            }
        }
    
        void build(int p, int l, int r) {
            t[p].info = {-inf, l}, t[p].add = 0;
            if (l == r) return;
            int mid = (l + r) >> 1;
            build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
        }
    
        void addRange(int p, int l, int r, int s, int e, int x) {
            if (s <= l && r <= e) {
                t[p].mk_add(x);
                return;
            }
            spread(p);
            int mid = (l + r) >> 1;
            if (s <= mid) {
                addRange(p * 2, l, mid, s, e, x);
            }
            if (mid < e) {
                addRange(p * 2 + 1, mid + 1, r, s, e, x);
            }
            upd(p);
        }
        void addRange(int s, int e, int x) {
            if (s <= e) {
                addRange(1, 1, Q, s, e, x);
            }
        }
    
        void change(int p, int l, int r, int x, int y) {
            if (l == r) {
                t[p].info.first = y;
                return;
            }
            spread(p);
            int mid = (l + r) >> 1;
            if (x <= mid) {
                change(p * 2, l, mid, x, y);
            } else {
                change(p * 2 + 1, mid + 1, r, x, y);
            }
            upd(p);
        }
        void change(int x, int y) {
            change(1, 1, Q, x, y);
        }
    }
    
    struct Key {
        int r, p;
        bool operator < (const Key &rhs) const {
            return r != rhs.r ? r < rhs.r : p > rhs.p;
        }
    };
    namespace Find {
        Key t[MaxQ * 4];
    
        void upd(int p) {
            t[p] = std::max(t[p * 2], t[p * 2 + 1]);
        }
    
        void build(int p, int l, int r) {
            if (l == r) {
                t[p] = {qry[l].r, l};
                return;
            }
            int mid = (l + r) >> 1;
            build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
            upd(p);
        }
    
        void change(int p, int l, int r, int x, int y) {
            if (l == r) {
                t[p].r = y;
                return;
            }
            int mid = (l + r) >> 1;
            if (x <= mid) {
                change(p * 2, l, mid, x, y);
            } else {
                change(p * 2 + 1, mid + 1, r, x, y);
            }
            upd(p);
        }
        void change(int x, int y) {
            change(1, 1, Q, x, y);
        }
    
        auto ask(int p, int l, int r, int s, int e) {
            if (s <= l && r <= e) {
                return t[p];
            }
            int mid = (l + r) >> 1;
            if (s <= mid && mid < e) {
                return std::max(ask(p * 2, l, mid, s, e), ask(p * 2 + 1, mid + 1, r, s, e));
            }
            if (s <= mid) {
                return ask(p * 2, l, mid, s, e);
            } else {
                return ask(p * 2 + 1, mid + 1, r, s, e);
            }
        }
        auto ask(int s, int e) {
            return s <= e ? ask(1, 1, Q, s, e) : Key(0, 0);
        }
    }
    
    int ans[MaxQ];
    
    namespace BIT {
        int c[N];
    
        void add(int x, int y) {
            for (; x <= n; x += x & -x) {
                c[x] += y;
            }
        }
    
        int ask(int x) {
            int ans = 0;
            for (; x; x -= x & -x) {
                ans += c[x];
            }
            return ans;
        }
    
        int ask(int l, int r) {
            return up[l] + ask(r) - ask(l);
        }
    }
    
    std::set<std::pair<int, int>> lp, rp; // lp: {左端点, 询问编号},rp: {右端点, 询问编号}
    
    void add(int i) {
        lp.insert({qry[i].l, i});
        rp.insert({qry[i].r, i});
        SGT::change(i, BIT::ask(qry[i].l, qry[i].r));
    }
    void del(int i) {
        lp.erase({qry[i].l, i});
        rp.erase({qry[i].r, i});
        SGT::change(i, -inf);
        Find::change(i, -inf);
    
        auto it = lp.lower_bound({qry[i].l, 0});
        int R = it != lp.end() ? it->second : (Q + 1);
    
        Key cur = Find::ask(1, R - 1);
        while (cur.p && cur.p > i) {
            add(cur.p);
            cur = Find::ask(1, cur.p - 1);
        }
    }
    
    void insert(int p) {
        up[p] = 1;
    
        int l = rp.lower_bound({p, 0})->second;
        int r = (-- lp.lower_bound({p + 1, 0}))->second;
        int L = rp.lower_bound({p + 1, 0})->second;
        int R = (-- lp.lower_bound({p, 0}))->second;
    
        if (l == r && qry[l].l == qry[l].r) {
            SGT::addRange(l, r, 1);
        } else {
            if (up[p - 1] && up[p + 1]) {
                SGT::addRange(L, R, -1);
            }
            if (!(up[p - 1] || up[p + 1])) {
                SGT::addRange(L, R, +1);
            }
            if (!up[p - 1]) {
                SGT::addRange(l, L - 1, +1);
            }
            if (!up[p + 1]) {
                SGT::addRange(R + 1, r, +1);
            }
        }
    
        if (p > 1 && up[p - 1] == 0) {
            BIT::add(p, +1);
        }
        if (p < n && up[p + 1] == 1) {
            BIT::add(p + 1, -1);
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n >> Q >> k;
    
        for (int i = 1; i <= n; i ++) {
            int h;
            std::cin >> h;
            pos[h].push_back(i);
        }
    
        for (int i = 1; i <= Q; i ++) {
            std::cin >> qry[i].l >> qry[i].r;
            qry[i].id = i;
        }
    
        std::sort(qry + 1, qry + 1 + Q, [&] (auto lhs, auto rhs) -> bool {
            return lhs.l != rhs.l ? lhs.l < rhs.l : lhs.r > rhs.r;
        });
    
        SGT::build(1, 1, Q);
        Find::build(1, 1, Q);
        rp = {{n + 1, Q + 1}}, lp = {{0, 0}};
    
        for (int i = 1, mr = 0; i <= Q; i ++) {
            if (mr >= qry[i].r) {
                continue;
            }
            mr = qry[i].r;
    
            SGT::change(i, 0);
            lp.insert({qry[i].l, i});
            rp.insert({qry[i].r, i});
        }
    
        for (int h = V; h >= 1; h --) {
            for (int p : pos[h]) {
                insert(p);
            }
    
            // debug(SGT::t[1].info.first) << '\n';
            while (SGT::t[1].info.first >= k) {
                int i = SGT::t[1].info.second;
                ans[qry[i].id] = h;
                del(i);
            }
        }
    
        for (int i = 1; i <= Q; i ++) {
            std::cout << (ans[i] ? ans[i] : -1) << '\n';
        }
    
        return 0;
    }