洛谷 P1966 [NOIP 2013 提高组] 火柴排队

// ★★★ 题面定义的那个「距离」，在顶格数据上根本装不下
//
// 用法：./p1966Dist [n]        人话版（默认 n = 10⁵，题面顶格）
//       ./p1966Dist [n] csv    给 check:viz 用
//
// 题面把问题定义成「让 Σ(aᵢ-bᵢ)² 最小」。于是很自然会想：
//   那我先写个函数把这个距离算出来，好歹能验一验吧？
//
// ⇒ 算不出来。题面的值域是 [0, 2³¹)：
//   · 一项最大 (2³¹-1)² ≈ 4.6×10¹⁸ —— 单独一项就快顶到 long long 的 9.2×10¹⁸ 了；
//   · n = 10⁵ 项加起来 ≈ 4.6×10²³，而 unsigned long long 的上限才 1.8×10¹⁹。
//
// 这份程序把最坏那组数据造出来（a 全挤在低端、b 全挤在高端），
// 用三种宽度各算一遍，看谁还活着。
//
// ★ 结论不是「要用 __int128」，是：**正解从头到尾一次都没算过这个距离。**
//   题面用它来**定义**问题，不是让你去**算**它 —— 真正被算的只有「排名」。

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

static void print128(__int128 v) {
    if (v == 0) { printf("0"); return; }
    char buf[64]; int p = 0;
    while (v > 0) { buf[p++] = char('0' + (int)(v % 10)); v /= 10; }
    while (p > 0) putchar(buf[--p]);
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 100000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    const long long TOP = 2147483647LL;          // 题面：0 <= a_i, b_i < 2³¹
    long long sll = 0;                            // 有符号 64 位（这里会回绕，故意的）
    unsigned long long sull = 0;                  // 无符号 64 位
    __int128 s128 = 0;                            // 真值

    for (int i = 0; i < n; i++) {
        long long ai = i, bi = TOP - i;           // a 全挤在低端、b 全挤在高端 = 最坏
        long long d = bi - ai;
        unsigned long long sq = (unsigned long long)d * (unsigned long long)d;
        sull += sq;
        sll = (long long)((unsigned long long)sll + sq);   // 用 unsigned 做加法再看成有符号
        s128 += (__int128)d * d;
    }

    unsigned long long ULL_MAX = ~0ULL;
    __int128 ratio = s128 / (__int128)ULL_MAX;

    if (csv) {
        printf("n,%d\n", n);
        printf("oneTermFitsLL,%d\n", ((__int128)(TOP) * TOP < (__int128)9223372036854775807LL) ? 1 : 0);
        printf("sumFitsULL,%d\n", (s128 <= (__int128)ULL_MAX) ? 1 : 0);
        printf("ullWrapped,%d\n", (s128 > (__int128)ULL_MAX) ? 1 : 0);
        printf("llNegative,%d\n", (sll < 0) ? 1 : 0);
        printf("ratioGE,%d\n", (int)ratio);
        return 0;
    }

    printf("题面顶格的最坏一组（n = %d，a 全在低端、b 全在高端）：\n\n", n);
    printf("  单项最大   (2³¹-1)² = ");  print128((__int128)TOP * TOP);
    printf("   （long long 上限 9223372036854775807，%s）\n",
           ((__int128)TOP * TOP < (__int128)9223372036854775807LL) ? "一项还塞得下" : "一项就塞不下");
    printf("  真值       Σ(aᵢ-bᵢ)² = ");  print128(s128);  printf("\n");
    printf("  unsigned long long 上限     = %llu\n", ULL_MAX);
    printf("  ⇒ 真值是它的 ");  print128(ratio);  printf(" 倍 —— **差了四个数量级**\n\n");
    printf("  用 unsigned long long 硬算：%llu   %s\n", sull, (s128 > (__int128)ULL_MAX) ? "★ 回绕了（这个数没有任何意义）" : "没回绕");
    printf("  再当成有符号看：            %lld   %s\n", sll, (sll < 0) ? "★ 变成负数了" : "");
    printf("\n  ⇒ 所以正解一次都没算过这个距离。题面用它**定义**问题，不是让你**算**它。\n");
    printf("    真正被算的只有排名 —— 而排名最大才 %d。\n", n);
    return 0;
}

