逆序數技巧 - 牛客

鏈接：https://ac.nowcoder.com/acm/contest/308/D
來源：牛客網

題目描述

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)的個數。

輸入描述:

第一行包括一個正整數n(1≤n≤10^5)。
接下來一行，包括一個長度為n的序列，序列為1到n的一種排列。
第三行包括一個正整數q(1≤q≤10^5)。
接下來q行，每行包括三個正整數L,R,k(1≤L≤R≤n，1≤k≤10^9)。
所有變量的含義題面均有給出。

輸出描述:

在每次操作后，逆序數如果是奇數，就輸出1，如果是偶數，就輸出0。

示例1

輸入

復制

4
2 3 1 4
3
1 3 2
2 4 1
2 3 1

輸出

復制

0
0
1

說明

原序列為：2 3 1 4
第一次操作后，序列變為：3 1 2 4，逆序數為2，所以答案為0。
第二次操作后，序列變為：3 4 1 2，逆序數為4，所以答案為0。
第三次操作后，序列變為：3 1 4 2，逆序數為3，所以答案為1。

題意 ： 每次選擇一個區間循環變換， 求整個串的逆序數是奇數還是偶數
思路分析 ： 
　　首先可以很容易求出整個序列的逆序數是多少，然后循環移位某一個區間時，會有個小特點就是，移動一步時，逆序數變化只會取決于他前面可操作區間的長度，，若其為偶數，則逆序數的奇偶不會發生變化，否則會產生變化。

代碼示例 ：
　　

int n;
int a[maxn];
int l, r, k;
int c[maxn];
int lowbit(int x){return x&(-x);}
void add(int pos){for(int i = pos; i <= n; i += lowbit(i)){c[i] += 1;}
}
int query(int pos){int res = 0;for(int i = pos; i ; i -= lowbit(i)){res += c[i];}return res;
}
int ans = 0;
void solve() {for(int i = 1; i <= n; i++){add(a[i]);ans += i-query(a[i]);ans = ans&1;}
}int main() {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);cin >> n;for(int i = 1; i <= n; i++) scanf("%d", &a[i]);int q;solve();//printf("+++++ %d \n", ans);cin >> q;while(q--){scanf("%d%d%d", &l, &r, &k);k = k % (r-l+1);int len = (r-l)*k;if (len&1) ans += 1;ans = ans&1;printf("%d\n", ans);}return 0;
}

?