关于逆序对的一些整理

1.求逆序对的方法：树状数组，O（nlog）的复杂度

树状数组功能：用log的复杂度求出一个数组里面所有大于某一个数字的和，即sum=a1+a2+。。。。+an，其中a1。。an全都小于目标值x

做法：对于数组元素ai来说，他的逆序对个数是i前面的所有比ai大的数字，但应为树状数组只能找前面n个数字的和，即找比ai小的数字，因此可以先把a数组倒过来，这样就是求ai这个数字前面比他

小的数字有几个，就是逆序对个数

逆序对的一些定理：

　　1.对于一个数组来说，如果交换其相邻两个元素，整个数组的逆序对个数的奇偶性会反转，即只有逆序对个数+1或-1两种情况

　　2.对于1--n的任意排列，交换其中任意两个元素即可让其奇偶性发生反转

　　证明：假如选定数组a中的ai跟aj两个元素，由定理1得，可以用2m+1次（m为i和j的距离）相邻元素之间的交换达到该两个元素互换的目的。因此定理成立。

例题：D-tokitsukaze and Inverse Number_牛客练习赛33 (nowcoder.com)

代码实现：

#include <bits/stdc++.h>
using namespace std;
const long long maxx = 0x3f3f3f3f3f3f3f3f;
const long long minn = 0xc0c0c0c0c0c0c0c0;
const double pi = 4.0 * atan(1.0);
#define int long long
#define f(i, n, m) for (long long i = n; i <= m; ++i)
#define unf(i, n, m) for (long long i = n; i >= m; --i)
#define kong NULL
#define debug cout << "sss" << endl;

int n;
int lowbit(int x)
{
    return (x & -x);
}
void add(int x, int v, vector<int> &tree)
{
    while (x <= n)
    {
        tree[x] += v;
        x += lowbit(x);
    }
}
int query(int x, vector<int> &tree)
{
    int sum = 0;
    while (x >= 1)
    {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}
void solve()
{

    cin >> n;
    vector<int> que((n<<2 )+10, 0);
    vector<int> tree((n<<2 )+10, 0);
    int zhi = 0;
    f(i, 1, n)
    {
        cin >> que[i];
    }
    unf(i, n, 1)
    {
        add(que[i], 1, tree);
        zhi += query(que[i] - 1, tree);
    }
    // cout << zhi << endl;

    int m;
    cin >> m;
    f(i, 1, m)
    {
        int l, r, k;
        cin >> l >> r >> k;
        zhi%=2;
         if(((r-l)&k&1)==1)zhi^=1;
        cout << zhi  << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
//     int _;
//     cin >> _;
//     while (_--)
//     {
//         solve();
//     }
     solve();
    return 0;
}