poj 2299 Ultra-QuickSort

树状数组   

例子过了就A了  

YA各种爽

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxx 500050
int bit[maxx],a[maxx];
int n;
struct node {
int x,y;
}pos[maxx];
bool cmp(node aa,node bb)
{
    return aa.x<bb.x;
}
int sum(int i)
{
    int s=0;
    while(i>0){
        s+=bit[i];
        i=i&(i-1);
    }
    return s;
}
void add(int i,int xx)
{
    while(i<=n)
    {
        bit[i]+=xx;
        i+=i&-i;
    }
}
void slove()
{
   long long  int  ans=0;
    for(int j=0;j<n;j++){
        ans+=j-sum(a[j]);
        add(a[j],1);
    }
    printf("%lld
",ans);
}
int main() {
   while(scanf("%d",&n),n){
    memset(bit,0,sizeof(bit));
    for(int i=0;i<n;i++){
    scanf("%d",&pos[i].x);
    pos[i].y=i;
    }
    sort(pos,pos+n,cmp);
    for(int i=0;i<n;i++)
    a[pos[i].y]=i+1;
    slove();
   }
}