首页 > 代码库 > Ultra-QuickSort

Ultra-QuickSort

2024-07-13 12:16:47   215人阅读

poj2299:http://poj.org/problem?id=2299

题意：就是求逆序对。

题解：直接用树状数组，但是这一题要你离散化，如果用之前的vector来离散化的话，会T的，自己用一个数组搞一下，然后二分查找，用lower_bound来搞一下，比vector要快。还有，答案要用long long，否则会WA。注意STL的使用，很是方便。

 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<map> 6 #include<vector> 7 using namespace std; 8 int n,a[500003],num; 9 int c[500003];10 int b[500003];11 long long ans;12 int lowbit(int x){13     return x&(-x);14 }15 void add(int x){16    while(x<=num){17      c[x]+=1;18      x+=lowbit(x);19    }20 }21 int getsum(int x){22    int sum=0;23    while(x>=1){24      sum+=c[x];25      x-=lowbit(x);26 27    }28    return sum;29 }30 int main(){31    while(~scanf("%d",&n)&&n){32        memset(c,0,sizeof(c));33        memset(a,0,sizeof(a));34        memset(b,0,sizeof(b));35        ans=0;36        for(int i=1;i<=n;i++){37         scanf("%d",&a[i]);38          b[i]=a[i];39        }40         sort(b+1,b+n+1);41        num=unique(b+1,b+1+n)-b-1;42        for(int i=n;i>=1;i--){43            int temp=lower_bound(b+1,b+1+num,a[i])-b;44           ans+=getsum(temp);45           add(temp);46        }47        printf("%I64d\n",ans);48    }49 }
View Code


联系
我们