题目描述
小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 \(L\) 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。
这个周末，主干道上预计出现 \(n\) 辆车，其中第 \(i\) 辆车从主干道上距离最南端 \(d_i\) 的位置驶入，以 \(v_i\) 的初速度和 \(a_i\) 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 \(v_i > 0\)，但 \(a_i\) 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 \(L\) 的位置）或速度降为 \(0\)（这只可能在 \(a_i < 0\) 时发生）时，我们认为该车驶离主干道。
主干道上设置了 \(m\) 个测速仪，其中第 \(j\) 个测速仪位于主干道上距离最南端 \(p_j\) 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速 \(V\)，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 \(n\) 辆车中会有多少辆车被判定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 \(n\) 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。
由于 \(n\) 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。
如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。
对于所有测试数据，保证：
- \(1 \leq T \leq 20\)；
- \(1 \leq n, m \leq 10^5\)，\(1 \leq L \leq 10^6\)，\(1 \leq V \leq 10^3\)；
- \(0 \leq d_i < L\)，\(1 \leq v_i \leq 10^3\)，\(|a_i| \leq 10^3\)；
- \(0 \leq p_1 < p_2 < \dots < p_m \leq L\)。
solution
速度是单调的，可以对每个车二分得到它在什么路程区间上是超速的。使用以下公式：
- 当一辆车的初速度为 \(v_0\)、加速度 \(a \neq 0\)，做匀加速运动，则当它的位移（即行驶路程）为 \(s\) 时，这辆车的瞬时速度为 \(\sqrt{v_0^2+2\times a\times s}\)。
为避免根号的误差，可以对两边平方。注意这个路程区间的两端只需要取到整数。
后面的部分我写了单调队列优化 dp。\(f_i\) 表示最后一个选上的灯是第 \(i\) 盏，转移首先计算 \(maxl=\max_{[l, r], r< pos_i}l\)，注意不被任何灯抓到的车不能计算贡献，然后 \(f_i=1+\min_{maxl\leq pos_j}f_j\)。有一些神经病的边界问题都可用 \(minl\) 判断。然后这个东西可以单调队列优化。我写的复杂度是 \(O(n(\log n+\log L))\)。
code
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#define endl "\n"
#endif
using LL = long long;
struct range {
int l, r;
bool operator<(const range& rhs) const { return r < rhs.r; }
};
int n, m, V, L;
LL calc(LL s, LL v0, LL a) { return v0 * v0 + 2 * a * s; }
int mian() {
cin >> n >> m >> L >> V;
LL V2 = 1ll * V * V;
vector<range> vec;
for (int i = 1; i <= n; i++) {
int d, v0, a;
cin >> d >> v0 >> a;
if (a > 0) {
if (calc(L - d, v0, a) > V2) {
int l = d, r = L, ans = L;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(mid - d, v0, a) > V2) ans = mid, r = mid - 1;
else l = mid + 1;
}
vec.push_back({.l = ans, .r = L});
}
} else if (a == 0) {
if (v0 > V) vec.push_back({.l = d, .r = L});
} else {
if (v0 > V) {
int l = d, r = L, ans = d;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(mid - d, v0, a) > V2) ans = mid, l = mid + 1;
else r = mid - 1;
}
vec.push_back({.l = d, .r = ans});
}
}
}
#ifdef LOCAL
for (auto rg : vec) debug("%d %d\n", rg.l, rg.r);
#endif
sort(vec.begin(), vec.end());
vector<int> pos(m);
for (int i = 0; i < m; i++) cin >> pos[i];
vector<int> f(m, 1e9);
auto it = vec.cbegin();
int minl = -1;
vector<int> q(m);
int l = 0, r = -1, ans1 = 0, ans2 = n;
vector<range> dec;
for (int i = 0; i < m; i++) {
while (it != vec.cend() && it->r < pos[i]) {
if (i && it->l <= pos[i - 1]) minl = max(minl, it->l), ++ans1, dec.push_back(*it);
++it;
}
while (l <= r && pos[q[l]] < minl) ++l;
if (minl == -1) f[i] = 1;
if (l <= r) f[i] = min(f[q[l]] + 1, f[i]);
while (l <= r && f[q[r]] >= f[i]) --r;
q[++r] = i;
debug("f[%d] = %d\n", i, f[i]);
}
while (it != vec.cend()) {
if (it->l <= pos.back()) minl = max(minl, it->l), ++ans1, dec.push_back(*it);
++it;
}
for (int i = 0; i < m; i++) if (pos[i] >= minl) ans2 = min(ans2, f[i]);
if (minl == -1) ans2 = 0;
cout << ans1 << " " << m - ans2 << endl;
return 0;
}
int main() {
#ifndef LOCAL
#ifdef NF
freopen("detect.in", "r", stdin);
freopen("detect.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int t;
cin >> t;
while (t--) mian();
return 0;
}