[CF1311F] Moving Points

Solution

按 $x$ 关键字升序排序，依次枚举每个点

考虑对任意 $x_j < x_i$，那么当 $v_j \leq v_i$ 时，它们不会相交，且 $dis$ 就是它们初态的距离 $x_i-x_j$

开两个树状数组，以离散化后的 $v$ 为下标，一个维护个数和，一个维护坐标和

那么每次询问的答案就是个数和 $\cdot x_i - $ 坐标和

然后把这个点插进去即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200005;

struct point {

    int v,x;

    bool operator < (const point &b) {

        return x<b.x;

    }

} p[N];

int n,ans;

struct ar {

    int b[N];

    int lowbit(int x) {return x&(-x);}

    void modify(int x,int v) {

        for(;x<=n;x+=lowbit(x)) (b[x]+=v);

    }

    int query(int x) {

        int ans=0;

        for(;x;x-=lowbit(x)) (ans+=b[x]);

        return ans;

    }

} a,b;

map<int,int> mp;

signed main() {

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=1;i<=n;i++) cin>>p[i].x;

    for(int i=1;i<=n;i++) cin>>p[i].v, mp[p[i].v]++;

    int ind=0;

    for(auto i=mp.begin();i!=mp.end();i++) i->second=++ind;

    for(int i=1;i<=n;i++) p[i].v = mp[p[i].v];

    sort(p+1,p+n+1);

    for(int i=1;i<=n;i++) {

        ans += a.query(p[i].v) * p[i].x - b.query(p[i].v);

        a.modify(p[i].v, 1);

        b.modify(p[i].v, p[i].x);

    }

    cout<<ans<<endl;

}

巴特西

[CF1311F] Moving Points - 树状数组

Solution

最新文章

热门文章