洛谷P9066 [yLOI2023] 腐草为萤题解

题目链接：P9066 [yLOI2023] 腐草为萤

题意：

夜幕降临，在树林中的一条平直的小径上，萤火虫们受到夜晚的呼唤，纷纷外出行动。

将小径视作数轴，一开始，共计 \(n\) 只萤火虫在数轴的一些整点上，从左到右依次标号为 \(1 \sim n\)，第 \(i\) 只萤火虫的初始坐标为 \(x_i\)。每个萤火虫有不同的亮度值，\(i\) 号萤火虫的亮度为 \(a_i\)。

在任意时刻，对任意存活的萤火虫 \(i\)，它会按如下规则飞行：

在当前仍存活的萤火虫中，找到与 \(i\) 相邻的萤火虫（可能是一只或两只）中亮度最大的一只，记其编号为 \(j\)。如果 \(a_i < a_j\)，则 \(i\) 会朝着 \(j\) 飞行，否则 \(i\) 留在原地。

这里两只萤火虫『相邻』的定义是：若两只萤火虫之间不存在任何仍存活的萤火虫，则它们相邻。

萤火虫飞行的速度均为每秒一个单位长度。

萤火虫生命短暂，当两只萤火虫相遇之时（即两个萤火虫的坐标相同时），亮度值较低的萤火虫将耗尽生命，在小径上消失。显然，最后只会剩余 \(1\) 只萤火虫。对其余的每只萤火虫，请分别求出它们耗尽生命时的坐标。

输入格式：

第一行是一个整数，表示萤火虫数量 \(n\)。
第二行有 \(n\) 个整数，第 \(i\) 个整数表示标号为 \(i\) 的萤火虫初始坐标 \(x_i\)。数据保证 \(x_i\) 单调递增。
第三行有 \(n\) 个整数，第 \(i\) 个整数表示标号为 \(i\) 的萤火虫的亮度值 \(a_i\)。数据保证亮度值互不相同。

输出格式：

输出一行 \(n\) 个以单个空格隔开的整数，第 \(i\) 个整数表示编号为 \(i\) 的萤火虫生命耗尽时的坐标。如果 \(i\) 号萤火虫最后存活下来了，则第 \(i\) 个数输出 0。

数据范围：

对于 \(5\%\) 的数据，\(n = 2\)。

对于 \(30\%\) 的数据，\(n \leq 100\)，\(x_i \leq 200\)。

对于 \(60\%\) 的数据，\(n \leq 10^3\)。

另有 \(5\%\) 的数据，满足特殊约定 A。

另有 \(5\%\) 的数据，满足特殊约定 B。

对 \(100\%\) 的数据，保证 \(2 \leq n \leq 5 \times 10^5\)，\(1 \leq x_i \leq 10^9\)，\(1 \leq a_i \leq n\)。且 \(x_i < x_{i + 1}\)，\(a_i\) 是长度为 \(n\) 的排列。

其中：

特殊约定 A：数列 \(a\) 单调递增。

特殊约定 B：数列 \(a\) 是单峰的，仅有一个极大值。即：存在 \(p\) 满足 \(1 \leq p < n\)，使得 \(a_1 \sim a_p\) 单调递增，\(a_p \sim a_n\) 单调递减.

省流：

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

求出每个点消失时的坐标。 \(1 \leq n \leq 5 \times 10^5,~ 1 \leq x_i \leq 10^9,~ a\) 是长度为 \(n\) 的排列。

找到距离最小的一对 \((i,j)\) ，令一方不动，另一方向其靠近。

容易发现，此时在 \((i,j)\) 碰撞前，其他点不会发生碰撞。

记经过 \(T\) 秒发生碰撞，则一个 \(T\) 秒前一个向右运动的点 \(i\) 的新坐标为 \(x_i + T\) 。

由此我们得到了一个思路，于是尝试继续寻找它的性质。

注意到，当碰撞发生后，至多只有 \(2\) 个点会改变运动方向。