// P1966 ⚠ 第 ① 版（很多人的第一反应）：**把两列各自排成升序**
//
// 想法完全说得通：
//   「距离最小 ⟺ 两列相对顺序一致」，那最省事的一致就是**两列都升序**。
//   把 a 排成升序要 inv(a) 次相邻交换，把 b 排成升序要 inv(b) 次，加起来就是答案。
//
// ★ 而它算出的**距离确实是最小的** —— 这一步没错。
//   错在题目问的不是「怎么达到最小距离」，是「**最少交换多少次**达到最小距离」。
//   达到最小距离的姿势有无穷多种，「两列都升序」只是最费力的那一种。
//
// 两组官方样例都打得死它：样例一 5（应为 1）、样例二 4（应为 2）。

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

static const int MAXN = 100005;
static const long long MOD = 99999997LL;

static int a[MAXN], b[MAXN], t_[MAXN];
static long long cnt = 0;

static void mergeSort(int* v, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(v, l, mid);
    mergeSort(v, mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (v[i] <= v[j]) t_[k++] = v[i++];
        else { cnt += mid - i + 1; t_[k++] = v[j++]; }
    }
    while (i <= mid) t_[k++] = v[i++];
    while (j <= r)   t_[k++] = v[j++];
    for (int p = l; p <= r; p++) v[p] = t_[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    if (n > 0) { mergeSort(a, 0, n - 1); mergeSort(b, 0, n - 1); }
    cout << cnt % MOD << "\n";
    return 0;
}

// P1966 火柴排队 —— 能 AC 的那一版
//
// 三步，每一步都是一次「换个说法」：
//
//   ① 距离最小 ⟺ **两列的相对大小顺序一致**（第 k 矮的对第 k 矮的）。
//      ⇒ 值本身没用了，只有**排名**有用。⚠ 而这一步的证明不在题面里，
//        p1966Bf.cpp 用一条和本算法完全无关的路把它验了出来。
//   ② 只需要动**一列**（另一列不动也不吃亏）—— 同样由 p1966Bf.cpp 验。
//   ③ 把一列用相邻交换排成指定顺序，**最少次数 = 逆序对数**（第 11 章正文）。
//
// 于是：令 pos[v] = 排名 v 在 b 里的位置，d[i] = pos[ra[i]]，答案 = inv(d)。
//
// ⚠ 两个坑：
//   · 模数是 **10⁸ - 3 = 99999997**，不是 10⁹+7；
//   · 逆序对数最多 n(n-1)/2 ≈ 5×10⁹ ⇒ **cnt 必须 long long**，最后才取模。

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

static const int MAXN = 100005;
static const long long MOD = 99999997LL;

static int a[MAXN], b[MAXN], ra[MAXN], rb[MAXN], pos_[MAXN], d[MAXN], tmp_[MAXN];
static long long cnt = 0;

static void rankOf(int* v, int* r, int n) {          // v 的元素互不相同 ⇒ 排名 1..n
    static pair<int, int> t[MAXN];
    for (int i = 0; i < n; i++) t[i] = {v[i], i};
    sort(t, t + n);
    for (int k = 0; k < n; k++) r[t[k].second] = k + 1;
}

static void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (d[i] <= d[j]) tmp_[k++] = d[i++];
        else { cnt += mid - i + 1; tmp_[k++] = d[j++]; }
    }
    while (i <= mid) tmp_[k++] = d[i++];
    while (j <= r)   tmp_[k++] = d[j++];
    for (int p = l; p <= r; p++) d[p] = tmp_[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    rankOf(a, ra, n);
    rankOf(b, rb, n);
    for (int i = 0; i < n; i++) pos_[rb[i]] = i;
    for (int i = 0; i < n; i++) d[i] = pos_[ra[i]];

    if (n > 0) mergeSort(0, n - 1);
    cout << cnt % MOD << "\n";
    return 0;
}

