洛谷 P1908 逆序对

// P1908 逆序对 —— 能 AC 的那一版：归并排序顺手数
//
// 和本章正文那份 fast.cpp 是同一个算法，差别只在**规模**：
//   · 正文那份按 n = 10⁵ 写，用的是 vector<long long>；
//   · 洛谷 P1908 的 n 上限是 **5×10⁵**，而且值域到 10⁹。
//
// 两处必须盯住的：
//   ① cnt 必须是 long long —— n = 5×10⁵ 时最多 n(n-1)/2 ≈ **1.25×10¹¹** 对，
//      int 的上限才 2.1×10⁹，差了 58 倍。（这条为什么对拍抓不到，见解析页第 ④ 步。）
//   ② 读入 5×10⁵ 个数：关掉同步的 cin 就够（解析页第 ⑦ 步量过字节数）。

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

static const int MAXN = 500005;
static int a[MAXN], tmp_[MAXN];
static long long cnt = 0;

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 (a[i] <= a[j]) {            // ★ 必须是 <=：相等不算逆序对
            tmp_[k++] = a[i++];
        } else {
            cnt += mid - i + 1;        // ★ 左边剩下的全都比 a[j] 大
            tmp_[k++] = a[j++];
        }
    }
    while (i <= mid) tmp_[k++] = a[i++];
    while (j <= r)   tmp_[k++] = a[j++];
    for (int p = l; p <= r; p++) a[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];

    if (n > 0) mergeSort(0, n - 1);

    cout << cnt << "\n";
    return 0;
}

// P1908 第 ① 版：每一对都看一遍，O(n²)
//
// 思路无可挑剔 —— 逆序对的定义是什么，它就照着数什么。
// 而且它**答案是对的**：下面对拍 1200 轮，它和归并版一次都没差过。
//
// 它唯一的毛病是慢，而这道题的题面自己把话说死了：
//   「应该不会有人 O(n²) 过 50 万吧 —— 2018.8 chen_zhe」
//
// n = 5×10⁵ ⇒ 1.25×10¹¹ 次比较。解析页第 ② 步有外推出来的秒数。

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

static const int MAXN = 500005;
static int a[MAXN];

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];

    long long cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) cnt++;

    cout << cnt << "\n";
    return 0;
}

// P1908 ⚠ 错法二：`a[i] <= a[j]` 写成 `a[i] < a[j]`
//
// 相等的时候走了 else 分支 ⇒ 把「相等」也当成逆序对数了一遍，答案偏大。
//
// ★ 它和上面那个错法的性质完全不同：
//   · cnt 用 int：对拍**结构上**抓不到（小数据根本不可能溢出）；
//   · 这一个：对拍抓得到，但**取决于数据里有没有重复值** ——
//     而这道题的题面明写「注意序列中可能有重复数字」，官方样例里却一个重复都没有。
//   ⇒ 抓获率由**值域**说了算，和 n 关系不大。解析页第 ⑤ 步那张表是量出来的。

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

static const int MAXN = 500005;
static int a[MAXN], tmp_[MAXN];
static long long cnt = 0;

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 (a[i] < a[j]) {             // ⚠ 就是这里少了一个等号
            tmp_[k++] = a[i++];
        } else {
            cnt += mid - i + 1;
            tmp_[k++] = a[j++];
        }
    }
    while (i <= mid) tmp_[k++] = a[i++];
    while (j <= r)   tmp_[k++] = a[j++];
    for (int p = l; p <= r; p++) a[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];

    if (n > 0) mergeSort(0, n - 1);

    cout << cnt << "\n";
    return 0;
}

// 数据生成器（P1908 对拍用）：`./p1908Gen <seed> [level] [n]`
//
//   level 0（默认）★ **照题面随机**：值域 1..10⁹ —— 几乎不可能撞出重复值
//   level 1        ★ **值域 1..5** —— 同样的 n，重复值满地都是
//   level 2        ★ **完全倒序的排列** n, n-1, …, 1（逆序对最多的形状，答案恰好 n(n-1)/2）
//   level 3        完全升序（答案 0）＋ n = 0/1 那几个边界，值域 1..5 所以还会带上相等
//
//   第三个参数可以**指定 n**（默认小数据）—— 解析页第 ④ 步就是拿
//   `level 2, n = 65536` 和 `n = 65537` 这两条命令把溢出的那条线卡到个位的。
//
// ★ 这四档要回答的是**同一个问题的两半**：
//   `<=` 写成 `<` 只在**有重复值**的时候露馅 ——
//   而「有没有重复值」由**值域**说了算，和 n 关系不大。
//   ⇒ 照题面随机（level 0）抓不到它，不是因为轮数不够，是因为值域太宽。
//
// ⚠ 这四档**一个都抓不到 cnt 用 int 那个错** —— 那不是轮数问题，是算术问题：
//   n ≤ 12 时逆序对最多 66 个，而 int 的上限是 21 亿。见 p1908Count.cpp。

