Codeforce 1311 F. Moving Points 解析(思維、離散化、BIT、前綴和)

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

題目
略，請直接看原題。

前言

最近寫1900的題目更容易不看題解了，不知道是不是較少人$AC$的同難度題目會比較簡單。

想法

首先注意到，如果$x$座標上的前後兩點$x_i,x_j$，$x_i<x_j$，如果$v[x_i]>v[x_j]$，不管$v$是正是負，兩點一定某個時候會重疊。反之，如果$v[x_i]\le v[x_j]$，那麼我們就需要把答案加上$x_j-x_i$。
而我們可能會想到用$BIT$來維護$:$到某個$x$座標為止，小於等於某個速度的點有多少個。但是$-10^8\le v_i\le10^8$實在太大了，因此我們需要離散化$v$，把範圍縮到至少$[1,n]$。
但是我們可能會發現，我們不只需要維護小於等於某個速度的點有多少個，還需要知道這些點和目前看的點$x_i$的距離的和。
因此我們可以這樣做:首先把所有$x_i$減去最小的$x$值(也就是把$x$陣列平移到非負座標)。這樣一來$BIT$維護目前有$r$個點的速度小於等於$v$，且這些點的$x$座標和為$p$，那麼當我們考慮$x_j$這個點的時候(要去找有多少在$x_j$之前的點的速度比$x_j$的速度小)，只需要把答案加上$r\times x_j-p$即可。

注意，本題$x$座標沒有排序，要自己先排序過。
且這題我的程式碼中的$PII$是$pair<long\ long,long\ long>$

程式碼:

const int _n=2e5+10;  
int t,n,minn=1e9;  
VI vv;  
PII s[_n];  
namespace BIT{  
  int nn;PII t[_n];  
  void update(int x,int val){while(x<=nn)t[x].fi+=val,t[x].se++,x+=(x&-x);}  
  //這模板是1-base，而且update是把修改量加上去  
  PII query(int x){PII res={0,0};while(x>0){res.fi+=t[x].fi,res.se+=t[x].se,x-=(x&-x);}return res;}  
  void init(int n_){nn=n_;}  
}  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n;rep(i,1,n+1){cin>>s[i].fi;minn=min(minn,s[i].fi);}rep(i,1,n+1){cin>>s[i].se;vv.pb(s[i].se);}  
  sort(s+1,s+n+1);sort(all(vv));int nn=unique(all(vv))-vv.begin();  
  rep(i,1,n+1)s[i].se=lower_bound(vv.begin(),vv.begin()+nn,s[i].se)-vv.begin()+1;  
  rep(i,1,n+1)s[i].fi-=minn;  
  BIT::init(nn); ll ans=0;  
  rep(i,1,n+1){  
    PII res=BIT::query(s[i].se);  
    ans+=1ll*s[i].fi*res.se-res.fi;  
    BIT::update(s[i].se,s[i].fi);  
  }cout<<ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission