逆序对的三种求法

逆序数是ACM比较基础的问题了，逆序数线性代数里面给有定义。每个数列都有一个标准排序，当某一对元素的先后顺序与标准次序不同的时候，就构成了一个逆序。逆序对当然不能暴力求啊，要不然时间复杂度O（n^2），太高了。这里常用的几种求逆序对的方法就是归并排序，树状数组，线段树。
现在找一道题题目练练手吧！
codeforces 987E Petr and Permutations

---

归并排序

const int N=1000010;
int a[N],b[N],ans;
void merge_sort(int l,int r){
    if(l>=r)return;
    int m=(l+r)>>1;
    merge_sort(l,m);
    merge_sort(m+1,r);
    int cur1=l,cur2=m+1,cur=0;
    while(cur1<=m&&cur2<=r){
        if(a[cur1]>a[cur2]){
            ans+=r-cur2+1;
            b[cur++]=a[cur1++];
        }
        else b[cur++]=a[cur2++];
    }
    while(cur1<=m)b[cur++]=a[cur1++];
    while(cur2<=r)b[cur++]=a[cur2++];
    while(cur--)a[l+cur]=b[cur];
}

归并排序的时候从大到小排，然后稍加分析，还是特别简单的。

---

线段树

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
#define eps 1e-8
#define lson l,m,td<<1
#define rson m+1,r,td<<1|1
#define INF 0x3f3f3f3f
#define clear(a) memset(a,0,sizeof a)
#define clear_1(a) memset(a,-1,sizeof a)
#define line puts("");
#define LOCALR freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#define LOCALW freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
using namespace std;
/*******************************************************************/
/*******************************************************************/
template<class T>
inline int read(T &x){
    char ch;
    bool flag=false;
    if((ch=getchar())==EOF)return -1;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=true;
    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
    return 1;
}
template<class T>
inline void write(T x,bool isnewline=false){
    static const int maxlen=100;
    static char s[maxlen];
    if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int len=0;
    for(;x;x/=10)s[len++]=x%10+'0';
    if(isnewline)puts(s);
    else for(int i=len-1;i>=0;i--)putchar(s[i]);
}
/*******************************************************************/
/*******************************************************************/
const int N=1000010;
int in[N],out[N],len,tree[N<<2],ans;
template<class T>
int search(T vaule){
    int l=1,r=len,m;
    while(l<=r){
        m=(l+r)>>1;
        if(out[m]==vaule)return m;
        else if(out[m]<vaule)l=m+1;
        else r=m-1;
    }
}
void build_tree(int l,int r,int td){
    if(l==r)return;
    else{
        int m=(l+r)>>1;
        build_tree(lson);
        build_tree(rson);
    }
}
void updata(int l,int r,int td,int to){
    if(l==r&&l==to)tree[td]++;
    else{
        int m=(l+r)>>1;
        if(m>=to)updata(lson,to);
        else if(m<to)updata(rson,to);
        tree[td]=tree[td<<1]+tree[td<<1|1];
    }
}
int Query(int l,int r,int td,int L,int R){
    if(R<L)return 0;
    if(l==L&&r==R)return tree[td];
    else{
        int m=(l+r)>>1;
        if(m<L)return Query(rson,L,R);
        else if(m>=R)return Query(lson,L,R);
        else return Query(lson,L,m)+Query(rson,m+1,R);
    }
}
int main(){
    int n;read(n);
    for(int i=1;i<=n;i++)read(in[i]),out[i]=in[i];
    sort(out+1,out+1+n);
    len=unique(out+1,out+1+n)-out-1;
    //build_tree(tree);
    for(int i=1;i<=n;i++){
        int t=search(in[i]);
        ans+=Query(1,len,1,t+1,len);
        updata(1,len,1,t);
    }
    if((ans+n)&1)printf("Um_nik\n");
    else printf("Petr\n");
    return 0;
}

树状数组

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
#define eps 1e-8
#define lson l,m,td<<1
#define rson m+1,r,td<<1|1
#define INF 0x3f3f3f3f
#define clear(a) memset(a,0,sizeof a)
#define clear_1(a) memset(a,-1,sizeof a)
#define line puts("");
#define LOCALR freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#define LOCALW freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
using namespace std;
/*******************************************************************/
/*******************************************************************/
template<class T>
inline int read(T &x){
    char ch;
    bool flag=false;
    if((ch=getchar())==EOF)return -1;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=true;
    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
    return 1;
}
template<class T>
inline void write(T x,bool isnewline=false){
    static const int maxlen=100;
    static char s[maxlen];
    if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int len=0;
    for(;x;x/=10)s[len++]=x%10+'0';
    if(isnewline)puts(s);
    else for(int i=len-1;i>=0;i--)putchar(s[i]);
}
/*******************************************************************/
/*******************************************************************/
const int N=1000010;
int in[N],out[N],a[N],len,ans;
template<class T>
int search(T vaule){
    int l=1,r=len,m;
    while(l<=r){
        m=(l+r)>>1;
        if(out[m]==vaule)return m;
        else if(out[m]<vaule)l=m+1;
        else r=m-1;
    }
}
void updata(int x){
    while(x<=len){
        a[x]++;
        x+=lowbit(x);
    }
}
int Query(int x){
    int sum=0;
    while(x){
        sum+=a[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){
    int n;read(n);
    for(int i=1;i<=n;i++)read(in[i]),out[i]=in[i];
    sort(out+1,out+1+n);
    len=unique(out+1,out+1+n)-out-1;
    for(int i=1;i<=n;i++){
        int t=search(in[i]);
        ans+=i-1-Query(t);
        updata(t);
    }
    if((ans+n)&1)printf("Um_nik\n");
    else printf("Petr\n");
    return 0;
}