题目
luogu P7167 Fountain
思路
分析题目，我们发现需要找到某一圆盘之后第一个比该圆盘大的圆盘，那么我们可以维护一个单调栈来进行预处理，保存每个圆盘对应的下一个圆盘
我们维护一个递减序列，在进行弹栈时，记录下弹出的元素对应的当前即将入栈元素，即弹栈元素对应的第一大圆盘
最后，将栈里剩下的元素对应第一大元素设定为地盘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void find_max() { // 递减序列
for (int i = 1; i <= N; i++) {
while (!stk.empty() && D[i] > D[stk.back()]) {
st[stk.back()][0] = i;
sum[stk.back()][0] = C[i];
stk.pop_back();
}
stk.push_back(i);
}
while (!stk.empty()) {
st[stk.back()][0] = 0; // 0 代表水池
stk.pop_back();
}
}
|
同时，我们最后需要进行批量的查询操作，联想到RMQ问题，我们使用st 表将查询操作的时间复杂度降至O(1)
st[stk.back()][0] = i;和st[stk.back()][0] = 0; // 0 代表水池将 st 表初始化，st[i][j]表示第 i 个圆盘跳 1 >> j 步后盘子的编号
这里 1 >> j 步指有效步数，即直接跳至下一个下一个水流流到的圆盘
自然而然，得到 st 表的递推公式st[i][j] = st[st[i][j - 1]][j - 1];
1
2
3
4
5
6
7
| void pre_rmq() {
for (int j = 1; (1 << j) <= N; j++)
for (int i = 1; i + (1 << j) <= N; i++) {
st[i][j] = st[st[i][j - 1]][j - 1];
sum[i][j] = sum[i][j - 1] + sum[st[i][j - 1]][j - 1];
}
}
|
最后处理查询，根据水量来一步步跳到正确的位置，区别于模板的RMQ问题，这里的查询时间复杂度会略大于 O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int query(int r, int val) { // query是查询的意思
if (C[r] >= val)
return r;
val -= C[r];
for (int i = 18; i >= 0; i--)
if (st[r][i] != 0 && val > sum[r][i]) {
val -= sum[r][i];
r = st[r][i];
}
return st[r][0];
}
|
可以看出，为了根据水量查询，我们定义了 sum 数组来统计区间内的出水总量
实现
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
| #include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
// 单调栈+st表
int N, Q;
int D[100005], C[100005];
int st[100005][30], sum[100005][30];
// sum是区间水量 st是从i跳1>>j步后盘子的编号
vector<int> stk;
void find_max() { // 递减序列
for (int i = 1; i <= N; i++) {
while (!stk.empty() && D[i] > D[stk.back()]) {
st[stk.back()][0] = i;
sum[stk.back()][0] = C[i];
stk.pop_back();
}
stk.push_back(i);
}
while (!stk.empty()) {
st[stk.back()][0] = 0; // 0 代表水池
stk.pop_back();
}
}
void pre_rmq() {
for (int j = 1; (1 << j) <= N; j++)
for (int i = 1; i + (1 << j) <= N; i++) {
st[i][j] = st[st[i][j - 1]][j - 1];
sum[i][j] = sum[i][j - 1] + sum[st[i][j - 1]][j - 1];
}
}
int query(int r, int val) { // query是查询的意思
if (C[r] >= val)
return r;
val -= C[r];
for (int i = 18; i >= 0; i--)
if (st[r][i] != 0 && val > sum[r][i]) {
val -= sum[r][i];
r = st[r][i];
}
return st[r][0];
}
int main() {
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++)
cin >> D[i] >> C[i];
find_max();
pre_rmq();
for (int i = 1; i <= Q; i++) {
int r, v;
cin >> r >> v;
cout << query(r, v) << endl;
}
return 0;
}
|