// ★★★ P1966 的暴力参照物 —— 一条和「逆序对」「排序不等式」一个字都不沾的路
//
// 用法：喂一组 n <= 6 的数据，输出最少交换次数。
//
// 做法：把「两列火柴的当前摆法」整个当成一个状态，在状态图上做 BFS。
//   · 状态 = (a 这一列的排列, b 这一列的排列)，共 (n!)² 个（n = 6 时 518 400 个）；
//   · 一步 = **任选一列**，交换相邻两根 —— 题面允许的动作，一字不差；
//   · 先扫一遍所有状态，找出题面那个 Σ(aᵢ-bᵢ)² 的最小值；
//   · 再从初始状态 BFS，第一次碰到「距离 = 最小值」的状态，深度就是答案。
//
// ★ 它为什么值钱：正解里有**两处跳跃**是题面没有证明的 ——
//   ① 「距离最小 ⟺ 两列排名对齐」；② 「只动一列就够，不吃亏」。
//   这份 BFS **两条都不知道**：它只知道题面允许干什么、题面要最小化什么。
//   ⇒ 它和正解跑出同一个数，那两处跳跃才算被验过。
//
// ⚠ 距离用 __int128 存：题面的值域是 [0, 2³¹)，一项就能到 4.6×10¹⁸。

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

int n;
long long a[8], b[8];
vector<array<int, 8>> perms;
vector<array<int, 8>> nb;                 // nb[idx][i] = 交换位置 i、i+1 之后的排列编号

static int packOf(const array<int, 8>& p) {
    int key = 0;
    for (int i = 0; i < n; i++) key |= p[i] << (3 * i);
    return key;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    if (n > 6) { cout << "-1\n"; return 0; }          // 状态数会炸，这份只当小数据的参照物

    vector<int> base(n);
    for (int i = 0; i < n; i++) base[i] = i;
    vector<int> id(1 << 18, -1);
    do {
        array<int, 8> p{};
        for (int i = 0; i < n; i++) p[i] = base[i];
        id[packOf(p)] = (int)perms.size();
        perms.push_back(p);
    } while (next_permutation(base.begin(), base.end()));

    int P = (int)perms.size();
    nb.assign(P, {});
    for (int k = 0; k < P; k++)
        for (int i = 0; i + 1 < n; i++) {
            array<int, 8> q = perms[k];
            swap(q[i], q[i + 1]);
            nb[k][i] = id[packOf(q)];
        }

    auto distOf = [&](int ia, int ib) {
        __int128 s = 0;
        for (int k = 0; k < n; k++) {
            long long d = a[perms[ia][k]] - b[perms[ib][k]];
            s += (__int128)d * d;
        }
        return s;
    };

    __int128 best = distOf(0, 0);
    for (int ia = 0; ia < P; ia++)
        for (int ib = 0; ib < P; ib++) {
            __int128 s = distOf(ia, ib);
            if (s < best) best = s;
        }

    vector<char> seen((size_t)P * P, 0);
    vector<int> q;
    q.reserve((size_t)P * P);
    q.push_back(0);
    seen[0] = 1;
    int depth = 0, head = 0;
    while (head < (int)q.size()) {
        int cntThisLevel = (int)q.size() - head;
        for (int t = 0; t < cntThisLevel; t++) {
            int s = q[head++];
            int ia = s / P, ib = s % P;
            if (distOf(ia, ib) == best) { cout << depth << "\n"; return 0; }
            for (int i = 0; i + 1 < n; i++) {
                int u = nb[ia][i] * P + ib;
                if (!seen[u]) { seen[u] = 1; q.push_back(u); }
                int v = ia * P + nb[ib][i];
                if (!seen[v]) { seen[v] = 1; q.push_back(v); }
            }
        }
        depth++;
    }
    cout << "0\n";
    return 0;
}

