题目链接：Codeforces 1148E

数轴上有 $n$ 块石头。最初，第 $i$ 个石头位于坐标 $s_i$ 的位置。同一个地方可能有不止一块石头。

你可以进行如下操作任意次（可以为 $0$ 次）：

• 拿出下标为 $i, j$ 且满足 $s_i \le s_j$ 的两块石头，选择一个整数 $d$ 满足 $0 \le 2 \cdot d \le s_j - s_i$ 并将第 $i$ 块石头放到坐标为 $(s_i + d)$ 的地方，将第 $j$ 块石头放到坐标为 $(s_j - d)$ 的地方。换言之，将两块石头相互靠近。

你想通过移动，将石头的坐标变为 $t_1, t_2, \dots, t_n$，注意石头的顺序是无关紧要的。

判断是否存在一种移动石头的方法。如果可以，输出 YES 并构造一种方法；否则输出 NO。你不需要最小化移动次数。

数据范围：$1 \le n \le 3 \times 10 ^ 5$，$1 \le s_i, t_i \le 10 ^ 9$。

Solution

注意到顺序是没有用的，而石头之间的相对顺序是不会改变的，我们将 $s, t$ 都按照值从小到大排序。

我们记 $\delta_i = s_i - t_i$，由于石头是不断靠近的，那么 $\delta$ 的某个前缀一定满足 $\forall i, \delta_i < 0$；同理某个后缀一定满足 $\forall i, \delta_i > 0$；而 $\delta_i = 0$ 的那些位置是没有用的，因为它们已经在正确的坐标了。

我们从前往后扫，一旦遇到 $\delta_i > 0$ 就用之前的某个 $\delta_j < 0$ 去抵消。拿个队列、栈之类的乱搞。注意在抵消过程中判断 NO 的情况。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

#define fail return printf("NO\n"), 0

const int N = 3e5 + 5;

int n, c[N];
std::pair<int, int> s[N], t[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i].first);
        s[i].second = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i].first);
        t[i].second = i;
    }
    std::sort(s + 1, s + n + 1);
    std::sort(t + 1, t + n + 1);
    std::queue<std::pair<int, int>> q;
    std::vector<std::tuple<int, int, int>> ans;
    for (int i = 1; i <= n; i++) {
        int x = s[i].first - t[i].first, j = s[i].second;
        if (x < 0) {
            q.push(std::make_pair(x, j));
        }
        if (x > 0) {
            while (x && !q.empty()) {
                int y = q.front().first, k = q.front().second;
                q.pop();
                int d = std::min(x, -y);
                x -= d, y += d;
                if (y) q.push(std::make_pair(y, k));
                ans.emplace_back(k, j, d);
            }
            if (x) fail;
        }
    }
    if (!q.empty()) fail;
    printf("YES\n");
    printf("%d\n", (int)ans.size());
    for (auto x : ans) {
        printf("%d %d %d\n", std::get<0>(x), std::get<1>(x), std::get<2>(x));
    }
    return 0;
}