「2026 杭电多校 3」1007. rains
https://acm.hdu.edu.cn/contest/problem?cid=1231&pid=1007
有一排相连的 n 块石头,第 i 块石头的高度为 h_i。每当下雨时的水位高度 H 大于 h_i 时,第 i 块石头就会被淹没。所有露出的石头会形成若干个连续段。
有 Q 次询问,每次询问给出 l, r,你需要求出:只考虑区间 [l, r] 内的石头,当使得露出的石头形成至少 k 个连续段时,下雨的水位 H 最高是多少。
数据范围:1 \leq n, Q, k \leq 10^6,1 \leq h_i \leq 10^6,1 \leq l \leq r \leq n。
时空限制:5s / 512MiB。
Solution
首先,连续段数量关于水位不单调,无法二分答案。
当水位为 H 时,第 i 块石头露出当且仅当 h_i \geq H。从高到低枚举水位 H,当一个询问的连续段个数第一次 \geq k 时,当前的水位 H 即为答案。
若某个小区间 [l_2, r_2] 被大区间 [l_1, r_1] 包含(即 l_1\leq l_2 \leq r_2 \leq r_1),则在任意时刻,小区间的连续段数都不超过大区间。在大区间找到答案之前,小区间肯定也找不到答案。
所以暂时只需要考虑那些极大的,不被其他区间包含的区间,我们称这一类询问为“活跃区间”。每次找到某个活跃区间的答案时,收集新产生的活跃区间。
活跃区间在排序后一定满足 l, r 均严格升序。这方便我们统计一次修改对活跃区间的影响。不妨一开始将所有询问按照 l 升序、r 降序进行排序,将排序后的次序记作每个询问的编号。那么活跃区间在编号递增的同时也满足 l, r 递增。
使用一个线段树按照排序后的询问编号,维护所有询问当前的连续段数(其实只维护了活跃区间的真实值,非活跃区间的值暂且记作 -\infty)。每次将一个点 p 从淹没改成露出时,影响到的活跃区间的编号是一段区间。具体地,先排除掉活跃区间 l = r 的情况,剩余情况大致分为三段区间:
- 活跃区间以 p 为右端点:此时若 p - 1 没有露出,则这一类询问的连续段数 +1。
- 活跃区间完全包含 p(即 l < p < r):
- p - 1 和 p + 1 均没有露出,则这一类询问的连续段数 +1。
- p - 1 和 p + 1 均已经露出,则这一类询问的连续段数 -1。
- 其余情况,这一类询问的答案不变。
- 活跃区间以 p 为左端点:此时若 p + 1 没有露出,则这一类询问的连续段数 +1。
所以每次修改对活跃区间的贡献,都可以使用线段树区间加实现。
处理完同一高度的所有修改后,不断地检查线段树的最大值是否 \geq k。若某个活跃区间找到了答案,就要去收集删除当前活跃区间后所产生的新活跃区间,新活跃区间需要初始化其当前的连续段数,所以我们还需要额外使用一个树状数组,快速计算一个区间当前的连续段数。
将所有询问按照 l 升序、r 降序进行排序,一个尚未回答的询问是活跃区间,当且仅当其右端点严格大于它前面所有尚未回答的询问的右端点(即其右端点为严格前缀最大值)。
当一个活跃区间得到答案并被删除后,只有它与下一个活跃区间之间的询问可能变成活跃区间。
额外使用一个线段树,支持查询一个前缀内右端点最大的询问。从右往左处理,每次找到当前前缀内右端点最大的询问,将其加入活跃区间。然后继续考察其编号左侧的询问,不断重复该过程,直到找到的询问位于被删除询问的编号左侧。这样筛选出的询问,恰好为这段范围内所有右端点为严格前缀最大值的询问,即为新活跃区间。
时间复杂度 \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;
}