Codeforce 61 E. Enemy is weak 解析(思維、離散化、BIT、線段樹)

今天我們來看看CF61E
題目連結

題目
給一個數列$a$，求有多少$(i,j,k)$，$i<j<k$，使得$a[i]>a[j]>a[k]$

前言

學到BIT的新用法

想法

首先可能會想到要枚舉$j$，而我們只要知道$a[j]$前有多少比較大的元素，$a[j]$後有多少比較少的元素就好。
單調棧只能得到一個元素的位置，似乎用不了。而既然我們只需要知道有多少元素而不需要知道精確位置，我們可能會想到要維護每個數字出現過的次數，而$\sum\limits_{k>a[j]}cnt[k]$就是$a[j]$左邊比較大的數字的數量了。
而維護前綴和自然會使用BIT或線段樹了。
當然由於$a[i]\le1e9$，我們需要把$a$複製到新數列中，並且排序，如此一來我們就可以把$a[i]$重新編號到範圍$[1,n]$裡，而需要得知這個新編號，可以直接$upper_bound$(詳見code)。

程式碼:

const int _n=1e6+10;  
int t,tt,n,a[_n],l[_n],r[_n];  
VI Li;  
ll ans;  
namespace BIT{  
  int nn;ll t[_n];  
  void update(int x){while(x<=nn)t[x]++,x+=(x&-x);}  
  ll query(int x){ll res=0;while(x>0){res+=t[x],x-=(x&-x);}return res;}  
  void init(int n_){nn=n_;}  
  void clear(){rep(i,0,nn+1)t[i]=0;}  
}  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n;rep(i,1,n+1){cin>>a[i];Li.pb(a[i]);} sort(all(Li));BIT::init(n);  
  per(i,1,n+1){  
    t=upper_bound(all(Li),a[i])-Li.begin();  
    r[i]=BIT::query(t-1),BIT::update(t);  
  }BIT::clear();  
  rep(i,1,n+1){  
    t=n-(upper_bound(all(Li),a[i])-Li.begin())+1;  
    l[i]=BIT::query(t-1),BIT::update(t);  
  }rep(i,1,n+1)ans+=1ll*l[i]*r[i];  
  cout<<ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission