题解：P11232 [CSP-S 2024] 超速检测（民间数据）

跟物理啥的没任何关系啦，题面给的一坨公式是为了让你看懂样例解释，虽然我没看。

我知道后面的贪心是经典问题。但是我不会于是自己造了个别的贪心。

## Description

一条长度为 $L$ 的道路上，有 $n$ 辆车和 $m$ 个测速仪。其中：

- 第 $i$ 辆车将从 $d_i$ 的位置出现，以 $v_i$ 的初速度和 $a_i$ 的加速度从左向右做匀加速运动。
- 第 $i$ 个测速仪在 $p_i$ 的位置。

若车 $i$ 经过某个测速仪 $j$ 时，其瞬时速度（$\sqrt {v_i^2 + 2a_is}$，其中 $s$ 为位移，即 $s = p_j - d_i$）大于 $V$，则车 $i$ 被判定为超速。若一辆车没有被任何一个测速仪判定为超速，它就没有超速。

求：

- 有多少辆车被判定为超速；
- 最多删掉多少个测速仪，能使得每辆车的超速情况都不发生改变。（实际上就是 $n - $ 最少保留几个。）

$1 \le n,m \le 10^5$，$1 \le L \le 10^6$。

## Solution

先考虑如何快速搞定第一问，即判断车 $i$ 能否被任意一个测速点判定为超速。

设 $f(i)$ 表示车 $i$ 在测速点 $f(i)$ 时速度**最大**，显然 $f(i) \in [1, m]$。那么车 $i$ 在任意一个测速点被判定超速，等价于 $\sqrt {v_{f(i)}^2 + 2a_{f(i)}(p_{f(i)}-d_i)} > V$。于是我们考虑求解所有 $f(i)$。

不妨对 $a_i$ 的正负分类讨论。

$$
f(i) = \begin{cases}
m & a_i \ge 0 \\
\min\limits_{p_j\ge i}j & a_i < 0
\end{cases}
$$

原因？

- $a_i \ge 0$，即速度越来越快。那么路程越远速度越大，而最远的测速点是 $m$。
- $a_i < 0$，即速度越来越慢。那么路程越短速度越大，而最近的测速点是 $\min\limits_{p_j\ge i}j$。

后者可以二分快速求解。于是第一问的复杂度我们可以做到 $\mathcal O(n \log n)$。

考虑第二问。

有了上面的思考，不难发现能将车 $i$ 判定为超速的测速仪是一段区间。具体地，当 $a_i \ge 0$ 时是一段以 $f(i)$ 为结尾的区间，当 $a_i < 0$ 时是一段以 $f(i)$ 为开头的区间。而这个区间的另一个端点可以通过二分求出。

我们将这些区间 $([l_1,r_1],[l_2,r_2],\dots,[l_m,r_m])$ 求出来后，问题变成了：

- 求在 $[1, n]$ 中最少选几个整数，能使得对于所有区间 $[l_i,r_i]$，都存在一个选择的整数 $j \in [l_i, r_i]$。

首先如果存在 $[l_i,r_i] \subseteq [l_j,r_j]$（即 $l_j \le l_i \le r_i \le r_j$），那么 $[l_j,r_j]$ 的存在是没有意义的。因为当区间 $i$ 覆盖一个整数时区间 $j$ 也一定覆盖了，但反过来不一定。

于是我们可以把像这样的“大区间 $j$”取出来删掉。此时剩下的区间就会满足：

- 左端点 $l$ 互不相同。
- 将所有区间按照左端点 $l$ 排序后，右端点 $r$ 严格递增。

显然考虑这样一种贪心策略：

- 首先将所有区间按照左端点 $l$ 排序。
- 从左往右扫描每个区间 $i$。如果当前区间 $i$ 已经覆盖了某个选择的整数那么忽略其不管。否则选择整数 $r_i$。

正确性显然。总复杂度 $\mathcal O(n \log n)$。

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long ll;

int n, m, L, V;

struct Car {
	int d, v, a;
}car[N];

int pos[N];

bool chk(int x, int y) {
	if (car[x].d > pos[y]) return false;
	int s = pos[y] - car[x].d;
	int a = car[x].a, v = car[x].v;
	return v * v + 2 * a * s > V * V;
}

struct Seg {
	int l, r;
}p[N];
int cnt;

bool st[N];

pair<int, int> solve() {
	cin >> n >> m >> L >> V;
	
	for (int i = 1; i <= n; ++ i ) {
		cin >> car[i].d >> car[i].v >> car[i].a;
	}
	
	for (int i = 1; i <= m; ++ i ) {
		cin >> pos[i];
	}
	
	cnt = 0;
	for (int i = 1; i <= n; ++ i )
		if (car[i].d <= pos[m]) {
			int l, r;
			
			if (car[i].a >= 0) {
				r = m;
				if (!chk(i, r)) continue;
				
				int lo = 1, hi = m;
				while (lo <= hi) {
					int mid = lo + hi >> 1;
					if (chk(i, mid)) {
						l = mid;
						hi = mid - 1;
					} else {
						lo = mid + 1;
					}
				}
			} else {
				l = lower_bound(pos + 1, pos + m + 1, car[i].d) - pos;
				if (!chk(i, l)) continue;
				
				int lo = l, hi = m;
				while (lo <= hi) {
					int mid = lo + hi >> 1;
					if (chk(i, mid)) {
						r = mid;
						lo = mid + 1;
 					} else {
 						hi = mid - 1;
 					}
				}
			}
			
			p[ ++ cnt] = {l, r};
		}
	
	sort(p + 1, p + cnt + 1,
		[&](Seg x, Seg y) {
			return x.l == y.l ? x.r > y.r : x.l < y.l;
		});
	
	int mn_r = 1e9;
	for (int i = cnt; i; -- i )
		if (p[i].r < mn_r) {
			st[i] = true;
			mn_r = p[i].r;
		} else {
			st[i] = false;
		}
	
	int res = 0;
	int lst = -1;
	
	for (int i = 1; i <= cnt; ++ i ) {
		if (st[i] && p[i].l > lst) {
			res ++ ;
			lst = p[i].r;
		}
	}
	
	return {cnt, m - res};
}

signed main() {
	int T;
	cin >> T;
	while (T -- ) {
		auto t = solve();
		cout << t.first << ' ' << t.second << '\n';
	}
	return 0;
}
```

正在渲染内容...