题解 CF911D 【Inversion Counting】

· · 题解

蒟蒻的第一篇题解，对大佬来说可能有点啰嗦

首先我们要仔细看题，要求的是[L, R]翻转后整个序列中逆序对的奇偶性，不是[L, R]中逆序对的奇偶性，也不是逆序对的总数

接着我们就可以思考[L, R]中的逆序对与整个序列逆序对的关系，我们会惊奇地发现，由于[L, R]中的数翻转之后与[L, R]区间之外的数的相对位置并不会发生改变，所以除了a, b两个数都属于[L, R]的数对(a, b)，其他的数对都不会发生变化，所以只要知道区间[L, R]中逆序对奇偶性的变化，就可以知道整个序列中奇偶性的变化

那如何求出这个变化呢? 思考一下逆序对的定义:

对于给定的一段正整数序列，逆序对就是序列中a_i>a_j且i<j的有序对 ——P1908 逆序对

接下来是本道题的主要难点:

对于任意数对(a_i, a_j)\, (i<j)，只存在以下三种情况:

显然我们可以得到以下等式: 逆序对数量 + 相等的数对的数量 + 顺序对数量 = 数对总数 其中逆序对在区间翻转后会变成顺序对，顺序对会变成逆序对，而相等的数对还是相等的数对 设$m = $ 逆序对数 + 翻转之后的逆序对数 = 数对总数 - 相等的数对数量，那么如果$m\&1 == 1$，奇偶性改变；如果$m\&1 == 0$，奇偶性不变 数对总数用很容易就可以算出$ = \frac {n(n-1)}{2} \;\; (n = R - L + 1)$，那么相等的数对个数怎么求呢？ 答案是不用求~~，这是我经过对人生和社会的大思考后得出的结论~~，其实这是翻译的锅，仔细看一眼英文题面，说的是： > A permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array 对，permutation就是`next_permutation();`里的那个permutation，排列的意思，也就是说$1$~$n$都各出现一次，互不重复，那么只要求出初始逆序对个数，然后对于每一个询问，我们$O(1)$地求出[L, R]内数对总数的奇偶性就可以了 代码$\downarrow 
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int m, x, y, num;

int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x;
}

#define lowbit(x) x&-x

int n, a[600000], b[600000], c[600000];

void add(int x) {
    for(int i = x; i <= n; i += lowbit(i)) ++c[i];
} 

long long sum(int x) {
    long long ans = 0;
    for(int i = x; i; i -= lowbit(i)) ans += c[i];
    return ans;
}

int main(void) {
    long long ans = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i) a[i] = b[i] = read();
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; ++i) a[i] = n - (lower_bound(b + 1, b + n + 1, a[i]) - b) + 1; 
    for(int i = 1; i <= n; ++i) {
        ans += sum(a[i] - 1);
        add(a[i]);
    }
    //上面是树状数组求逆序对个数，这题归并甚至暴力求逆序对因该也是可以的
    ans &= 1;
    m = read();
    while(m--)
    {
        x = read();
        y = read();
        num = y-x+1;
        num = num*(num-1)/2;//求数对总数
        if((num)&1) ans = (ans+1)&1;//判断奇偶性是否改变
        if(ans) puts("odd");
        else puts("even");
    }
}