Description

给定数轴上的坐标升序的 $n$ 个点，坐标为 $a_{1\sim n}$，点有权值 $b_{1\sim n}$。

还给出一个区间 $[l,r]$，从点 $1$ 出发，每次跳 $u\to v$ 必须满足 $l\le a_v-a_u\le r$，要通过若干次操作跳到 $n$。

将走过点的 $b_i$ 非升序排成一个序列，最大化其字典序，若无解输出 $-1$，$t$ 组数据。

Limitations

$1\le \sum n\le 10^6,1\le l\le r\le 10^9$

$1\le a_i\le 10^9,1\le b_i\le n$

$2.5\text{s},1024\text{MB}$

Solution

先考虑暴力，设 $S_i$ 表示走到 $i$ 时的最优序列，维护字典序升序的单调队列 $Q$。

双指针维护 DP，持续推进 $j$ 直到 $a_i-a_j\ge l$ 不满足，其中对每个 $j$ 先弹出 $Q$ 队头所有 $S_j>S_\text{front}$ 的序列，然后从 $Q$ 队头压入 $j$ 保证单调性。

然后若 $Q$ 队尾不满足 $a_i-a_\text{back}\le r$，则不断弹掉队尾直到满足，显然此时 $l\le a_i-a_\text{back}\le r$ 一定满足，且 $\text{back}$ 位置是最优的，直接令 $S_i=S_\text{back}\cup {b_i}$ 即可。

由于单次比较序列要 $O(n)$，总复杂度 $O(n^2)$。但是你发现可以用权值线段树维护 hash 值 $\sum_{x=1}^n B^x\text{cnt}_x$，容易二分来 $O(\log n)$ 比较两个序列。由于转移是复制再插入，改成 PST 即可，复杂度 $O(n\log n)$，注意记录 $S_i$ 为空的情况。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}

template<class T>
bool chmin(T &a, const T &b){
    if(a > b){ a = b; return true; }
    return false;
}

constexpr int B = 1313131;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, L, R;
        cin >> n >> L >> R;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i], b[i]--;

        vector<ui64> pw(n + 1); pw[0] = 1;
        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * B;
        }

        struct Node {
            int l, r;
            int cnt; ui64 hs;
        };
        vector<Node> t(1); t.reserve(n * 40);
        function<int(int, int, int, int)>
        insert = [&](int pre, int l, int r, int x) {
            int u = t.size();
            t.push_back(t[pre]);
            t[u].hs += pw[x], t[u].cnt++;
            if (l == r) return u;

            const int mid = (l + r) >> 1;
            if (x <= mid)
                t[u].l = insert(t[pre].l, l, mid, x);
            else
                t[u].r = insert(t[pre].r, mid + 1, r, x);
            return u;
        };

        function<bool(int, int, int, int)>
        compare = [&](int u, int v, int l, int r) {
            if (l == r) return t[u].cnt > t[v].cnt;

            const int mid = (l + r) >> 1;
            if (t[t[u].r].hs == t[t[v].r].hs)
                return compare(t[u].l, t[v].l, l, mid);
            else
                return compare(t[u].r, t[v].r, mid + 1, r);
        };

        vector<int> ans;
        function<void(int, int, int)>
        flat = [&](int u, int l, int r) {
            if (!u) return;
            if (l == r) {
                for (int i = 0; i < t[u].cnt; i++)
                    ans.push_back(l);
                return;
            }

            const int mid = (l + r) >> 1;
            flat(t[u].r, mid + 1, r);
            flat(t[u].l, l, mid);
        };

        vector<int> root(n);
        vector<bool> vis(n); deque<int> dq;
        root[0] = insert(0, 0, n - 1, b[0]);

        for (int i = 1, j = -1; i < n; i++) {
            while (j + 1 < i && a[i] - a[j + 1] >= L) {
                j++; if (vis[j]) continue;
                while (!dq.empty() && compare(
                       root[j], root[dq.front()], 0, n - 1))
                    dq.pop_front();
                dq.push_front(j);
            }
            while (!dq.empty() && a[i] - a[dq.back()] > R) dq.pop_back();
            if (dq.empty()) vis[i] = true;
            else
                root[i] = insert(root[dq.back()], 0, n - 1, b[i]);
        }

        if (vis[n - 1]) cout << "-1\n";
        else {
            flat(root[n - 1], 0, n - 1);
            cout << ans.size() << '\n';
            for (int x : ans) cout << x + 1 << ' ';
            cout << '\n';
        }
    }

    return 0;
}