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

題目連結

題目大意

在 O X OX OX坐标軸上有 n n n個點，每個點都有一個速度（可以為負數），每時每刻所有點都以自己的速度不斷運動，定義 d ( i , j ) d(i,j) d(i,j)為第 i i i和第 j j j個點在坐标軸上的的最短距離（可以是任意時刻）如果可以相遇則 d ( i , j ) = 0 d(i,j)=0 d(i,j)=0，求任意兩個節點的 d d d之和。顯然兩個節點要麼相遇要麼不相遇，相遇的話 d d d為 0 0 0，不相遇的話 d d d為初始兩點的距離（因為随着時間流逝不相遇的話距離會越來越大）

解題思路

首先需要明白的是如果目前 x i < x j x_i<x_j xi​<xj​且 v i ≤ v j v_i \leq v_j vi​≤vj​，那麼兩點不會相遇，隻需要加上兩者內插補點的絕對值，否則就不統計二者的距離。如果使用樹狀數組的話，我們需要知道要統計的是每個節點前面有多少個速度小于等于它的節點。如第二組樣例輸入1 2 4後，三者速度相同，那麼其貢獻是 2 ∗ 4 − ( 1 + 2 ) 2*4-(1+2) 2∗4−(1+2)，也就是該節點前面有 n u m num num個小于等于它的節點，就拿 n u m ∗ x − s u m ( x − 1 ) num*x-sum(x-1) num∗x−sum(x−1)，後者是節點之前的字首和。而且要保證後面節點坐标大于目前節點坐标，而且速度也要滿足後者大于等于前者。故我們要對速度和坐标分别從小到大進行排序。

對上面分析完之後，接下來就是如何去建立樹。對去重後的速度數組建立樹狀數組，而且要用另外一個二進制組儲存坐标和速度的對應關系并對坐标從小到大排序，這樣保證了兩個序列都是從小到大的排列。每次先取目前坐标的速度，使用 l o w e r b o u n d lower_bound lowerb​ound查找在去重的速度排第幾位（注意從 1 1 1開始），我們再通過建立的兩個樹狀數組 s u m sum sum和 c n t cnt cnt（分别記錄字首和以及每個速度對應的前面速度有幾個點），求出對 a n s ans ans的貢獻後再更新這個速度（這裡是相對的第幾大）以後的樹狀數組，這樣就可以計算出結果

我參考了這個部落格，感謝部落客。每次我都會去列一下是否建立的樹狀數組符合題目，然後在紙上構造出這個圖：如圖的 a a a對應去重後的速度數組 v v v，而 t t t就是 s u m sum sum和 c n t cnt cnt數組。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
#define lowbit(x) (x&(-x))
const int maxn=2e5+10;
pair<ll,ll> a[maxn];

ll sum[maxn],cnt[maxn];
int v[maxn],n;

void update(int i,int k){
    while(i<=n){
        cnt[i]++;  //目前以及之後對應節點數增加一
        sum[i]+=k;  //目前以及之後字首和增加k
        i+=lowbit(i);
    }
}

ll getSum(int i){
    ll ans=0;
    for(;i;i-=lowbit(i))
        ans+=sum[i];
    return ans;
}

ll getCnt(int i){
    ll ans=0;
    for(;i;i-=lowbit(i))
        ans+=cnt[i];
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].first);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&v[i]);
        a[i].second=v[i];
    }
    sort(a+1,a+1+n);
    sort(v+1,v+1+n);
    int tot=unique(v+1,v+n+1)-v-1;  //得到一共多少個去重後的速度
    ll ans=0;
    for(int i=1;i<=n;i++){
        int num=lower_bound(v+1,v+1+tot,a[i].second)-v; //減去v得到的才是目前速度是第幾大
        ans+=1LL*getCnt(num)*a[i].first-getSum(num);
        update(num,a[i].first);
    }
    printf("%lld",ans);
}
           

做法二

這是我去逛CF官網送出記錄的時候發現的，而且很多大佬也都這樣寫%%%，我想了一會沒想出來為什麼這樣寫，但是大佬的代碼總是簡單精煉效率高。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,x[N];
pair<int,int>a[N];
ll ans;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i];
        a[i].second=x[i];
    }
    for(int i=1;i<=n;i++)
        cin>>a[i].first;
    sort(a+1,a+n+1);
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++){
        //cout<<"("<<x[i]<<","<<a[i].first<<"-"<<a[i].second<<")"<<"-----"<<lower_bound(x+1,x+n+1,a[i].second)-x-n-1<<" "<<i+lower_bound(x+1,x+n+1,a[i].second)-x-n-1<<endl;
        ans+=(i+lower_bound(x+1,x+n+1,a[i].second)-x-n-1)*1LL*a[i].second;
    }
    cout<<ans;
}