逆序对 - PhantomAgony - Vijos

分享
xuyifeng LV 10 MOD @ 2017-07-27 10:49:50

逆序对可以用归并排序，树状数组来解决，下面是用树状数组解决的AC代码：

#include<cstdio>

#ifdef WIN32
#define outl "%I64d"
#else
#define outl "%lld"
#endif

using namespace std;

typedef long long LL;
const int MAXN = 1000005;
int n, a[MAXN], c[MAXN];
LL ans;

int low_bit(int x){
    return x & -x;
}

void insert(int x){
    while(x < 1000000){
        c[x]++;
        x += low_bit(x);
    }
}

LL query(int x){
    LL res = 0;
    while(x){
        res += c[x];
        x -= low_bit(x);
    }
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = n; i >= 1; i--){
        ans += query(a[i]);//
        insert(a[i]+1);    //为了避免a[i]==0的尴尬情况，这里+1；同理，上面query(a[i]-1)改成了query(a[i]);
    }
    printf(outl, ans);
    return 0;
}

xuyifeng LV 10 MOD @ 2017-07-27 20:58:10

这是用归并排序做的codevs4163，不得不吐槽一下不能乱加memset啊，居然会超时...

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

#ifdef WIN32
#   define outl "%I64d"
#else
#   define outl "%lld"
#endif

using namespace std;

typedef long long LL;
const int MAXN = 1000005; 
int n, a[MAXN];
LL ans;
int t[MAXN], dex = 0;

void mergesort(int l, int mid, int r){
    int i = l, j = mid+1;
    dex = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j])    t[dex++] = a[i++];
        else    t[dex++] = a[j++], ans += mid - i + 1;
    }
    while(i <= mid) t[dex++] = a[i++];
    while(j <= r)   t[dex++] = a[j++];
    for(int i = 0; i < dex; i++)
        a[l+i] = t[i];
}

void merge(int l, int r){
    if(l >= r)  return;
    int mid = (l+r)>>1;
    merge(l, mid);
    merge(mid+1, r);
    mergesort(l, mid, r);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    merge(1, n);
    printf(outl, ans);
    return 0;
}

xuyifeng LV 10 MOD @ 2017-07-27 21:03:39

不得不说codevs评测的怎么那么慢，还以为超时了...

xuyifeng LV 10 MOD @ 2017-07-27 10:51:04

那啥，用线段树建树的时候我爆掉了（那道题a[i] <= 1000000)
而且，树状数组多简单呢~
- kk118294191 LV 8 @ 2017-07-27 17:51:28
  
  可以离散化这样就不会爆了
- xuyifeng LV 10 MOD @ 2017-07-27 20:35:23
  
  @kk118294191: 但这道题n也是1000000，极限情况下离散化没有用呢