題目鏈接：點(diǎn)擊查看

題目大意：給出n個(gè)數(shù)字，求使用冒泡排序所需要交換的次數(shù)

題目分析：這個(gè)題n給到了5e5，如果直接冒泡排序的話，的時(shí)間復(fù)雜度肯定就TLE了，所以不能直接暴力模擬

我們換個(gè)思路，這個(gè)題其實(shí)需要轉(zhuǎn)化一下，就是求每個(gè)位置上數(shù)字的逆序數(shù)，然后加和就是所要求的答案了

因?yàn)橄鄬?duì)較大的數(shù)字經(jīng)過排序后要往右邊移動(dòng)，而任意位置的一個(gè)數(shù)字所要移動(dòng)的距離就是他的逆序數(shù)，即需要和每一個(gè)他右邊

比他小的數(shù)字所交換一次，所以現(xiàn)在問題轉(zhuǎn)化為了求這串?dāng)?shù)字的逆序數(shù)了

---

那么該怎么求逆序數(shù)呢？我們就要用到線段樹了，我先來大體描述一下該怎么用線段樹求逆序數(shù)吧：

我們先要知道求一個(gè)位置上的逆序數(shù)，有兩種途徑，一種是通過求該位置之前比它本身大的數(shù)字的個(gè)數(shù)，另一種就是通過求該位

置之后比它本身小的數(shù)字的個(gè)數(shù)

我們先假設(shè)一個(gè)數(shù)列為5,1,3,2,4，我們需要求這個(gè)數(shù)列每一項(xiàng)的逆序數(shù)，我們就用第一種方法來求吧，就是求每個(gè)位置之前比它

本身大的數(shù)字的個(gè)數(shù)，首先我們先假設(shè)下面五個(gè)方塊依次代表著沒一個(gè)數(shù)字，點(diǎn)亮后的方塊代表前面已經(jīng)遍歷過的數(shù)字

□? □? □? □? □

一開始還沒有進(jìn)行填充，我們現(xiàn)在開始遍歷一邊這個(gè)數(shù)列：

首先第一個(gè)數(shù)字是5，我們需要查找比5大的數(shù)字，即查找區(qū)間（5+1,5），很顯然這個(gè)區(qū)間是不存在的，因?yàn)樽蠖它c(diǎn)大于了右端

點(diǎn)，故第一個(gè)數(shù)的逆序數(shù)為0，在遍歷下一個(gè)數(shù)字之前，需要將第一個(gè)數(shù)字點(diǎn)亮，即變成這個(gè)樣子。

□? □? □? □? ■

然后我們?cè)偬幚淼诙€(gè)數(shù)字，我們需要找到比1大的數(shù)字，即查找區(qū)間（1+1,5）中有多少個(gè)點(diǎn)亮的方塊，很顯然答案是1，然后

更新點(diǎn)亮的狀態(tài)，將第一個(gè)燈也點(diǎn)亮

■? □? □? □? ■

接下來處理第三個(gè)數(shù)字，是3，那么我們需要查找區(qū)間（3+1,5），答案是1，更新狀態(tài)：

■? □? ■? □? ■

然后是處理數(shù)字2，我們需要查找區(qū)間（2+1,5），答案是2，更新狀態(tài)：

■? ■? ■? □? ■

最后只剩一個(gè)4了，我們需要查找區(qū)間（4+1,5），答案是1，更新狀態(tài)：

■? ■? ■? ■? ■

到此為止，我們將上述結(jié)果加和，得到的便是這一串?dāng)?shù)列的逆序數(shù)了，即0+1+1+2+1=5

然后稍微總結(jié)一下，關(guān)于上述的兩個(gè)操作：“查找區(qū)間”和“點(diǎn)亮狀態(tài)”的操作，分別對(duì)應(yīng)著線段樹中的區(qū)間查找和點(diǎn)更新，是不是有

點(diǎn)感覺了？

