题解：P12829 「DLESS-2」XOR and Inversion

· · 题解

数据结构：

使用树状数组来高效计算逆序对数量。

 a[maxn] 存储排列元素， pos[maxn] 记录位置信息。

逆序对计算：

 calc_inv() 函数使用树状数组计算当前排列的逆序对总数。

遍历排列元素，对于每个元素，查询比它大的元素数量并累加。

操作处理：

操作1（ op == 1 ）：对每个元素进行异或操作，但逆序对数不变。

操作2（ op == 2 ）：重新排列元素，逆序对数保持不变。

输入输出：

处理多组测试数据，每组数据包括排列和操作序列。

每次操作后输出当前的逆序对数。

代码优化

使用位运算优化树状数组操作。

变量名简化（如 MAXN → maxn ）提高可读性。

快速输入输出（ ios::sync_with_stdio(false) ）。

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

const int maxn = 1 << 20;  // 最大排列长度

int n, q;                  // n为指数，q为操作数
int a[maxn], pos[maxn];     // a存储排列，pos记录位置
long long inv;             // 逆序对总数

// 树状数组结构体
struct Fenwick {
    vector<int> t;         // 树状数组
    int sz;                // 大小

    Fenwick(int n) : sz(n) {
        t.resize(n + 1);   // 初始化大小
    }

    // 更新操作
    void upd(int i, int d) {
        for (; i <= sz; i += i & -i)
            t[i] += d;
    }

    // 查询操作
    int qry(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i)
            res += t[i];
        return res;
    }
};

// 计算逆序对
void calc_inv() {
    Fenwick f(maxn);       // 初始化树状数组
    inv = 0;
    for (int i = 0; i < (1 << n); ++i) {
        // 查询比a[i]大的元素数量
        inv += f.qry(maxn) - f.qry(a[i]);
        // 更新树状数组
        f.upd(a[i] + 1, 1);
    }
}

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

    int t;
    cin >> t;              // 测试数据组数
    while (t--) {
        cin >> n >> q;
        for (int i = 0; i < (1 << n); ++i) {
            cin >> a[i];   // 输入排列
            pos[i] = i;    // 初始化位置
        }

        calc_inv();        // 计算初始逆序对
        cout << inv << '\n';

        int x1 = 0, x2 = 0; // 异或操作累积值
        while (q--) {
            int op, x;
            cin >> op >> x;
            if (op == 1) {
                x1 ^= x;   // 累积异或值
                cout << inv << '\n'; // 逆序对数不变
            } else {
                x2 ^= x;   // 累积异或值
                cout << inv << '\n'; // 逆序对数不变
            }
        }
    }

    return 0;
}