题目链接:https://ac.nowcoder.com/acm/contest/543/D
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

兔子最近喜欢上了逆序对。
一个逆序对(i,j) 需要满足 i < j 且 ai > aj
兔子觉得只是求一个序列的逆序对个数太没有意思了。
于是兔子想到了一个更有趣的问题！
兔子可以把区间[L,R] 反转，例如序列{1,2,3,4} 反转区间[1,3] 后是{3,2,1,4}。
兔子有m次反转操作，现在兔子想知道每次反转后逆序对个数是奇数还是偶数，兔子喜欢偶数，而讨厌奇数。
请注意，每一次反转操作都会对原序列进行改变。例如序列{1,2,3,4} 第一次操作区间[1,2] 后变成{2,1,3,4} 第二次反转区间[3,4] 后变成 {2,1,4,3}

输入描述

第一行一个整数 n，表示序列的大小。
第二行 n 个整数ai 表示序列的各个元素。
第三行一个整数m，表示操作个数。
接下来 m 行，每行两个整数 l，r，表示反转的区间。

输出描述

输出共m行每行一个字符串，表示反转后序列逆序对个数的奇偶性，如果是逆序对个数奇数，输出"dislike"(不含引号)，如果是偶数，输出"like"。

示例1

输入

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

输出

dislike
like
like
dislike

说明

注意：以下的(i,j)指的是位置 i 和位置 j
a={2,1,3,4} 的逆序对是 (1,2) 共1个，1是奇数，所以是dislike
a={2,1,4,3} 的逆序对是 (1,2) (3,4)共2个,2是偶数，所以是like
a={3,4,1,2} 的逆序对是 (1,3) (1,4) (2,3) (2,4)共4个,4是偶数，所以是like
a={3,1,4,2} 的逆序对是 (1,2) (1,4) (3,4) 共3个,3是奇数，所以是dislike

备注:

对于20%的数据
1 ≤ n ≤ 100 1 ≤ m ≤ 10 
对于40%的数据
1 ≤ n ≤ 2000 1 ≤ m ≤ 50 
对于60%的数据
1 ≤ n ≤ 2000 1 ≤ m ≤ 10^4
对于100%的数据
1 ≤ n ≤ 10^5 1 ≤ m ≤ 2*10^6
对于所有数据 l ≤ r且 ai 是n的一个排列，即ai互不相同且ai ≤ n
由于读入数据较大，建议使用快速读入。

解题思路

我们可以用归并排序求出逆序对个数，然后我们可以知道每交换一对元素，就会改变逆序对个数的奇偶性，所以我们可以根据每次区间翻转的大小来判断奇偶。

#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
inline int read() {
    int ans = 0, f = 1;
    char ch = getchar();
    if (ch == '-')
        f *= -1;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ans = ans * 10 + ch - '0';
        ch = getchar();
    }
    return ans * f;
}
void Merge(int A[], int L, int Mid, int R) {
    int *Temp = (int *)malloc((R - L + 1) * sizeof(int));
    int p = L, q = Mid, k = 0;
    while (p <= Mid - 1 && q <= R) {
        if (A[p] <= A[q])
            Temp[k++] = A[p++];
        else {
            Temp[k++] = A[q++];
            ans += Mid - p;
        }
    }
    while (p <= Mid - 1)
        Temp[k++] = A[p++];
    while (q <= R)
        Temp[k++] = A[q++];
    for (int i = 0; i < k; i++)
        A[i + L] = Temp[i];
}
void MSort(int A[], int L, int RightEnd) {
    if (L < RightEnd) {
        int mid = (L + RightEnd) / 2;
        MSort(A, L, mid);
        MSort(A, mid + 1, RightEnd);
        Merge(A, L, mid + 1, RightEnd);
    }
}
int main() {
    int n, t, l, r, A[100005];
    n = read();
    for (int i = 0; i < n; i++)
        A[i] = read();
    MSort(A, 0, n - 1);
    ans %= 2;
    scanf("%d", &t);
    while (t--) {
        l = read(), r = read();
        int p = r - l + 1;//区间长度 
        if ((p * (p - 1) / 2 % 2))//判断区间反转次数p*(p-1)/2的奇偶 
            ans ^= 1;//改变奇偶性 
        if (ans)
            printf("dislike\n");
        else printf("like\n");
    }
    return 0;
}