首页 > 代码库 > Ultra-QuickSort (树状数组离散化)
Ultra-QuickSort (树状数组离散化)
题目原意是用归并排序,刚学树状数组,就用了下
树状数组的离散化
离散化,是数据范围太大是所借用的利器,举个例子,有四个数99999999 1 123 1583 数据范围太大,而树状数组中的c数组开的范围是数据的范围,这时候就需要离散化,把四个数一次标号为1 2 3 4(即第一个数,第二个数。。。),按键值排序之后 依次为2 3 4 1(即从小到大排序为第二个数,第三个数。。。),所以,第二个数是最小的,即f[2]=1,f[3]=2,f[4]=3,f[1]=4,也就是把键值变为了1~n,相对大小还是不变的,即4 1 2 3。
用f[]数组存放相对大小,要引用原数组第i个的元素,就是f[i]了
题目给的数据有maxn=500000,完全逆序的逆序数为等差数列的前n项和=(maxn-1)*maxn/2 , 差不多是10的13次方,所以要用longlong 存
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #define maxn 500010 typedef long long LL; using namespace std; struct node { int x,i; }a[maxn]; int n; int c[maxn],f[maxn]; bool cmp(node x,node y) { return x.x<y.x; } int lowbit(int x) { return x&-x; } void update(int x,int v) { while(x<=n){ c[x]+=v; x+=lowbit(x); } } int getsum(int x) { int sum=0; while(x>0){ sum+=c[x]; x-=lowbit(x); } return sum; } int main() { while(~scanf("%d",&n),n){ memset(c,0,sizeof(c)); memset(f,0,sizeof f); for(int i=1;i<=n;i++){ scanf("%d",&a[i].x); a[i].i=i;//在原数组的下标 } sort(a+1,a+n+1,cmp);//开始离散化 f[a[1].i]=1;//从最小的开始 for(int i=2;i<=n;i++){ if(a[i].x!=a[i-1].x){ f[a[i].i]=i; } else f[a[i].i]=f[a[i-1].i]; }//离散化结束 LL ans=0; for(int i=1;i<=n;i++){ update(f[i],1); ans+=i-getsum(f[i]);//第i个数的逆序数=i-前面有多少个比它小的=就是前面多少个比它大的 ,getsum(i)就是前面有多少个数比i小 } //也能写成 ans+=getsum(n)-getsum(i) cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。