CF624div3-F. Moving Points

题目

图片说明
意思很简单，就是在一个x轴上，有N个有速度的点，他们可以向左向右的速度，问在之后的移动过程中，两两点点距离差之和最小是多少。

分析

因为这是一个匀速运动，我们不妨把两个匀速运动方程做差，做差之后的运动方程就是就是两个点运动过程中的距离之差方程。




我们可以发现，只有和 同号两个点才不会相撞，因为他们的距离差是越来越大，所以我们可以通过排序固定为.所以只存在下面这种情况，当t = 0时，他们的距离差最小。

现在就遍历,每遍历一个就看在它之前有多少个(设为t)速度是小于等于它的，以及速度小于等于它的所有点离x = 0的距离和是多少(设为y)，然后当前的最小距离和就是：x*t-y。现在就可以想到要用线段树来做来，先把点按坐标进行排序，然后一个一个插入到线段树中，并返回t和y(用pair存)

AC 代码

#include <iostream>
#include <algorithm>
#define X first
#define Y second
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
typedef pair<ll,ll> pii;
int N;
pii arr[maxn];
struct node{
    int l,r;
    pii pre;
}tr[4*maxn];
ll V[maxn],tail; //用于离散化
void pushup(int u){
    tr[u].pre.first  = tr[u*2].pre.first+tr[u*2+1].pre.first; //前缀和
    tr[u].pre.second  = tr[u*2].pre.second+tr[u*2+1].pre.second; //个数
}
void build(int u,int l,int r){
    tr[u] = {l,r};
    if(l == r) return ;
    int mid = l+r>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}
void modify(int u,int idx,int x){
    if(tr[u].l == tr[u].r && tr[u].r == idx){
        tr[u].pre.first += x;
        tr[u].pre.second += 1;
    }else{
        int mid = (tr[u].l+tr[u].r)>>1;
        if(idx<=mid) modify(u*2,idx,x);
        else modify(u*2+1,idx,x);
        pushup(u);
    }
}
pii query(int u,int l,int r){
    if(tr[u].l >=l && tr[u].r<=r){
        return tr[u].pre;
    }else{
        int mid = tr[u].l+tr[u].r>>1;
        pii p1,p2,p3;
        if(l<=mid) p2 = query(u*2,l,r);
        if(r>mid) p3 = query(u*2+1,l,r);
        p1.first = p2.first+p3.first;
        p1.second = p2.second+p3.second;
        return p1;
    }
}

int ind(ll  x){
    return lower_bound(V,V+tail,x)-V+1;//加1是因为我线段树下标从1开始的
}
int main(){
    cin>>N;
    build(1,1,N);
    for(int i = 0;i<N;i++) scanf("%lld",&arr[i].X);
    for(int i = 0;i<N;i++) {
        scanf("%lld",&arr[i].Y);
        V[tail++] = arr[i].Y;
    }
    sort(arr,arr+N);
    sort(V,V+tail);
    tail = unique(V,V+tail)-V;//排序后去重
    ll res = 0;
    for(int i = 0;i<N;i++){
        pii p = query(1,1,ind(arr[i].Y)); 
        res += arr[i].X*p.second - p.first;
        modify(1,ind(arr[i].Y),arr[i].X);
    }
    cout<<res<<endl;
    return 0;
}