#题解#洛谷P7167 喷泉#ST表#区间最值#

P7167 [eJOI 2020] Fountain (Day1) - 洛谷

分析

1. 由于喷泉确定，比第i个盘子大的第一个盘子nxt i 是确定的。我们由ST表维护nxt i 。

2. 最终落入第几个盘子的答案显然单调，我们进行二分。nxt i j 表示i后面第 j+1个盘子，对 j 二分

代码实现

#include<bits/stdc++.h>
#define int  long long
#define endl '\n'
using namespace std;
const int N = 1e6+10;
int n, q, d[N], c[N], rmax[N][20], f[N][20], g[N][20], log_2[N];
int query_max(int a, int b)
{int x = log_2[b - a + 1];return max(rmax[a][x], rmax[b - (1 << x) +1][x]);
}
signed main()
{ios::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];for (int i = 2; i <= n; i++)log_2[i] = log_2[i >> 1] + 1;for (int i = 1; i <= n; i++)rmax[i][0] = d[i];for (int j = 1; (1 << j) <= n; j++)for (int i = 1; i <= n - (1 << j) +1; i++)rmax[i][j] = max(rmax[i][j - 1],rmax[i + (1 << (j - 1))][j - 1]);c[n + 1] = 1e9;d[n + 1] = 1e9;for (int i = 1; i < n; i++){int l = i + 1, r = n + 1, mid;while (l < r){mid = (l + r ) >> 1;if (query_max(i + 1, mid) <= d[i])l = mid + 1;elser = mid;}f[i][0] = l;//下一个盘子的编号g[i][0] = c[f[i][0]];//下一个盘子的容量}for (int t = 1; t <= 16; t++)for (int i = 1; i <= n; i++){f[i][t] = f[f[i][t - 1]][t - 1];//i后第2^t个盘子g[i][t] = g[i][t - 1] + g[f[i][t - 1]][t - 1];}while (q--){int r, v;cin >> r >> v;if (v > c[r]){v -= c[r];for (int t = 16; t >= 0; t--)if (v > g[r][t]){v -= g[r][t];r = f[r][t];}r = f[r][0];}if (r == n + 1) r = 0;cout << r << endl;}return 0;
}