// P1966 ★ 「配对方向反过来」的那一版 —— 它**不是 bug**
//
// 正解是：pos[v] = 排名 v 在 b 里的位置，d[i] = pos[ra[i]]，答案 = inv(d)。
// 很容易顺手写反成：posA[v] = 排名 v 在 a 里的位置，e[i] = posA[rb[i]]，答案 = inv(e)。
//
// ⇒ d 和 e 是**互逆的排列**，而**一个排列和它的逆排列，逆序对数完全相同**：
//   d 的逆序对 (i, j)（i < j 且 d[i] > d[j]）和 e 的逆序对之间是一一对应的
//   —— 把「谁排在谁前面」这句话的主语宾语调换一遍而已。
//
// ★ 这一版留在这儿是为了说一件事：**看起来致命的「写反了」，不一定是错的。**
//   下面 1200 轮对拍，它和正解逐字节相同。⇒ 改之前先验，别凭直觉动刀。

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

static const int MAXN = 100005;
static const long long MOD = 99999997LL;

static int a[MAXN], b[MAXN], ra[MAXN], rb[MAXN], posA[MAXN], e[MAXN], tmp_[MAXN];
static long long cnt = 0;

static void rankOf(int* v, int* r, int n) {
    static pair<int, int> t[MAXN];
    for (int i = 0; i < n; i++) t[i] = {v[i], i};
    sort(t, t + n);
    for (int k = 0; k < n; k++) r[t[k].second] = k + 1;
}

static void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (e[i] <= e[j]) tmp_[k++] = e[i++];
        else { cnt += mid - i + 1; tmp_[k++] = e[j++]; }
    }
    while (i <= mid) tmp_[k++] = e[i++];
    while (j <= r)   tmp_[k++] = e[j++];
    for (int p = l; p <= r; p++) e[p] = tmp_[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    rankOf(a, ra, n);
    rankOf(b, rb, n);
    for (int i = 0; i < n; i++) posA[ra[i]] = i;      // ⚠ 和正解正好调了个个儿
    for (int i = 0; i < n; i++) e[i] = posA[rb[i]];

    if (n > 0) mergeSort(0, n - 1);
    cout << cnt % MOD << "\n";
    return 0;
}

// 数据生成器（P1966 对拍用）：`./p1966Gen <seed> [level] [n]`
//
//   level 0（默认）★ n ≤ 6、值域 1..15 —— **给 p1966Bf.cpp 那个 BFS 参照物用的**
//                  （状态数 (n!)²，n = 7 就是 2500 万，跑不动）
//   level 1        n ≤ 8、值域到 10⁹ —— 值大不大和这道题的答案无关（只有排名有关），
//                  这一档就是用来把「无关」这件事验一遍的
//   level 2        顶格：n 由第三个参数给（默认 10⁵），值域到 8×10⁸
//   level 3        ★ **答案最大的形状**：a 升序、b 降序 ⇒ 交换次数恰好 n(n-1)/2
//                  （n = 10⁵ 时是 4 999 950 000 —— 取模之前就已经越过 int 了）
//
// ⚠ 题面保证「同一列火柴的高度互不相同」—— 生成器必须照办，
//   否则「排名」这个概念本身就没了（而参照物和正解会一起错，对拍看不出来）。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

static vector<int> distinctVals(int n, int step) {   // 互不相同：从 0 开始逐个往上跳
    vector<int> v(n);
    int cur = ri(0, step);
    for (int i = 0; i < n; i++) { v[i] = cur; cur += ri(1, step); }
    for (int i = n - 1; i > 0; i--) swap(v[i], v[rng() % (unsigned)(i + 1)]);
    return v;
}

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    int n = (level == 0) ? ri(1, 6) : (level == 1) ? ri(1, 8) : 100000;
    if (argc > 3) n = atoi(argv[3]);
    int step = (level == 0) ? 3 : (level == 1) ? 200000000 : 8000;

    printf("%d\n", n);
    if (level == 3) {                                 // a 升序、b 降序：答案 = n(n-1)/2
        for (int i = 0; i < n; i++) printf("%d%c", i + 1, i + 1 == n ? '\n' : ' ');
        for (int i = 0; i < n; i++) printf("%d%c", n - i, i + 1 == n ? '\n' : ' ');
        return 0;
    }
    for (int col = 0; col < 2; col++) {
        vector<int> v = distinctVals(n, step);
        for (int i = 0; i < n; i++) printf("%d%c", v[i], i + 1 == n ? '\n' : ' ');
    }
    return 0;
}