逆序?qū)?br /> 逆序?qū)Φ亩x：對于給定的一段正整數(shù)序列，逆序?qū)褪切蛄兄?$a_i>a_j,i<j$，讓統(tǒng)計(jì)逆序?qū)Φ膫€(gè)數(shù)。

本題的數(shù)據(jù)加強(qiáng)，允許存在重復(fù)的數(shù)字。這并不影響下面分析的正確性。
思路
對于a[ i ] ,我們要求的是它前面大于a [ i ]的個(gè)數(shù)。
采用的思路是： i減去 小于等于a[i]的個(gè)數(shù)，剩下的就是大于a[i] 的個(gè)數(shù)

使用樹狀數(shù)組來求前綴和(query)，也就是來計(jì)算小于等于a[i]的個(gè)數(shù)，對于第i個(gè)數(shù)a[ i ]，其逆序?qū)Φ膫€(gè)數(shù)是i-query(a[i])

我是看了這篇博客會的https://blog.csdn.net/ssimple_y/article/details/53744096
這里需要注意的是位置的理解，即a數(shù)組中的數(shù)值a[i]，作為另一個(gè)數(shù)組中的下標(biāo)。 $t[a[i]]$
比如 數(shù)組a={5,2,3,4,1},假設(shè)數(shù)組下標(biāo)是1~5，a[1]==5，5就是在數(shù)組 t 中的下標(biāo)，5出現(xiàn)一次5的位置就加1，t數(shù)組初始化全0.

遍歷a數(shù)組
a[1]=5，數(shù)組t中$t[a[1]]=t[5]加1$;

這個(gè)時(shí)候對數(shù)組t求前綴和（從第一項(xiàng)加到t[5]），sum=1,意思是在前面包括自身，≤5的個(gè)數(shù)=1，此時(shí)i=1，表示總共一個(gè)數(shù)，則其中大于5的個(gè)數(shù)=0；

遍歷到a[2]=2,數(shù)組t中$t[a[2]]=t[2]加1$;

此時(shí)對數(shù)組t關(guān)于t[2] 求前綴和，發(fā)現(xiàn)等于1，意思是a數(shù)組2前面包括2本身有1個(gè)數(shù)字≤2。此時(shí)i=2，總共有2個(gè)數(shù)，其中比2大的個(gè)數(shù)：2-1=1。也就是逆序的個(gè)數(shù)。
逆序?qū)€(gè)數(shù) ans+=i-前綴和(a[i]).
此時(shí)逆序?qū)€(gè)數(shù)：ans=1;
遍歷到a[3]=3
發(fā)現(xiàn)t[3]前面的前綴和=2，意思是3前面包括本身≤3的個(gè)數(shù)是2，此時(shí)i=3，總共三個(gè)數(shù)，前面比3大的個(gè)數(shù)是：3-2=1；
此時(shí)逆序?qū)€(gè)數(shù) ans+=1 ,所以 ans=2;

遍歷到a[4]=4,

發(fā)現(xiàn)t[4]前面的前綴和=3，意思是4前面有3個(gè)數(shù)小于等于4。換句話說，有1個(gè)大于4，所以逆序?qū)€(gè)數(shù) 加1
逆序?qū)€(gè)數(shù)：ans+=1,所以 ans=3
遍歷到a[5]=1,

發(fā)現(xiàn)t[1]的前綴和為1，則1前面比1小的數(shù)的個(gè)數(shù)為1.此時(shí)i=5，5-1=4為逆序?qū)Φ膫€(gè)數(shù)

所以逆序?qū)Φ膫€(gè)數(shù) ans+=4;
最終ans=7;

ac代碼

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; const int maxn=5e5+10; ll n,a[maxn],b[maxn];//離散化用數(shù)組 ll t[maxn];//樹狀數(shù)組 //快讀 inline ll read(){ll k=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return f*k; }//計(jì)算前驅(qū)和后繼 ll lowbit(ll x){return x&-x; }// 樹狀數(shù)組更新 void update(ll i,ll k){while(i<=n){t[i]+=k;i+=lowbit(i);}}//前綴和 ll query(ll x){ll res=0;while(x>0){res+=t[x];x-=lowbit(x);}return res; } int main(){n=read();for(ll i=1;i<=n;i++){a[i]=read();b[i]=a[i];}sort(b+1,b+n+1);ll m=unique(b+1,b+1+n)-b;for(ll i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+n,a[i])-b;//用來離散化}ll ans=0;for(ll i=1;i<=n;i++){update(a[i],1);//樹狀數(shù)更新，出現(xiàn)的話，給位置+1ans+=i-query(a[i]);//維護(hù)的是比a[i]大的個(gè)數(shù),累加就是答案}printf("%lld",ans);}

補(bǔ)充一點(diǎn)：這題離散化如果從0開始計(jì)數(shù)的話，需要注意后面樹狀數(shù)組更新時(shí)需要下標(biāo)+1，求前綴和時(shí)數(shù)組下標(biāo)也需要+1；

for(int i=0;i<n;i++){cin>>q[i];a[i]=q[i];} sort(a,a+n);int m=unique(a,a+n)-a;//第一個(gè)大于的位置for(int i=0;i<n;i++){q[i]=lower_bound(a,a+n,q[i])-a;//這樣的話離散化從0開始 //cout<<q[i]<<endl;}ll ans=0;for(int i=0;i<n;i++){update(q[i]+1,1);ans+=i+1-sum(q[i]+1);}cout<<ans<<endl;

總結(jié)

以上是生活随笔為你收集整理的洛谷P1908求逆序对【树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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