这意味着，如果我们能够快速找到相距最小的那对 \((i,j)\) ，就可以 \(\mathcal{O}(1)\) 更新所有关联的点的状态

于是考虑用 set 来维护这个最小间距。但是这会出现一个问题，每次点对的间距只能在加入时计算。

当时间增加时，我们无法更新原来的间距。那么怎么办呢？

可以发现，无法直接比较点对间距的原因是它们加入 set 时计算间距的时间是不同的。

于是我们定义等效间距 \(T+d\) ，其中 \(T\) 为当前时刻，初始为 \(0\) 。

当一次碰撞发生时，我们只更新与消失的点 \(i\) 相邻的点（显然只有这两个点可以凑成新点对）

记 last_i 表示上次更新 \(i\) 坐标的时刻，上次更新 \(i\) 后的坐标是 \(x_i\) ，当前时刻为 \(T\) 。

则 \(i\) 当前的坐标为 \(x_i + (T -\) last_i\() \times\) to_i ，其中 to_i 表示方向（左为 \(-1\) ，右为 \(1\) ，不动时为 \(0\) ）

两次更新之间 \(i\) 的运动方向不可能改变，这也是可以用等效间距维护最小间距的原因。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

int n,T,x[N],a[N],d[N],to[N],ans[N],last[N];
set<int> ok; set< tuple<int,int,int> > st;
int get_to(int pre, int x, int suf)
{
    if(a[pre] > a[suf]) {
        if(a[pre] > a[x]) return -1;
    }else { if(a[suf] > a[x]) return 1; }
    return 0;
}
int get_p(int i) { return x[i] + (T - last[i]) * to[i]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 1; i <= n; i++) cin >> a[i], ok.insert(i);
    for(int i = 1; i <= n; i++) to[i] = get_to(i - 1, i, i + 1);
    // for(int i = 1; i <= n; i++) cout << to[i] << " \n"[i == n];
    x[0] = -INF, x[n + 1] = INF; ok.insert(0), ok.insert(n + 1);
    for(int i = 1; i <= n; i++) if(to[i] == -1) d[i] = d[i - 1] - x[i - 1] + x[i];
    for(int i = n; i; i--) if(to[i] == 1) d[i] = d[i + 1] - x[i] + x[i + 1];
    for(int i = 1; i <= n; i++) if(to[i] != 0) {
        if(to[i + to[i]] != to[i]) st.insert({d[i], a[i + to[i]], i});
    }
    for(int cnt = 1; cnt < n; cnt++)
    {
        auto begin = st.begin(); int i = get<2>(*begin);
        T = last[i] + d[i]; st.erase(st.begin());
        int j = (to[i] == 1) ? *(++ok.find(i)) : *(--ok.find(i));
        ans[i] = x[j];
        int k = (to[i] == -1) ? *(++ok.find(i)) : *(--ok.find(i));
        ok.erase(i);
        if(to[i] == to[k])
        {
            x[k] = get_p(k); last[k] = T;
            st.insert({T + (d[k] = abs(x[k] - x[j])), a[j], k});
        }else
        {
            if(k == 0 || k == n + 1) continue;
            int t = get_to(*(--ok.find(k)), k, *(++ok.find(k)));
            if(t != to[k])
            {
                if(!to[k])
                {
                    int h = (t == -1) ? *(++ok.find(k)) : *(--ok.find(k));
                    if(st.find({d[h] + last[h], a[k], h}) != st.end())
                        st.erase({d[h] + last[h], a[k], h});
                }
                x[k] = get_p(k);
                int p = (to[k] == 1) ? *(++ok.find(k)) : *(--ok.find(k));
                if(st.find({d[k] + last[k], a[p], k}) != st.end())
                    st.erase({d[k] + last[k], a[p], k});
                to[k] = t;
                st.insert({T + (d[k] = abs(x[k] - x[j])), a[j], k}); last[k] = T;
            }
        }
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
    return 0;
}