「2026 杭电多校 3」1007. rains

发表于 分类于 本文字数： 1.8k 阅读时长 ≈ 2 分钟

Description

Link：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))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
#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;
}