【問題描述】

給你n個整數(shù)，每個數(shù)a[i]都是不超過109的非負(fù)整數(shù)。求其中逆序?qū)Φ膫€數(shù)，即所有這樣的數(shù)對(i,j)滿足1≤i<j≤n且a[i]>a[j]。

【輸入文件】inverse.in

第一行一個正整數(shù)n(1≤n≤500000)，代表數(shù)字的個數(shù)。

接下來一行n個用空格分隔的整數(shù)，代表要處理的數(shù)字序列。

【輸出文件】inverse.out

一行一個整數(shù)，代表逆序?qū)Φ膫€數(shù)。

【樣例輸入】

5

2 3 1 5 4

【樣例輸出】

3

【數(shù)據(jù)及時間與空間限制】

對于20%的數(shù)據(jù)，n≤20000，對于100%的數(shù)據(jù)，n≤500000。

時間限制：1秒，空間限制：256MB。

【算法分析】

1.離散化 由于輸入數(shù)據(jù)較為離散，我們對其采用保持大小關(guān)系但改變數(shù)值的辦法，如以9 1 0 5 4為例，離散化后變成5 2 1 4 3，去除冗余內(nèi)存空間和計算，有助于樹狀數(shù)組的高效運算。

2.樹狀數(shù)組 對于當(dāng)前操作數(shù)a[i]，計算getsum(m)-getsum(a[i]) {m為數(shù)列中數(shù)字個數(shù)} 并用add(a[i])將a[i]加入樹狀數(shù)組。

注：add過程實際為birtree中的change過程，由于本題的特殊性，每次調(diào)整數(shù)組只需+1，因此調(diào)整為add函數(shù)，只需一個參數(shù)。

【程序描述】

a數(shù)組 原始數(shù)列

b數(shù)組 快速排序后數(shù)列，用于離散化。

c數(shù)組 樹狀數(shù)組

lowbit函數(shù)、add函數(shù)、getsum函數(shù) 參考Birtree

【反思】

表示我讀代碼的水平越來越次了，然后快排居然忘記怎么寫了跳進(jìn)死循環(huán)了TAT，真心對不起老師啊。

【源程序】

Inverse program inverse; var a,b,c:array[0..500000] of longint;n,i:longint; procedure qsort(l,r:longint); var i,j,mid,temp:longint; begini:=l;j:=r;mid:=a[(l+r) div 2];while i<=j dobeginwhile a[i]<=mid do inc(i);while a[j]>=mid do dec(j);if i<=j thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp;temp:=b[i];b[i]:=b[j];b[j]:=temp;inc(i);dec(j);end;end;if i<r then qsort(i,r);if j>l then qsort(l,j); end; function lowbit(i:longint):longint; beginlowbit:=i-(i and (i-1)); end; procedure add(i:longint); beginwhile i<=n dobeginc[i]:=c[i]+1;i:=i+lowbit(i);end; end; function getsum(i:longint):longint; begingetsum:=0;while i>0 dobegingetsum:=getsum+c[i];i:=i-lowbit[i];end; end; begin {main}readln(n);for i:=1 to n dobeginread(a[i]);b[i]:=i;end;qsort(1,n);c:=a; c[0]:=-1;for i:=1 to n doif c[i]<>c[i-1] thenbegininc(m);a[b[i]]:=m;endelsea[b[i]]:=m;fillchar(c,sizeof(c),0);for i:=1 to n dobegininc(ans,getsum(m)-getsum(a[i]);add(a[i]);end;writeln(ans); end.

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Sky-Grey/archive/2013/03/03/2941521.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[树状数组] Inverse的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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