#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)); }

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 == 3) ? ri(0, 3) : ri(1, 12);
    if (argc > 3) n = atoi(argv[3]);
    printf("%d\n", n);

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (level == 2)      a[i] = n - i;            // ★ 严格倒序的排列，答案 = n(n-1)/2
        else if (level == 1) a[i] = ri(1, 5);
        else if (level == 3) a[i] = ri(1, 5);
        else                 a[i] = ri(1, 1000000000);
    }
    if (level == 3) sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    if (n == 0) printf("\n");
    return 0;
}

// P1908 ⚠ 错法一：cnt 用 32 位存 —— 全书最出名的 0 分写法
//
// 除了 cnt 的类型，和 p1908.cpp 一个字符都不差。
// 样例过、对拍 1200 轮全过、你在本地找不到任何理由怀疑它。
// 而它在洛谷上是 0 分。
//
// ⚠ 为什么这里写的是 `unsigned` 而不是真正的 `int`：
//   有符号整数溢出在 C++ 里是 **UB** —— 编译器可以假设它不发生，
//   于是 -O2 下这份代码的输出**不可复现**（换个编译器、换个优化等级就变）。
//   `unsigned` 的回绕是标准规定的，转回 int 打印之后
//   得到的正是你在洛谷上看到的那个负数。⇒ 这样这一页的数字才钉得住。
//
// 那条线在哪儿：p1908Count.cpp 把它算到了个位（提示：n = 65537）。

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

static const int MAXN = 500005;
static int a[MAXN], tmp_[MAXN];
static unsigned cnt = 0;               // ⚠ 就是这里。正解是 long long

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 (a[i] <= a[j]) {
            tmp_[k++] = a[i++];
        } else {
            cnt += (unsigned)(mid - i + 1);
            tmp_[k++] = a[j++];
        }
    }
    while (i <= mid) tmp_[k++] = a[i++];
    while (j <= r)   tmp_[k++] = a[j++];
    for (int p = l; p <= r; p++) a[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];

    if (n > 0) mergeSort(0, n - 1);

    cout << (int)cnt << "\n";          // 回绕之后再当成 int，就是洛谷上那个负数
    return 0;
}

// ★★★ 把「对拍为什么抓不到 int 溢出」算到个位
//
// 用法：./p1908Count            人话版
//       ./p1908Count csv        给 check:viz 用
//
// 正文（第 11 章第 ② 步那个警告框）说的是「小数据的答案才几十，对拍会全过」。
// 那句话是对的，但它容易被读成「溢出这种错，对拍原理上看不见」——
// 而这份程序想说明的恰恰相反：**对拍看得见，只要你把 n 开到题面顶格。**
// 它抓不到的真正原因是一个**成本**问题，而成本能算：
//
//   ① 触发线：完全倒序 / 随机排列，各要多大的 n 才可能越过 int 的上限；
//   ② 三档生成器（n ≤ 12 / n ≤ 1000 / 顶格 n ≤ 5×10⁵）各能抓到几轮；
//   ③ ★ 代价：**对拍的参照物是暴力**，而暴力在这些 n 上要跑多久。

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

static const long long INT_MAX_LL = 2147483647LL;
static const int NMAX = 500000;                 // 题面顶格

