tokitsukaze and Inverse Number（樹狀數組求逆序對及逆序對性質）

題目連結：

tokitsukaze and Inverse Number

題意：

tokitsukaze給你一個長度為n的序列，這個序列是1到n的一種排列。

然後她會進行q次操作。每次操作會給你L R k這三個數，表示區間[L,R]往右移動k次。

移動一次的定義是：一個數的位置是P(L≤P≤R-1)，它往右移動後就會在P+1這個位置上；如果一個數在R這個位置，它會移動到L這個位置。

在每次操作結束後，tokitsukaze想讓你算出現在這個序列的逆序數的多少，簡單起見，你隻需要告訴她現在這個序列的逆序數是奇數還是偶數就行了。

提示：序列的逆序數指的是：a[i]>a[j](i<j)，滿足條件的(i,j)的個數。

思路：

原序列的逆序對數可通過樹狀數組求解：

這裡樹狀數組維護的是字首和，樹狀數組c[i]表示大小為 i 的數的個數，那麼字首和就是大小小于等于 i 的數的個數。依次周遊數組，設目前位置為 i ，先用樹狀數組計算小于該數的數的個數num，那目前逆序對數為：原逆序對數+ i - num ，然後把這個數插入到樹狀數組，add(a[i],1)，表示c[a[i]]+=1 。周遊完數組即可得總逆序對數。

逆序對結論：

1到n的排列。任意交換兩個數，逆序數奇偶性發生改變。

證明：

設排列為a1 a2 .. al a b b1 b2 .. bm  對換a，b ->  a1 a2 .. al b a b1 b2 .. bm

除a，b外，其他元素的逆序數不變。

當a<b時，對換後a的逆序數+1不變，b的逆序數不變。

當a>b時，對換後a的逆序數不變，b的逆序數-1。

是以，對換相鄰兩個元素，排列逆序數改變奇數個。

設排列為a1 a2 .. al a b1 b2 .. bm b c1 c2 .. cn，現在來對換a，b：

a1 a2 .. al a b b1 b2 .. bm c1 c2 .. cn  -> b經過了 m 次相鄰對換 。

a1 a2 .. al b b1 b2 .. bm a c1 c2 .. cn -> a經過了 m+1 次相鄰對換。

總共經過了 2*m+1 次相鄰對換。

是以，一個排列中的任意兩個元素對換，排列逆序數改變奇數個。

是以，本題 ans = （操作前逆序數 + 需要交換多少次才能變成操作後的序列（不需要求最小操作數））%2 。

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

typedef long long ll;

const int MAX = 1e5+10;
const ll mod = 1e9+7;

int n;
int a[MAX];
int c[MAX];

int lowbit(int x){
    return x&(-x);
}

void add(int k,int x){
    while(k<=n){
        c[k]+=x;
        k+=lowbit(k);
    }
}

int sum(int x){
    int val=0;
    while(x){
        val+=c[x];
        x-=lowbit(x);
    }
    return val;
}

int main()
{
    scanf("%d",&n);
    ll num=0; // 逆序數個數
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        num+=(i-1)-sum(a[i]);
        add(a[i],1);
    }
    int q;
    scanf("%d",&q);
    while(q--){
        ll l,r,k;
        scanf("%lld%lld%lld",&l,&r,&k);
        num+=(r-l)*k;
        num%=2;
        if(num%2==0){
            printf("0\n");
        }
        else{
            printf("1\n");
        }
    }
    return 0;
}