题解：P14180 「FAOI-R8」奶龙大战暴暴龙

· · 题解

模拟赛出了这个题的 n \le 10^3，1h 秒了。

给出两个长为 n,m 的数组 a_i,b_i。一次操作选择 l,r,k，满足 1 \le l \textcolor{red}{<} r \le n，然后将 a 的子数组 [l,r] 移除，再插入到第 k 个元素后。

你需要在至多 \max(n,m) 次操作后将 a_i 变成 b_i，给出构造或报告无解。

多测，T \le 30，1 \le n,m,a_i,b_i \le 5 \times 10^4，0.5 秒，512 MB。

首先判掉一些显然的无解情形：n\ne m 或者 a_i,b_i 构成的多重集不同。

因为操作次数为 n，我们想到逐个让 a_i \gets b_i。从左到右扫描 i，找到第一个 b_i 出现的位置 p：

注意特判 n=3 的 corner case。操作次数显然不大于 n。

直接模拟上述构造，复杂度 O(n^2)，可以获得 85pts。

考虑用数据结构模拟上述过程，需要模拟操作和找出现位置。一个魔怔的做法是 FHQ-Treap 套 bitset，复杂度 O\left(\frac{nV \log n}{w}\right)，可以获得 25pts。

较为人类的做法：维护 FHQ-Treap 的父节点，然后对于每个值开队列维护对应的节点指针，查询的时候跳根链得到下标。复杂度 O(n\log n)，可以通过。

:::::info[代码]

const int N = 5e4 + 5;
int h, n, m, a0[N], b0[N], a[N], b[N];
vector<tuple<int, int, int>> vec;

struct node {
    u32 pri; int val, sz;
    node *l, *r, *f;
    node(int v = 0) : 
    pri(rand32()), val(v), sz(1), l(nullptr), r(nullptr), f(nullptr) {}
    node* pushup() {
        sz = 1;
        if (l) sz += l->sz, l->f = this;
        if (r) sz += r->sz, r->f = this;
        return this;
    }
};
void split(node* u, int k, node*& x, node*& y) {
    if (!u) return x = y = nullptr, void();
    int ls = u->l ? u->l->sz : 0;
    if (ls < k) x = u, split(u->r, k - ls - 1, x->r, y), x->pushup(), x->f = nullptr;
    else y = u, split(u->l, k, x, u->l), y->pushup(), y->f = nullptr;
}
node* merge(node* u, node* v) {
    if (!u || !v) return u ? u : v;
    return u->pri < v->pri 
    ? (u->r = merge(u->r, v), u->f = nullptr, u->pushup())
    : (v->l = merge(u, v->l), v->f = nullptr, v->pushup());
}
node *T;
deque<node*> pos[N];

void op(int l, int r, int k) {
    node *a, *b, *c, *d, *e, *f;
    split(T, r, a, c), split(a, l - 1, a, b);
    d = merge(a, c), split(d, k, e, f);
    T = merge(merge(e, b), f);
    vec.emplace_back(l, r, k);
}
int ask(node* u) {
    int p = (u->l ? u->l->sz : 0) + 1;
    for (; u->f; u = u->f) 
        if (u == u->f->r) p += (u->f->l ? u->f->l->sz : 0) + 1;
    return p;
}

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], a0[i] = a[i];
    for (int i = 1; i <= m; i++) cin >> b[i], b0[i] = b[i];
    if (n != m) return cout << -1 << '\n', void();
    sort(a0 + 1, a0 + n + 1), sort(b0 + 1, b0 + n + 1);
    for (int i = 1; i <= n; i++) if (a0[i] != b0[i]) return cout << -1 << '\n', void();
    if (n == 3) {
        if (a[1] == b[1] && a[2] == b[2]) cout << 0 << '\n';
        else if (a[1] == b[2] && a[2] == b[3]) cout << "1\n1 2 1\n";
        else if (a[2] == b[1] && a[3] == b[2]) cout << "1\n2 3 0\n";
        else cout << -1 << '\n';
        return;
    }
    T = nullptr, vec.clear();
    for (int i = 1; i <= n; i++) pos[a[i]].clear();
    for (int i = 1; i <= n; i++) {
        node *u = new node(a[i]);
        pos[a[i]].emplace_back(u), T = merge(T, u);
    }
    for (int i = 1; i <= n; i++) {
        node *u = pos[b[i]].front(); 
        pos[b[i]].pop_front();
        int p = ask(u);
        if (p == i) continue;
        if (p != n) op(p, n, i - 1);
        else if (i != p - 1) op(i, p - 1, i); 
        else op(n - 3, n - 2, n - 3), op(n - 2, n, n - 4);
    } 
    cout << vec.size() << '\n';
    for (auto [l, r, k] : vec) cout << l << ' ' << r << ' ' << k << '\n';
}

:::::