[yLOI2023] D 腐草为萤
一扶苏一
·
·
题解
[yLOI2023] D 腐草为萤
这个题上线前经过了巨大削弱，导致结论变得很一眼，可能对思维量的要求变弱了。
Description
数轴上有 n 个点，每个点的初始坐标为 x_i，权重为 a_i。在任何时刻，每个点会向与它相邻的两个点中权重较大的那个点移动，速度为一个单位长度每秒，如果相邻两个点的权重都比它自身权重小，则不移动。两个点相遇时，权重较小的点消失。
求出每个点消失时的坐标。
## Analysis
### 算法一
$n = 2$ 时只要比较两个点谁权重大即可，一定是权重较小的走到权重较大的然后去世。期望得分 $5$ 分。
### 算法二
当 $n \leq 100$，$x_i \leq 200$ 时，显然每隔 $200$ 秒至少会有一个点消失。于是逐秒模拟即可。时间复杂度 $O(n x_i)$，期望得分 $30$ 分。
### 算法三
找到离得最近的一对相邻点 $(i,j)$，使得一方静止，另一方在朝着对方移动。容易发现，在 $(i,j)$ 发生碰撞之前，其他点不会发生碰撞。于是可以直接把时间跳到 $(i,j)$ 碰撞的时刻，容易算出此时其他所有点的坐标：在这个过程中，其他点的运动方向和速度都是不变的，所以假设经过了 $T\mathrm s$ 发生碰撞，则一个 $T \mathrm s$ 前向右运动的点 $i$ 的新坐标就是 $x_i + T$。向左运动同理。暴力修改仍存活的点的坐标。每次修改 $O(n)$ 个点，一共修改 $O(n)$ 次。时间复杂度为 $O(n^2)$。期望得分 $60$ 分。
### 算法四
$a_i$ 单调递增的情况：除了最后一个点，所有的点都向右移动。因为点的移动速度是一样的，所以移动方向相同的两个点的间距是不会变的，不会发生碰撞。大家最后都会和 $n$ 号点碰撞，然后去世。
时间复杂度 $O(n)$，期望得分 $5$ 分。结合算法三可得 $65$ 分。
### 算法五
$a_i$ 单峰的情况：类似的，所有点都会朝着权值最大的点移动，且同向的两个点间距不变。最后大家都和权重最大的点碰撞，去世。
时间复杂度 $O(n)$，期望得分 $5$ 分。结合算法三、四可得 $70$ 分。
### 算法六
结合算法三、四、五，我们尝试分析运动的形式，得出 key conclusion：
1. 相邻两个同向运动的点（在一方方向改变前）的间距不会改变。
2. 发生一次碰撞后，**至多只有两个点的运动方向会改变**。
3. 只有运动方向不同的两个点（把静止也看做一个运动方向）会发生碰撞。
第一条显然，考虑证明第二条：假设 $j,i,k$ 是三个相邻的点，某一时刻 $i$ 碰撞到了 $j$。此时与 $j$ 相邻和与 $k$ 相邻的点发生了变化（从 $k$ 变成 $i$ 或从 $j$ 变成 $i$），因此可能导致 $j$ 和 $k$ 的运动方向改变。对 $j$ 左侧和 $k$ 右侧的点而言，与它们相邻的点没有改变，所以它们的运动方向不会改变。
结合第三条，我们考虑维护所有运动方向不同的相邻点对。那么一次碰撞后，只需要对点对做出 $O(1)$ 个修改就能得到新的状态。根据算法三，在任何时刻，最先发生碰撞的一定是离得最近的点对，我们按时间顺序维护每次碰撞。
每次碰撞是找间距最小的两个点对，于是需要一个支持插入、删除、查找最小值的数据结构。可以使用 `std::set` 或者 `std::priority_queue`。以下约定使用 `std::set`。
我们需要能找出这些点对里当前间距最小的，这个点对会最先发生碰撞。这里产生了一个问题：每个点对的间距是在加入 set 的时刻计算的。当时间增加时，不可能暴力修改 set 里点对的距离。那么如何找出**当前**间距最小的点对呢？
可以发现，无法直接比较点对间距的原因是它们加入 set 时计算间距的时间是不同的。自然可以想到，如果统一维护两个点对在某一固定时刻时的**等效间距**，就可以比较大小了。这里我们选择维护它们在时刻 $0$ 的等效间距。具体来说，在时刻 $T$，间距为 $d$ 的点对的等效间距为 $T + d$。也就是说，等效间距的含义是，假设点对的两个点是以每秒一个单位长度不停靠近时，他们在第 $0$ 秒时的距离。
当一次碰撞发生后，可能会改变一些点的运动方向，导致一些点对消失，一些点对增加。这样的改变量都是 $O(1)$ 个。例如，对四个相邻的点 $i,j,k,l$（$k$ 和 $l$ 相距较远），假设它们的权重分别是 $4,1,2,3$。则初始时 $k$ 向 $l$ 移动，此时 $(i,j)$ 是一个点对，$(k,l)$ 是一个点对。当 $(i,j)$ 碰撞后，$k$ 左侧的权重比右侧大，则它会回头向左侧走。$(k,l)$ 这个点对被删除了，$(i,k)$ 这个点对增加了。
最后一个问题是，在插入 set 时，要求出两点当前的间距。这要求我们能快速求出每个点的坐标。考虑懒更新，仅当一次碰撞发生后，更新与消失的点相邻的点的坐标（因为只有这两个点可能凑成新点对）。记 $lastChange_i$ 表示上次更新 $i$ 的坐标的时刻，上次更新后 $i$ 的坐标是 $x_i$，当前时刻为 $T$，则 $i$ 当前的坐标就是 $x_i + (T - lastChange_i) \times aspect_i$。其中，当 $i$ 向左移动时，$aspect_i = -1$，$i$ 向右移动时，$aspect_i = 1$，静止不动时 $aspect_i = 0$。这是因为两次更新之间 $i$ 的运动方向不可能变化（想一想，为什么）。这其实也是能使用等效间距维护最小间距的原因。
此外，为了能求出当前与某个点相邻的点，需要按顺序维护当前还存活的点，支持查询上一个、下一个。这部分可以使用链表完成，std 图省事使用了 `std::set`。
总的来说，一共发生了 $O(n)$ 次碰撞，每次碰撞对 set 有 $O(1)$ 次修改，单次修改复杂度 $O(\log n)$。于是算法的总时间复杂度为 $O(n \log n)$。期望得分 $100$ 分。
验题人给出的代码中，直接维护了每个点在时刻 $0$ 的**等效坐标**。原理与等效间距相似，也就是假设一个点一直按当前的方向移动，则它在时刻 $0$ 应有的坐标。相当于把上文做法里 $lastChange$ 固定为 $0$。
因为篇幅原因，本文省去了一些证明比较简单（但可能并不直观）的可行性、正确性证明，仅给出了做法。这些被省去的可行性可以通过自己尝试举反例（发现举不出）来感性理解，进而通过反证法证明，在此略去。
## Code
有一个小细节是，注意到同一秒可能会有多只萤火虫去世，会导致一些萤火虫的方向被反复更新。如果更新顺序不正确就会出问题。一个简单的解决方法是在 set 里以不动（显然碰撞都是一只动的撞一只不动的）的那只萤火虫亮度为第二关键字排序。
如果没有想到这个技巧，那么有一个很普适的解决方案是先把同一秒发生的碰撞全都拿出来，集体更新完以后再扫一遍受影响的点，求出这一秒的末状态，最后塞入 set。std 使用的是第一种解决方法。
```cpp
#include <set>
#include <tuple>
#include <iostream>
#include <algorithm>
const int maxn = 500005;
const int INF = 2000000001;
int n, bcnt, T;
int x[maxn], a[maxn], dis[maxn], aspect[maxn], ans[maxn], lastChange[maxn];
std::set<std::tuple<int, int, int>> s;
std::set<int> alive;
inline int getAspect(int pre, int x, int post) {
if (a[pre] > a[post]) {
if (a[pre] > a[x]) return -1;
} else {
if (a[post] > a[x]) return 1;
}
return 0;
}
inline int getp(int i) { return x[i] + (T - lastChange[i]) * aspect[i];}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
auto read = []() { int x; std::cin >> x; return x; };
std::generate(x + 1, x + 1 + n, read);
std::generate(a + 1, a + 1 + n, read);
for (int i = 1; i <= n; ++i) aspect[i] = getAspect(i - 1, i, i + 1);
x[0] = -INF, x[n + 1] = INF;
alive.insert(0); alive.insert(n + 1);
for (int i = 1; i <= n; ++i) if (aspect[i] == -1) dis[i] = dis[i - 1] - x[i - 1] + x[i];
for (int i = n; i; --i) if (aspect[i] == 1) dis[i] = dis[i + 1]- x[i] + x[i + 1];
for (int i = 1; i <= n; ++i) if (aspect[i] != 0) {
if (aspect[i + aspect[i]] != aspect[i]) s.insert(std::make_tuple(dis[i], a[i + aspect[i]], i));
}
for (int Cnt = 1; Cnt < n; ++Cnt) {
auto begin = s.begin();
int i = std::get<2>(*begin);
T = lastChange[i] + dis[i];
s.erase(s.begin());
int j = (aspect[i] == 1) ? *(++alive.find(i)) : *(--alive.find(i));
ans[i] = x[j];
int k = (aspect[i] == -1) ? *(++alive.find(i)) : *(--alive.find(i));
alive.erase(i);
if (aspect[i] == aspect[k]) {
x[k] = getp(k);
lastChange[k] = T;
s.insert(std::make_tuple((dis[k] = abs(x[k] - x[j])) + T, a[j], k));
} else {
if (k == 0 || k == n + 1) continue;
int as = getAspect(*(--alive.find(k)), k, *(++alive.find(k)));
if (as != aspect[k]) {
if (aspect[k] == 0) {
int h = (as == -1) ? *(++alive.find(k)) : *(--alive.find(k));
if (s.find(std::make_tuple(dis[h] + lastChange[h], a[k], h)) != s.end()) {
s.erase(std::make_tuple(dis[h] + lastChange[h], a[k], h));
}
}
x[k] = getp(k);
int prenode = (aspect[k] == 1) ? *(++alive.find(k)) : *(--alive.find(k));
if (s.find(std::make_tuple(dis[k] + lastChange[k], a[prenode], k)) != s.end()) {
s.erase(std::make_tuple(dis[k] + lastChange[k], a[prenode], k));
}
aspect[k] = as;
s.insert(std::make_tuple(T + (dis[k] = abs(x[k] - x[j])), a[j], k));
lastChange[k] = T;
}
}
}
for (int i = 1; i <= n; ++i) std::cout << ans[i] << " \n"[i == n];
}
```
## Generator
```cpp
const int maxn = 500005;
int a[maxn], x[maxn];
void makedata(int T) {
int n = 500000, lim = 500000000;
if (T <= 6) {
if (T == 1) n = 2;
else n = 100;
lim = 200;
for (int i = 1; i <= n; ++i) a[i] = i;
std::random_shuffle(a + 1, a + 1 + n, modx<int>);
for (int i = 1; i <= lim; ++i) x[i] = i;
std::random_shuffle(x + 1, x + 1 + lim, modx<int>);
std::sort(x + 1, x + 1 + n);
} else {
if (T <= 12) n = 1000;
int block = lim / 7, tn = n / 7, nn = 0;
for (int cnt = 1, i = 1; cnt <= 3; ++cnt) {
int delta = block / (tn + 1);
for (int j = 1, p = i; j <= tn; ++j) {
x[++nn] = p;
p += delta;
}
i += block;
}
int beg = tn * 3 + 1;
std::set<int> oc;
for (int i = nn; i <= n; ++i) {
int p;
do p = modx(lim - block * 3) + block * 3; while (oc.find(p) != oc.end());
oc.insert(p);
x[i] = p;
}
std::sort(x + nn, x + 1 + n);
if (T == 13) {
for (int i = 1; i <= n; ++i) a[i] = i;
} else if (T == 14) {
for (int i = 1; i <= n; ++i) a[i] = i;
std::random_shuffle(a + 1, a + 1 + n);
std::sort(a + 1, std::find(a + 1, a + 1 + n, n));
std::sort(std::find(a + 1, a + 1 + n, n), a + 1 + n, std::greater<int>());
} else if (T > 14 && T <= 17) {
for (int i = 1; i <= n; ++i) a[i] = i;
std::random_shuffle(a + 1, a + 1 + n);
for (int i = 2, c0 = 1, c1 = 1; i <= n; ++i) if (a[i] > a[i - 1]) {
c0++; c1 = 1;
if (c0 > 5) std::swap(a[i - 2], a[i - 3]);
} else {
c1++; c0 = 1;
if (c1 > 5) std::swap(a[i - 2], a[i - 3]);
}
} else {
for (int i = 1; i <= tn; ++i) a[i] = 2 * i;
for (int i = tn; i > 0; --i) a[i + tn] = 2 * i - 1;
for (int i = 2 * tn + 1; i <= n; ++i) a[i] = i;
std::random_shuffle(a + tn + tn + 1, a + 1 + n, modx<int>);
}
}
printf("%d\n", n);
for (int i = 1; i <= n; ++i) printf("%d%c", x[i] * 2, i == n ? '\n' : ' ');
for (int i = 1; i <= n; ++i) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
```