题解 | #兔子的逆序对#

题目

链接：https://ac.nowcoder.com/acm/problem/20861 来源：牛客网

兔子最近喜欢上了逆序对。
一个逆序对(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}

分析

先通过归并求得初始状态的逆序数奇偶性，而后续操作只需判断元素交换次数。
交换偶数次，奇偶性不变
交换奇数次，奇变偶，偶变奇
翻转$[l,r][l,r]$，需要交换$(r-l+1)\mathrm{/}2(r-l+1)/2$次。

AC代码

#include<bits/stdc++.h>
using namespace std;
int num=0,a[100005],temp[100005];
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void mergesort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    mergesort(q,l,mid),mergesort(q,mid+1,r);
    
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else{
            temp[k++]=q[j++];
            num+=mid-i+1;
        }
    }
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}
int main()
{
    int n;int flag;
    n=read();
    for(int i=0;i<n;i++) a[i]=read();
    mergesort(a,0,n-1);
    if(num&1) flag=0;
    else flag=1;
    int m;m=read();
    while(m--)
    {
        int l,r;
        l=read();r=read();
        int d=(r-l+1)/2;
        if(d&1) flag=1-flag;
        if(flag)  printf("like\n");
        else printf("dislike\n");
    }
}