題目：http://poj.org/problem?id=2299

?

離散化是一種常用的技巧，有時數據范圍太大，可以用來放縮到我們能處理的范圍?因為其中需排序的數的范圍0---

999999999；顯然數組不肯能這么大；而N的最大范圍是500000；故給出的數一定可以與1.。。。N建立一個一一映射；

?

這里用一個結構體

struct Node

?{

????? int v,order;

?}a[510000];

和一個數組aa[510000];

?

其中v就是原輸入的值，order是下標；然后對結構體按v從小到大排序；此時，v和結構體的下標就是一個一一對應關系，而且

滿足原來的大小關系；

for(i=1;i<=N;i++)

?????aa[a[i].order]=i;

?

然后a數組就存儲了原來所有的大小信息；比如 9 1 0 5 4 ------- 離散后aa數組就是 5 2 1 4 3；具體的過程可以自己

用筆寫寫就好了。

?

離散之后，怎么使用離散后的結果數組來進行樹狀數組操作，計算出逆序數？?

如果數據不是很大，可以一個個插入到樹狀數組中，每插入一個數，統計比他小的數的個數，對應的逆序為 i- getsum(aa

[i]),其中i為當前已經插入的數的個數，getsum(aa[i])為比aa[i]小的數的個數,i- sum(aa[i]) 即比aa[i]大的個數，

即逆序的個數但如果數據比較大，就必須采用離散化方法。

?

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 500005;struct Node {int v,order; };int n; int c[N]; int aa[N]; //離散化后的數組 Node a[N]; //樹狀數組int Lowbit(int x) {return x & (-x); }void Update(int t,int val) {for(int i=t; i<=n; i+=Lowbit(i))c[i] += val; }int getSum(int x) {int ans=0;for(int i=x; i>0; i-=Lowbit(i))ans += c[i];return ans; }bool cmp(Node a,Node b) {return a.v<b.v; }int main() {while(~scanf("%d",&n),n){//離散化for(int i=1; i<=n; i++){scanf("%d",&a[i].v);a[i].order=i;}sort(a+1,a+1+n,cmp);for(int i=1; i<=n; i++)aa[a[i].order]=i;//樹狀數組求逆序數memset(c,0,sizeof(c));long long ans=0;for(int i=1; i<=n; i++){Update(aa[i],1);ans+=i-getSum(aa[i]);}printf("%I64d\n",ans);}return 0; }

?

?

題目：HDU2492 Ping pong

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define N 200010typedef struct {int v;int order; }Node;int n; int c[N]; int aa[N]; Node a[N]; int lmin[N]; int rmin[N]; int lmax[N]; int rmax[N];int LowBit(int x) {return x&(-x); }int Update(int t,int v) {for(int i=t;i<=n;i+=LowBit(i)){c[i]+=v;} }int GetSum(int x) {int i,temp=0;for(i=x;i>=1;i-=LowBit(i)){temp+=c[i];}return temp; }bool cmp(Node a,Node b) {return a.v<b.v; }int main() {int t,i,j;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].order=i;}sort(a+1,a+n+1,cmp);for(i=1;i<=n;i++)aa[a[i].order]=i;memset(c,0,sizeof(c));for(i=1;i<=n;i++){lmin[i]=GetSum(aa[i]);lmax[i]=i-lmin[i]-1;Update(aa[i],1);}memset(c,0,sizeof(c));for(i=n,j=1;i>=1;i--,j++){rmin[i]=GetSum(aa[i]);rmax[i]=j-rmin[i]-1;Update(aa[i],1);}long long ans=0;for(i=1;i<=n;i++)ans+=lmin[i]*rmax[i]+rmin[i]*lmax[i];printf("%I64d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的离散化+树状数组求逆序数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。