思路与算法

用v²+2a(p-d)>V²整数判超速，根据加速度正负二分得到每车可捕获的测速仪下标区间。统计非空区间，然后按右端排序，贪心选右端点覆盖所有区间，最多关闭数为m减最少保留数。

正确性说明

对已驶入位置p>=d，瞬时速度平方为v²+2a(p-d)，大于V²等价超速；当a为负时能超速必然尚未停车。随p单调，超速的测速仪构成一个连续下标区间，二分精确取得端点。每辆原本能被捕获的车对应一个需至少保留一个点的区间。按右端最小区间选择其右端点，任何覆盖该区间的选择都可交换成该右端而不失去对后续区间的覆盖，所以贪心保留最少。

复杂度

每组O(n log m+n log n+m)时间、O(n+m)空间，含车辆、测速仪、区间数组初始化和排序；T<=20。

易错点

严格超过V才超速，等于不算；测速仪位于驶入/驶出点也会检测，负加速度停车之后不能捕获，而速度平方大于V²已经排除了停车后。所有乘法用64位，不计算平方根。若没有车被检测，所有测速仪均可关闭。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        long long L, V;
        cin >> n >> m >> L >> V;
        vector<array<long long, 3>> a(n);
        for (auto &v : a)
            for (auto &x : v)
                cin >> x;
        vector<long long> p(m);
        for (auto &x : p)
            cin >> x;
        vector<pair<int, int>> seg;
        for (auto c : a) {
            long long d = c[0], v = c[1], acc = c[2];
            int l = lower_bound(p.begin(), p.end(), d) - p.begin(), rr = m - 1;
            if (l == m)
                continue;
            auto fast = [&](int i) {
                return v * v + 2 * acc * (p[i] - d) > V * V;
            };
            if (acc >= 0) {
                int lo = l, hi = m;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    if (fast(mid))
                        hi = mid;
                    else
                        lo = mid + 1;
                }
                l = lo;
            } else {
                if (!fast(l))
                    continue;
                int lo = l, hi = m;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    if (fast(mid))
                        lo = mid + 1;
                    else
                        hi = mid;
                }
                rr = lo - 1;
            }
            if (l <= rr)
                seg.push_back({rr, l});
        }
        sort(seg.begin(), seg.end());
        int last = -1, used = 0;
        for (auto z : seg)
            if (last < z.second) {
                last = z.first;
                used++;
            }
        cout << seg.size() << " " << m - used << "\n";
    }
}