自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:45:04，当前版本为作者最后更新于2018-06-18 16:43:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[yLOI2023] D 腐草为萤

这个题上线前经过了巨大削弱，导致结论变得很一眼，可能对思维量的要求变弱了。

Description

数轴上有 $n$ 个点，每个点的初始坐标为 $x_i$，权重为 $a_i$。在任何时刻，每个点会向与它相邻的两个点中权重较大的那个点移动，速度为一个单位长度每秒，如果相邻两个点的权重都比它自身权重小，则不移动。两个点相遇时，权重较小的点消失。

求出每个点消失时的坐标。

$1 \leq n \leq 5 \times 10^5$，$1 \leq x_i \leq 10^9$，$a$ 是长度为 $n$ 的排列。

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 使用的是第一种解决方法。

#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

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' : ' ');
}