Codeforces 301E Infinite Inversions：樹狀數組 + 離散化 解法詳解

題目大意

有一個無限遞增序列 p = {1, 2, 3, ...}。進行 n 次交換操作 swap(a, b)，交換位置 a 和 b 的元素。求最終序列的逆序對數量（即 i < j 且 p[i] > p[j] 的對數）。

約束：n ≤ 1e5，a, b ≤ 1e9。

核心觀察

1. 只有參與交換的位置值會發生變化，其餘位置值仍等於其下標（即 p[i] = i）。
2. 只需關注所有出現過的交換位置集合，將其離散化後構建有限序列。
3. 交換操作本質上是對這些關鍵位置值的排列變換。

算法流程

步驟 1：模擬交換得到最終映射

使用 map<int, int> Q 記錄位置→值的映射。初始時 Q[x] = x。每次交換 swap(Q[a], Q[b])。最終 Q 中只包含被交換過的位置。

步驟 2：離散化值域

將 Q 的所有值收集到向量 sec，排序去重，構建值→排名的映射，用於樹狀數組索引。

步驟 3：樹狀數組計算逆序對

按位置從大到小遍歷 Q 的鍵值對 (pos, val)：

• 查詢樹狀數組中小於 val 的個數，累加到答案（這是標準逆序對統計）。
• 將當前 val 的排名加入樹狀數組。
• 關鍵優化：考慮當前位置 pos 與前一個位置 prev_pos 之間的連續未交換區間 [prev_pos+1, pos-1]。這段區間內的值等於下標，單調遞增。其對逆序對的貢獻可通過數學公式批量計算，避免逐個處理。

區間貢獻計算

設區間長度 w = (pos - 1) - (prev_pos + 1) + 1 = pos - prev_pos - 1。若 w > 0：

• 區間內每個值 x 右側小於它的數 = Query(rank(x) - 1)。由於區間值連續且排名連續，總貢獻 = w * Query(rank(prev_pos+1) - 1)。
• 區間作為整體向左貢獻：需在樹狀數組中 rank(prev_pos+1) - 1 位置增加 w，表示這 w 個元素對左側更大元素的貢獻。

關鍵代碼片段

map<int, int> Q;
for (int i = 0; i < n; ++i) {
    int L, R; cin >> L >> R;
    if (!Q.count(L)) Q[L] = L;
    if (!Q.count(R)) Q[R] = R;
    swap(Q[L], Q[R]);
}

vector<pair<int, int>> v;
vector<int> sec;
for (auto& p : Q) {
    v.push_back(p);
    sec.push_back(p.second);
}
sort(sec.begin(), sec.end());
sec.erase(unique(sec.begin(), sec.end()), sec.end());

int tot = v.size();
memset(c, 0, sizeof(c[0]) * (tot + 10));
long long ans = 0;

for (int i = tot - 1; i >= 0; --i) {
    int Loc = lower_bound(sec.begin(), sec.end(), v[i].second) - sec.begin() + 1;
    ans += Query(Loc - 1); // 標準逆序對
    if (i == 0) break;
    Modify(Loc, 1, tot);

    long long w = (v[i].first - 1) - v[i-1].first; // 間隙長度
    if (w < 1) continue;
    Loc = lower_bound(sec.begin(), sec.end(), v[i-1].first + 1) - sec.begin() + 1;
    ans += w * Query(Loc - 1); // 區間右側貢獻
    Modify(Loc - 1, w, tot);   // 區間左側貢獻
}
cout << ans << endl;

複雜度分析

• 時間：O(n log n)，主要來自排序、離散化、樹狀數組操作。
• 空間：O(n)，存儲映射、離散化數組、樹狀數組。

總結

本題巧妙結合了離散化與樹狀數組，關鍵在於識別出「未交換區間值等於下標」的性質，並推導出區間批量貢獻公式，將無限序列問題轉化為有限尺度的高效計算。