# CSP-S 2024 真题：物理条件区间化与双序列状态压缩

## 本节目标

学习把连续运动判定转成测速仪下标区间，并把两种颜色的完整历史压成“当前颜色末值 + 另一颜色末值”。

## 前置知识与课前自测

前置：二分、区间刺点贪心、动态规划、Lazy 全局加思想。

1. 匀加速下速度平方关于位置是怎样的函数？
2. 两种颜色序列中，处理新值时未来还关心每种颜色的哪些信息？

<details><summary>答案</summary>

1. $v^2(x)=v_0^2+2a(x-d)$，对位置单调。
2. 各颜色最后一个值；更早历史已经结算完得分。

</details>

## 问题动机

《超速检测》若按每车逐监测器模拟会产生二次量访问，《染色》若把两个序列的选择进度全放进状态又会得到平方状态。两题的降维分别来自“物理不等式在单调位置上形成区间”与“下一步只与已取元素的边界色有关”。

## 精选例题 1：超速检测

### 来源、题意与范围

- [洛谷-P11232 超速检测](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P11232)
- 每组 $n,m\le10^5$，车辆匀加速向北、测速仪位置有序；先求会被全部仪器检测的车数，再求保证都仍被检测时最多关闭多少仪器。

<details><summary>Hint 1：避免浮点</summary>在位置 p 比较 `v_i^2 + 2*a_i*(p-d_i) > V^2`。</details>
<details><summary>Hint 2：每辆车对应什么</summary>由于速度平方单调，能检测它的测速仪下标构成一个连续区间。</details>
<details><summary>Hint 3：保留最少测速仪</summary>转成用最少点刺中全部区间，按右端点贪心。</details>

### Observations

- 加速度正、零、负分别产生后缀、全后缀/空、有限前缀区间，但统一为检测器下标区间。
- 严格“超过”要求使用 `>`，速度恰等于限速不能计入。
- 第二问只关心每辆已检测车至少留下一个命中仪器，是经典区间刺点。

### Editorial 与证明

对每辆车先找第一个不小于驶入位置的测速仪，再按加速度与整数速度平方不等式二分区间另一端。非空区间计入检测车辆。将区间按右端点排序；若上次保留点不在当前区间，就保留当前右端点。

区间右端点是当前及以后所有可选点中最早的，不会比任何其他选择减少覆盖后续区间的机会；交换可得到存在最优方案选它。故保留点数最小，关闭数为 m 减它。

复杂度 $O((n+m)\log n)$。

### 核心伪代码与附件

```text
for each car:
    derive detector-index interval where speed_squared(position) > limit_squared
sort nonempty intervals by right endpoint
last = none; kept = 0
for [l,r]:
    if last < l: keep detector r; last=r; kept++
output interval_count, m-kept
```

[完整 C++17 附件](../../参考实现/12-历年真题/洛谷-P11232.cpp)

## 精选例题 2：染色

### 来源、题意与范围

- [洛谷-P11233 染色](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P11233)
- $n\le2\times10^5$，每个正整数染红/蓝；若它与同色前一个数相等则获得该值，最大化总分。

<details><summary>Hint 1：两条子序列</summary>红蓝染色等价于把原序列分到两个保持顺序的子序列。</details>
<details><summary>Hint 2：利用颜色对称</summary>令当前元素总在“活动颜色”末尾，状态只记录另一颜色末值。</details>
<details><summary>Hint 3：全体状态同加</summary>若下一值等于当前值，继续活动颜色让所有状态统一加该值；切换颜色只更新一个状态。</details>

### Observations

- 朴素状态 `(lastRed,lastBlue)` 是值域平方；颜色交换对称可固定一边末值为当前元素。
- 新值放当前颜色时，另一末值不变且全部 DP 状态加同一奖励。
- 新值放另一颜色后，新的“另一末值”统一变成旧当前值；只需用全局最优或旧另一末值等于新值的状态更新一个点。

### Editorial

处理到 i，设当前活动颜色末值为 $A_i$，`dp[x]` 表示另一颜色末值为 x 的最优分。维护所有 `dp` 的全局加量与基值最大值。到新值 y：切换颜色候选为 `max(globalBest, dp[y]+y)`；继续当前颜色若 y 等于旧当前值则给所有状态加 y；最后用切换候选点更新状态 `oldCurrent`。

### 正确性证明

任一染色方案在处理前缀后可交换红蓝名称，使当前元素属于活动颜色，故状态无损。下一元素只有继续或切换两种，转移完全覆盖。继续奖励只由 y 与旧当前值决定，切换奖励只由 y 与另一末值决定，因此聚合公式精确。

每步 $O(1)$，空间 $O(\max A_i)$。

### 核心伪代码与附件

```text
dp[empty_other] = 0; current = A[1]; global_add = 0
for y in A[2:]:
    switch_value = max(best_dp + global_add, dp[y] + global_add + y)
    if y == current: global_add += y
    dp[current] = max(dp[current], switch_value - global_add)
    current = y
answer = best_dp + global_add
```

[完整 C++17 附件](../../参考实现/12-历年真题/洛谷-P11233.cpp)

## 实现指南

《超速检测》先在 128 位整数中解速度平方不等式，再用两次二分将实数/整数边界落到监测器下标；贪心覆盖时按区间右端排序。《染色》的状态中要明确“上一个取自哪个序列”，相同位置色值不能代替来源维度；转移时使用新层数组，防止一个元素在同层被取多次。

## 扩展与联系

超速检测把连续实数运动压成离散区间；染色把两维历史压成一个值与全局偏移。两者都先找单调/对称结构，再选择数据结构。

## 总结与自检

1. 减速车辆为什么仍是连续检测区间？
2. 区间刺点为何按右端点？
3. 染色状态中的颜色交换为什么安全？
4. 切换转移为何只更新 `oldCurrent` 状态？

## 课后训练建议

物理题用离散时间模拟小数据；染色题枚举 $2^n$ 染色对拍，覆盖连续相等、全不同、零状态不存在等情况。