题解 | #兔子的逆序对#

反转一个区间

1. 不影响区间内的数与区间外的数构成的逆序对个数。
2. 对于这个区间，假设它原来有$xx$个逆序对，反转后变成$N-x,NN-x,N$为序对个数，则

由于2x是偶数，如果这个区间有奇数个序对，反转后对整体的改变是奇数的，如果有偶数个，对整体的影响是偶数的。通过归并排序算出整体的逆序对个数，判断其奇偶性，再判断区间序对数的奇偶性就能知道反转后的奇偶性。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, m;
    static int[] help = new int[100010];
    static int[] arr = new int[100010];
    static int[] sums = new int[100010];
    static int cnt = 0;
    public static void merge(int l, int mid, int r) {
        int i = l, j = mid + 1;
        for(int k = l; k <= r; ++k) {
            if((j > r) || (i <= mid && arr[i] <= arr[j])) {
               help[k] = arr[i++];
            } else {
                cnt += mid - i + 1;
                help[k] = arr[j++];
            }
        }
        for(int k = l; k <= r; ++k)
            arr[k] = help[k];
    }
    public static void mergeSort(int l, int r) {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(l , mid);
        mergeSort(mid + 1 , r);
        merge(l, mid, r);
    }
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        String[] strs = bf.readLine().split(" ");
        for(int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(strs[i]);
        }
        for(int i = 1; i <= n; ++i) {
            sums[i + 1] = sums[i] + i;//预先处理序对数
        }
        mergeSort(0, n - 1);
        m = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; ++i) {
            strs = bf.readLine().split(" ");
            int l = Integer.parseInt(strs[0]);
            int r = Integer.parseInt(strs[1]);
            int k = sums[r - l + 1];
            if((cnt & 1) == 1) {
                if((k & 1) == 1) {
                    sb.append("like\n");
                    ++cnt;//记得改变奇偶性
                }
                else
                    sb.append("dislike\n");
            } else {
                if((k & 1) == 1) {
                    ++cnt;
                    sb.append("dislike\n");
                }  
                else
                    sb.append("like\n");
            }
        }
        System.out.print(sb);
	} 
}