Codeforces Round #624 (Div. 3) F. Moving Points（樹狀數組+離散化）

題目大意

       數軸上有 n n n個點( 2 ≤ n ≤ 2 ⋅ 1 0 5 2\le n\le2·10^5 2≤n≤2⋅105)，給出每個點的坐标 x i ( 1 ≤ x i ≤ 1 0 8 x_i (1\le x_i\le10^8 xi​(1≤xi​≤108）以及速度 v i ( − 1 0 8 ≤ v i ≤ 1 0 8 ) v_i(-10^8\le v_i\le 10^8) vi​(−108≤vi​≤108)，問在無窮時間範圍内，任意兩點間的最小距離之和是多少？（即求 ∑ 1 ≤ i < j ≤ n d ( i , j ) \sum\limits_{1\le i<j\le n}d(i,j) 1≤i<j≤n∑​d(i,j) 的值）

分析過程

       首先我們分析對于數軸上的兩個點 x i 和 x j x_i和x_j xi​和xj​（假設 x i < x j x_i<x_j xi​<xj​）來說：如果 v i > v j v_i>v_j vi​>vj​，那麼兩個點一定會在某一個時刻相遇；反之，兩點的初始位置之差便是兩點的最小距離。是以，對于任意一個點 x i x_i xi​，我們隻需要統計在它左側的速度比它小的點與它距離的絕對值之和即可。假設 x i x_i xi​左側的速度比其小的位置為 x 0 , x 1 , x 2 , . . . , x j x_0,x_1,x_2,...,x_j x0​,x1​,x2​,...,xj​，則我們所求即為： ( x i − x 0 ) + ( x i − x 1 ) + ( x i − x 2 ) + . . . + ( x i − x j ) = m ⋅ x i + ∑ p = 0 j x p (x_i-x_0)+(x_i-x_1)+(x_i-x _2)+...+(x_i-x_j)=m·x_i+\sum_{p=0}^jx_p (xi​−x0​)+(xi​−x1​)+(xi​−x2​)+...+(xi​−xj​)=m⋅xi​+p=0∑j​xp​（其中， m m m為比 x i x_i xi​速度小的位置點數）

       是以我們其實隻需要知道 x i x_i xi​左側比它小的位置點的個數以及他們的和就可以了，這是一個典型的具備字首特征的情境。不難想到，我們可以用樹狀數組來解決這個問題。我們使用兩個樹狀數組,其中一個用于存儲 v i v_i vi​的字首和（以樹狀數組下标作為值域，用于 v i v_i vi​很大這裡需要離散化一下），另一個存儲對應點的位置，以便求出字首和。

       綜上所述，本題做法如下：先對位置進行升序排序，然後離散化它們的 v i v_i vi​，從左到右周遊 x x x數組，每一次根據其速度對應的樹狀數組的字首計算出結果并累加到 a n s ans ans中，然後将該點也加入到樹狀數組中。時間複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)

AC代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 200;
//bt[0]數組用于标記第i個位置之前比其速度小的坐标個數
//bt[1]用于表示累計的坐标字首和 
ll n,arr[maxn],bt[2][maxn];
struct Point{
	ll x,v;
	bool operator()(Point a, Point b){
		return a.x < b.x;
	}
}p[maxn];
int low_bit(int x){
	return x & -x;
}
void add(int pos,int i,ll value){
	while(pos <= n){
		bt[i][pos] += value;
		pos += low_bit(pos);
	}
}
ll Query(int pos,int i){
	ll sum = 0;
	while(pos > 0){
		sum += bt[i][pos];
		pos -= low_bit(pos);
	} 
	return sum;
}
void preDeal(){
	int i;
	sort(arr+1,arr+1+n);
	int size = unique(arr+1,arr+1+n) - arr - 1;
	for(i=1;i<=n;++i){
		p[i].v = lower_bound(arr+1,arr+1+size,p[i].v) - arr;
	}
}
int main(){
	int i,j;
	ll ans = 0;
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;++i) cin>>p[i].x;
	for(i=1;i<=n;++i){
		cin>>p[i].v;
		arr[i] = p[i].v;
	}
	preDeal();
	sort(p+1,p+1+n,Point());
	for(i=1;i<=n;++i){
		ans += p[i].x * Query(p[i].v,0) - Query(p[i].v,1);
		add(p[i].v,0,1);
		add(p[i].v,1,p[i].x);
	}
	cout<<ans;
	return 0;
}