题解：P7167 [eJOI 2020 Day1] Fountain
观察本题题干，发现制约水最终的去处的为盘子的直径与容量。若对于每次询问，都直接暴力计算，显然会超时。于是想到一种能够减少判断次数，又不影响结果的方法—倍增。
首先预处理出从第 $i$ 个圆盘开始连续 $2^j$ 个圆盘中的最大直径，记为 $pre_{i,j}$。显然 $\forall i \in [1,n],pre_{i,0} = d_i$。然后就是倍增求最值的过程，这里就不赘述了。然后给出 $f_{i,j},g_{i,j}$，分别表示从 $i$ 开始水溢出 $2^j$ 次后所到达的圆盘与求水溢出所到达的 $2^j$ 个圆盘的容量之和。
但是现在还有一个问题，如果每次遍历去求第 $i$ 个圆盘再加入水后，最终能流到的圆盘，会额外产生 $O(N)$ 的复杂度，加上对所有圆盘的求解以及预处理后的查询，会达到 $O(N^2 \log N)$ 的复杂度，无法通过此题。不难发现，这其实存在单调性，因此使用二分答案去求解。设预处理的查询函数为 query (l,r)，则有满足 query(i + 1,(l + r) >> 1) <= d[i] 的时候更新左端点为 l = ((l + r) >> 1) + 1，否则为 r = (l + r) >> 1。在得到答案 $l$ 后，就可以根据变量设置的含义去更新 $f_{i,0},g_{i,0}$，有 $f_{i,0} = l,g_{i,0} = c_{f_{i,0}}$。
由于 $N_{\max} = 10^5$，所以本题解将两个数组设置为 f[100005][20],g[100005][20]。则对于 $f_{i,j},g_{i,j}$ 的转移有：
1
2
3
| for (int j = 1;j < 20;++j)
for (int i = 1;i <= n;++i)
f[i][j] = f[f[i][j - 1]][j - 1],g[i][j] = g[f[i][j - 1]][j - 1] + g[i][j - 1];
|
最后就是求解的部分了。考虑到题目存在流到最终的水池的情况，所以我们可以再加入一个容积为 $\inf$ 的圆盘。对于每一组的询问，首先判断水能否溢出，若可以，则利用倍增进行处理直至无法溢出，最后特判到达底盘的情况即可。
最后利用倍增的时间复杂度为 $O(n \log n)$。完整代码如下：
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,d[MAX],c[MAX];
int pre[MAX][20],f[MAX][20],g[MAX][20];
int query (int x,int y);
int main ()
{
n = read ();m = read ();
for (int i = 1;i <= n;++i) d[i] = read (),c[i] = read ();
for (int i = 1;i <= n;++i) pre[i][0] = d[i];
for (int j = 1;(1 << j) <= n;++j)
for (int i = 1;i + (1 << j) - 1 <= n;++i)
pre[i][j] = max (pre[i][j - 1],pre[i + (1 << (j - 1))][j - 1]);
c[n + 1] = INF;f[n][0] = n + 1;g[n][0] = c[f[n][0]];
for (int i = 1;i < n;++i)
{
int l = i + 1,r = n + 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (query (i + 1,mid) <= d[i]) l = mid + 1;
else r = mid;
}
f[i][0] = l;
g[i][0] = c[f[i][0]];
}
for (int j = 1;j < 20;++j)
for (int i = 1;i <= n;++i)
f[i][j] = f[f[i][j - 1]][j - 1],g[i][j] = g[f[i][j - 1]][j - 1] + g[i][j - 1];
for (int i = 1;i <= m;++i)
{
int x = read (),y = read ();
if (y > c[x])
{
y -= c[x];
for (int j = 19;j >= 0;--j)
if (y > g[x][j]) y -= g[x][j],x = f[x][j];
x = f[x][0];
}
printf ("%d\n",x == (n + 1) ? 0 : x);
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
int query (int x,int y)
{
int k = (int) log2 (y - x + 1);
return max (pre[x][k],pre[y - (1 << k) + 1][k]);
}
|
