Inversioin Counting

Inversioin Counting

这题还是比较简单的，可惜上次比赛时脑袋短路，一直卡在C题上了，这题看都没有看，导致掉了rating.....

题目来源:Codeforces

这道题看完题目以后，立刻就想到了以前学过的逆序对的一些性质。其中有一个性质是:消除一个逆序对的步数一定是奇数。虽然和这题没有太大的关系，但是由此认为这题可以最终推出一个较为简单的数学公式。

那么，这题让我们输出的是每次交换后的逆序对数的奇偶性，由此我们可以就每次交换来分析其对逆序对数的影响。

题解

在此之前，显然可以得知，每次对区间翻转时只会对区间内的逆序对数造成影响。即只有对于$ i,j \(，由\)i,j$构成的逆序对会变化。并且是逆序对变为"正序对"，"正序对"变为逆序对。

首先，我们假设在区间\([l,r]\)共\(x(x=r-l+1)\)个数当中共有$ w $个逆序对。

与此同时，我们可以得出在这\(x\)个数中，我们有\(C^2_n\)个数对。

所以说，我们当前共有$ C^2_n - m $ 个 "正序对"，当我们对当前的区间进行翻转时，它们便变成了逆序对。

所以，当每次翻转前\(m\)的奇偶性已知时，若我们知道\(C^2_n\)的奇偶性，便可算出最后每次操作后的奇偶性。

每次操作后\(m\)的变化率$ m = C^2_n - m*2 \(,所以当\)C^2_n$为奇数时答案奇偶性取反，偶数时则不变。

因为$ C^2_n = \(，所以只要\)n%4=0\(或\)(n-1)%4=0\(，\)C^2_n$就是偶数，否则为奇数。

由此，我们只要在读入数组后先算出逆序数的奇偶性，然后每读入一个\(l,r\)，再如此计算就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <cstdio>

int a[1510];

int main()
{
trueint n;
truescanf("%d",&n);
truefor (int i = 1; i<=n; i++)
truetruescanf("%d",&a[i]);

truebool b = true;
truefor (int i = 2; i<=n; i++)
truetruefor (int j = 1; j<i; j++)
truetruetrueif (a[j] > a[i])
truetruetruetrueb = !b;
/*
	if (b)
		printf("even\n");
	else printf("odd\n");
*/
trueint m;
truescanf("%d",&m);
truefor (int i = 1; i<=m; i++)
true{
truetrueint l,r;
truetruescanf("%d%d",&l,&r);
truetrueint x = r-l+1;
truetrueif (x%4!=0 && (x-1)%4!=0)
truetruetrueb = !b;
true
truetrueif (b)
truetruetrueprintf("even\n");
truetrueelse printf("odd\n");
true}
}