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

今天我們來看看CF61E

題目連結

題目

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

前言

學到BIT的新用法

@copyright petjelinux 版權所有

觀看更多正版原始文章請至petjelinux的blog

想法

首先可能會想到要枚舉\(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

巴特西

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

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

前言

想法

程式碼:

最新文章

热门文章