等等等等！這個(gè)題到這里還沒完呢，為什么呢？因?yàn)檫@個(gè)題的數(shù)據(jù)范圍，n是5e5，還不算太大，那么每一個(gè)位置上的數(shù)呢？范圍

竟然是999999999？我們都知道線段樹是根據(jù)范圍來開的，如果按照范圍的話，我們需要開至少4e10的數(shù)組才能實(shí)現(xiàn)上述的方

法，不過很顯然，會(huì)爆內(nèi)存，那我們?cè)撛趺刺幚砟?#xff1f;

這個(gè)題涉及到了二維偏序問題，在這個(gè)題目中，每個(gè)數(shù)字的位置代表一個(gè)維度，每個(gè)數(shù)字的數(shù)值代表著另一個(gè)維度，因?yàn)樗臄?shù)

值涉及到的范圍很廣，所以我們需要將其離散化來處理，即在存儲(chǔ)每一個(gè)數(shù)字的時(shí)候一起存上他原本的位置，然后對(duì)于他的數(shù)值

排序，然后對(duì)于他的位置來求逆序數(shù)，這樣就可以將求逆序數(shù)的范圍規(guī)范到了1~n之間了，剩下的就可以用線段樹來解決了。

---

?2019.11.29更新：

學(xué)習(xí)了歸并排序的原理和內(nèi)部實(shí)現(xiàn)后，發(fā)現(xiàn)這個(gè)題目用歸并排序能以穩(wěn)定的nlogn的時(shí)間復(fù)雜度解決，掛一下代碼

上代碼：更多的會(huì)在代碼里注釋

線段樹：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;struct Node {int l,r,sum; }tree[N<<2];struct node {int pos,val; }a[N];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r){ return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void add(int k,int pos) {if(tree[k].l==tree[k].r){tree[k].sum=1;return;}int mid=(tree[k].l+tree[k].r)>>1;if(mid>=pos)add(k<<1,pos);elseadd(k<<1|1,pos);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }int query(int k,int l,int r) {if(l>r)return 0;if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].r<=r&&tree[k].l>=l)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }bool cmp(node a,node b) {return a.val<b.val; }int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF&&n){build(1,1,n);for(int i=1;i<=n;i++){scanf("%d",&a[i].val);a[i].pos=i;}sort(a+1,a+1+n,cmp);//離散化LL ans=0;//注意這里記得開long long，因?yàn)橛?jì)算的過程中會(huì)爆int，因?yàn)檫@個(gè)WA了一發(fā)for(int i=1;i<=n;i++){ans+=query(1,a[i].pos+1,n);//我們求每個(gè)數(shù)字前比他大的數(shù)字的個(gè)數(shù)add(1,a[i].pos);//每次處理完記得“點(diǎn)亮”這個(gè)點(diǎn)}cout<<ans<<endl;}return 0; }

歸并排序：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;int a[N],b[N];LL merge_sort(int l,int r) {if(l==r)//只有一個(gè)元素直接返回return 0;int mid=l+r>>1;LL ans=merge_sort(l,mid)+merge_sort(mid+1,r);//分別往左側(cè)和右側(cè)遞歸int p=l,q=mid+1;for(int i=l;i<=r;i++)//合并，數(shù)組b是輔助數(shù)組，輔助排序用的{if(q>r||p<=mid&&a[p]<=a[q])b[i]=a[p++];else{b[i]=a[q++];ans+=mid-p+1;//這里，既然q點(diǎn)屬于當(dāng)前右區(qū)間內(nèi)最小的點(diǎn)了，那么左區(qū)間內(nèi)比他大的點(diǎn)有mid-p+1個(gè)}}for(int i=l;i<=r;i++)a[i]=b[i];return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF&&n){for(int i=1;i<=n;i++)scanf("%d",a+i);printf("%lld\n",merge_sort(1,n));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 2299 Ultra-QuickSort(线段树+离散化/归并排序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。