首先是数学表达这道题
考虑第 \(i\) 个怪物。
它跑完自己的全程扣得血是：
\[\sum\min\{c_j,m_{j,lst} + \Delta t \times r_j\}
\]
\(\min\) 有点难搞，没啥好性质。
考虑拆开为两个部分：
\[\sum c_j + \sum (m_{j,lst} + \Delta t \times r_j) = \sum c_j + \sum m_{j,lst} + \sum \Delta t \times r_j
\]
且取用的部分都与 \(\Delta t\) 有关，当 \(\Delta t \geq \frac{c_j}{r_j}\) 时取用 \(c_j\)，反之亦然。
有上式可以想到二分，若前缀关于上式的值小于 \(h\) 则可取，反之亦然。
这样维护前缀的上式即可。
不想打主席树怎么办？分块处理。
维护块中上式，对于三种情况：
-
非全零块暴力
-
全零块 \(O(1)\) 计算。
-
未能抹平块暴力。
均摊 \(O(n\sqrt{n})\)
#include <bits/stdc++.h>
#define int long long
const int maxn = 4e5;
using namespace std;
int s, n, q;
#define getbl(x) (x - 1) / s + 1
#define getbll(x) (x - 1) * s + 1
#define getblr(x) x *s
#define forbl(i, bl) for (int i = getbll(bl); i <= min(n, getblr(bl)); i++)
int c[maxn + 5], r[maxn + 5], m[maxn + 5];
int t[maxn + 5], h[maxn + 5];
int mxt;
int d[maxn + 5];
signed main() {
freopen("dinosaurs.in", "r", stdin);
freopen("dinosaurs.out", "w", stdout);
scanf("%lld", &n);
s = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &c[i], &r[i]);
m[i] = c[i];
}
scanf("%lld", &q);
for (int i = 1; i <= q; i++) {
scanf("%lld%lld", &t[i], &h[i]);
}
t[0] = 0;
int ed = getbl(n);
mxt = t[q];
for (int i = 1; i <= ed; i++) {
memset(d, 0, sizeof d);
int j, k;
forbl(j, i) {
d[1] += r[j];
if(c[j] / r[j] > maxn)continue;
d[c[j] / r[j] + 1] -= r[j];
if (c[j] % r[j]) {
d[c[j] / r[j] + 1] += c[j] % r[j];
d[c[j] / r[j] + 2] -= c[j] % r[j];
}
}
for (j = 1; j <= maxn; j++) {
d[j] += d[j - 1];
}
for (j = 1; j <= maxn; j++) {
d[j] += d[j - 1];
}
int lst = 0;
bool tag = 0;
for (j = 1; j <= q; j++) {
if (!h[j])
continue;
if (!tag) {
forbl(k, i) { m[k] = min(m[k] + (t[j] - t[lst]) * r[k], c[k]); }
bool clr = true;
forbl(k, i) {
int ct = min(h[j], m[k]);
h[j] -= ct;
m[k] -= ct;
if (m[k])
clr = false;
}
if (clr)
tag = 1;
} else {
int dt = t[j] - t[lst];
if (h[j] >= d[dt]) {
h[j] -= d[dt];
} else {
forbl(k, i) { m[k] = min(m[k] + dt * r[k], c[k]); }
bool clr = true;
forbl(k, i) {
int ct = min(h[j], m[k]);
h[j] -= ct;
m[k] -= ct;
}
tag = 0;
}
}
lst = j;
}
}
int ans = 0;
for (int i = 1; i <= q; i++) {
ans += h[i];
}
printf("%lld", ans);
}