洛谷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;
}