Codeforces

Luogu

分析

考虑对值域分块，设块长为 $B$。

对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。

考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样子每块操作次数是 $T(B) = 2T(\frac{B}{2}) + \frac{1}{2}B^2 = B^2$ 的，总操作次数为 $nB$。

于是总的操作次数是 $\frac{nq}{B} + nB$，$B=\sqrt{q}$ 时取最小值 $2n\sqrt{q}$，可以通过。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 4096 + 10;

int n, Q, a[N], pos[N], ans[N << 4];
int B, bl[N], L[N], R[N];

vector<pair<int, int>> vec;
int tot = 0;
int merge(int x, int y) {
    if (!x || !y) return x | y;
    else {
        vec.emplace_back(x, y);
        return ++tot;
    }
}

struct Block {
    vector<int> o; vector<vector<int>> id;
    int get(int l, int r) {
        int x = lower_bound(o.begin(), o.end(), l) - o.begin();
        int y = upper_bound(o.begin(), o.end(), r) - o.begin() - 1;
        return x <= y ? id[x][y] : 0;
    }
} b[N];
Block merge(Block x, Block y) {
    int n = x.o.size() + y.o.size();
    Block z; z.o.resize(n), z.id.resize(n);
    for (int i = 0; i < n; ++i) z.id[i].resize(n);
    merge(x.o.begin(), x.o.end(), y.o.begin(), y.o.end(), z.o.begin());
    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j) {
            int p = x.get(z.o[i], z.o[j]), q = y.get(z.o[i], z.o[j]);
            z.id[i][j] = merge(p, q);
        }
    return z;
}
Block build(int l, int r) {
    if (l == r) return (Block){{pos[l]}, {{pos[l]}}};
    int mid = (l + r) >> 1;
    return merge(build(l ,mid), build(mid + 1, r));
}

int main() {
    n = read(), Q = read();
    for (int i = 1; i <= n; ++i) a[i] = read(), pos[a[i]] = i;
    B = sqrt(Q);
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / B + 1;
    for (int i = 1; i <= bl[n]; ++i) L[i] = R[i - 1] + 1, R[i] = min(i * B, n);
    tot = n;
    for (int i = 1; i <= bl[n]; ++i) b[i] = build(L[i], R[i]);
    for (int i = 1; i <= Q; ++i) {
        int l = read(), r = read();
        for (int j = 1; j <= bl[n]; ++j)
            ans[i] = merge(ans[i], b[j].get(l, r));
    }
    printf("%d\n", tot);
    for (auto i : vec) printf("%d %d\n", i.first, i.second);
    for (int i = 1; i <= Q; ++i) printf("%d%c", ans[i], " \n"[i == Q]);
    return 0;
}