Ultra-QuickSort

题目链接：https://vjudge.net/problem/POJ-2299

思路

其实我们在学冒泡排序的时候，就可以发现有些相邻交换是不必要的。好的交换应该是使得数值更加的靠近他的真正位置。
好的排序过程如图所示：

这样每次新添加一个数，就看他之前有多少个比他大的数，就是交换次数(这个用树状数组就可以log级别完成统计)

代码

因为这题输入量挺大的，所以我使用了快读

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int tr[maxn];
struct node
{
    int v,id;    
    bool operator < (const node & o) const{
        return v < o.v;
    }
}arr[maxn];

inline void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}

bool cmp(const node & a,const node & b){
    return a.id < b.id;
}

void Lisa(){
    sort(arr+1,arr+N+1);
    for(int i = 1;i<=N;i++) arr[i].v = i;
    sort(arr+1,arr+N+1,cmp);
}
int lowbit(int x){
    return x&-x;
}
void add(int idx,int v){
    for(int i = idx;i<=N;i += lowbit(i)) tr[i] += v;
}
ll query(int r){
    ll sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int main(){
    // debug;
    while(scanf("%d",&N)){
        if(N == 0) break;
        memset(tr,0,4 * N+10);
        for(int i = 1;i<=N;i++){
            int cur;read(cur);
            arr[i] = {cur,i};
        }
        Lisa();
        ll res = 0;
        for(int i = 1;i<=N;i++){
            res += query(N) - query(arr[i].v);
            add(arr[i].v,1);
        }
        printf("%lld\n",res);
    }
    return 0;
}