首页 > 代码库 > poj 2299 Ultra-QuickSort
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\n",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(); } }
poj 2299 Ultra-QuickSort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。