static vector<int> buf;
static long long mergeCount(vector<int>& a, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long c = mergeCount(a, l, mid) + mergeCount(a, mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) buf[k++] = a[i++];
        else { c += mid - i + 1; buf[k++] = a[j++]; }
    }
    while (i <= mid) buf[k++] = a[i++];
    while (j <= r)   buf[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = buf[p];
    return c;
}
static long long invOf(vector<int> a) {
    if (a.empty()) return 0;
    buf.assign(a.size(), 0);
    return mergeCount(a, 0, (int)a.size() - 1);
}
static vector<int> permOf(int n, mt19937& rng) {        // 手写 Fisher–Yates，跨机器可复现
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    for (int i = n - 1; i > 0; i--) swap(a[i], a[rng() % (unsigned)(i + 1)]);
    return a;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 触发线 */
    long long minNDesc = 0;
    for (long long n = 2; ; n++) if (n * (n - 1) / 2 > INT_MAX_LL) { minNDesc = n; break; }
    long long descInv  = minNDesc * (minNDesc - 1) / 2;
    long long descPrev = (minNDesc - 1) * (minNDesc - 2) / 2;
    int descWrapped = (int)(unsigned)(unsigned long long)descInv;

    int lo = 2, hi = 200000;                    // 随机排列：二分找第一个越界的 n（实测，不套公式）
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        mt19937 r(20260827u);
        if (invOf(permOf(mid, r)) > INT_MAX_LL) hi = mid; else lo = mid + 1;
    }
    int minNRand = lo;

    /* ② 三档生成器各抓几轮（100 轮；「抓到」= 真答案越过 int 上限） */
    const int ROUNDS = 100;
    const int CAPS[3] = {12, 1000, NMAX};
    int caught[3] = {0, 0, 0};
    long long bruteOps[3] = {0, 0, 0};          // 那 100 轮里暴力参照物要跑多少次比较
    for (int t = 0; t < 3; t++) {
        mt19937 rng(20260827u + (unsigned)t);
        for (int r = 0; r < ROUNDS; r++) {
            int n = (int)(rng() % (unsigned)CAPS[t]) + 1;
            bruteOps[t] += (long long)n * (n - 1) / 2;
            if (invOf(permOf(n, rng)) > INT_MAX_LL) caught[t]++;
        }
    }

    /* ③ 暴力有多贵：在 minNDesc 上真跑一次，拿到「每秒多少次比较」再外推 */
    int n = (int)minNDesc;
    vector<int> desc(n);
    for (int i = 0; i < n; i++) desc[i] = n - i;
    auto t0 = steady_clock::now();
    long long bcnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (desc[i] > desc[j]) bcnt++;
    double bruteMs = duration<double, milli>(steady_clock::now() - t0).count();
    double opsPerMs = (double)((long long)n * (n - 1) / 2) / max(0.001, bruteMs);
    double fullMin = (double)bruteOps[2] / opsPerMs / 60000.0;   // 顶格那 100 轮要多少分钟

    t0 = steady_clock::now();
    long long fcnt = invOf(desc);
    double fastMs = duration<double, milli>(steady_clock::now() - t0).count();

    if (csv) {
        printf("intMax,%lld\n", INT_MAX_LL);
        printf("minNDesc,%lld\ndescInv,%lld\ndescPrev,%lld\ndescWrapped,%d\n",
               minNDesc, descInv, descPrev, descWrapped);
        printf("minNRand,%d\n", minNRand);
        printf("rounds,%d\ncaught12,%d\ncaught1000,%d\ncaughtFull,%d\n",
               ROUNDS, caught[0], caught[1], caught[2]);
        printf("bruteOk,%d\nbruteSlower,%d\n", (bcnt == fcnt) ? 1 : 0, (bruteMs > fastMs * 50) ? 1 : 0);
        printf("fullMinutes,%.0f\n", fullMin);
        return 0;
    }

    printf("int 的上限：%lld\n\n", INT_MAX_LL);
    printf("① 什么样的 n 才**可能**溢出\n");
    printf("     完全倒序：n = %lld ⇒ %lld（还在里面）；n = %lld ⇒ %lld ★ 第一次越过，\n",
           minNDesc - 1, descPrev, minNDesc, descInv);
    printf("               塞进 int 变成 %d\n", descWrapped);
    printf("     随机排列：最小的 n = %d（实测，不是套 n²/4 的公式）\n\n", minNRand);
    printf("② 同一个 bug，三档生成器各抓到几轮（每档 %d 轮）\n", ROUNDS);
    printf("     n ≤ %6d（顺手写的）  %3d / %d\n", CAPS[0], caught[0], ROUNDS);
    printf("     n ≤ %6d              %3d / %d\n", CAPS[1], caught[1], ROUNDS);
    printf("     n ≤ %6d（题面顶格）  %3d / %d   ★ 抓得到，而且很轻松\n\n", CAPS[2], caught[2], ROUNDS);
    printf("③ ★ 那为什么大家还是抓不到？因为对拍的参照物是**暴力**\n");
    printf("     暴力在 n = %lld 上：%.0f 毫秒（%lld 次比较）；归并只要 %.1f 毫秒\n",
           minNDesc, bruteMs, (long long)n * (n - 1) / 2, fastMs);
    printf("     ⇒ 顶格那 %d 轮，光暴力那一侧就要 **约 %.0f 分钟**（按上面那个速率外推）。\n\n", ROUNDS, fullMin);
    printf("  ⇒ 结论不是「对拍看不见溢出」，是「顶格对拍的参照物不能是暴力」。\n");
    printf("    而这个 bug 有更便宜的抓法：n(n-1)/2 和 2³¹ 比一下 —— 一句算术。\n");
    return 0;
}

// P1908 ★ 另一条路：离散化 + 树状数组（第 38 章的写法，提前看一眼）
//
// 和归并完全无关的一条路 —— 而这正是它在这一页的价值：
// **两条互不相干的路算出同一个数**，比「同一条路跑两遍」有说服力得多。
//
// 思路：从右往左扫，每遇到一个 a[i]，问「右边已经放进去的数里，有几个比它小」。
//   那就是以 i 为左端点的逆序对个数。树状数组按「值」建，单点加、前缀和查。
//
// ⚠ 值域到 10⁹，不能直接开数组 ⇒ **离散化**：排序去重后用「排名」当下标。
// ⚠ cnt 一样要 long long（换了算法不换这条线）。

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

static const int MAXN = 500005;
static int a[MAXN], b[MAXN], tree_[MAXN];
static int m;                                  // 去重之后有多少种值

static void add(int i) { for (; i <= m; i += i & -i) tree_[i]++; }
static int ask(int i) { int s = 0; for (; i > 0; i -= i & -i) s += tree_[i]; return s; }

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]; b[i] = a[i]; }

    sort(b, b + n);
    m = (int)(unique(b, b + n) - b);
    for (int i = 0; i < n; i++)
        a[i] = (int)(lower_bound(b, b + m, a[i]) - b) + 1;   // 1..m 的排名

    long long cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        cnt += ask(a[i] - 1);      // 右边严格小于 a[i] 的个数（相等的不算）
        add(a[i]);
    }

    cout << cnt << "\n";
    return 0;
}