CF1311F Moving Points

思路

给出一种不需要脑子的四颗树状数组解法。

这四颗树状数组分别为：一颗维护负数，一颗维护负数个数，一颗维护正数，一颗维护正数个数。

首先考虑没有速度该怎么求。

不妨先按 \(x_i\) 从小到大排序，答案为 \(\sum x_i \times (i-1)-sum_i\)，其中 \(sum_i\) 表示 \(\sum_{j=1}^i x_j\)。所以我们不妨先把 \(ans\) 赋值为这个值。

接下来考虑加入速度。

我们只需考虑两种情况：相遇和相离，由于时间无限，所以相遇的情况 \(d_{i,j}\) 一定是 \(0\)，而相离后的距离一定大于 \(0\) 时刻的距离，所以 \(d_{i,j}\) 实际只有两种情况：\(0\)，\(|x_i-x_j|\)。

我们已经把所有的 \(|x_i-x_j|\) 累加入答案，接下来只需要消去 \(0\) 的贡献即可。

设当前扫到的位置为 \(i\)：

若 \(v_i>0\)，则此时能与 \(i\) 距离为 \(0\) 的点 \(j\) 必定满足 \(v_j>v_i\)，这是简单的追及问题。
若 \(v_i<0\)，则此时能与 \(i\) 距离为 \(0\) 的点 \(j\) 必定满足 \(v_j>0\) 或 \(v_j<v_i\)，\(v_j>0\) 是相遇问题，\(v_j<v_i\) 是追及问题。

接下来就可以简单地二维数点了，或者也可以像我一样暴力开四颗树状数组维护。

代码

//A tree without skin will surely die.

//A man without face is invincible.

#include<bits/stdc++.h>

using namespace std;

#define int long long

int const N=2e5+10;

int n,b[N],sum[N],hsum[N];

struct node{int x,v;}a[N];

struct Tree_Array{

    int c[N];

    #define lowbit(x) (x&-x)

    inline void update(int x,int v){while (x<=n) c[x]+=v,x+=lowbit(x);}

    inline int query(int x){int res=0;while (x) res+=c[x],x-=lowbit(x);return res;}

}T[5];

inline bool cmp(node a,node b){return a.x<b.x;}

signed main(){

    //读入

    sort(b+1,b+n+1);int l=unique(b+1,b+n+1)-b-1;//离散化

    for (int i=1;i<=n;++i) a[i].v=lower_bound(b+1,b+l+1,a[i].v)-b;

    sort(a+1,a+n+1,cmp);int ans=0;

    for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i].x;

    for (int i=n;i>=1;--i) hsum[i]=hsum[i+1]+a[i].x;

    for (int i=1;i<=n;++i) ans+=a[i].x*(i-1)-sum[i-1];

    int sum0=0,sum=0;

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

        int j=i;while (a[j+1].x==a[i].x) ++j;

        for (int k=i;k<=j;++k){

            if (!b[a[k].v]){

                ans-=a[k].x*T[3].query(n)-T[0].query(n);

                continue;

            }

            if (b[a[k].v]>0) ans-=a[k].x*(T[3].query(n)-T[3].query(a[k].v))-(T[0].query(n)-T[0].query(a[k].v));

            else ans-=a[k].x*sum0-sum+a[k].x*(T[3].query(n)+(T[4].query(n)-T[4].query(a[k].v)))-(T[0].query(n)+(T[1].query(n)-T[1].query(a[k].v)));

        }

        for (int k=i;k<=j;++k){

            if (!b[a[k].v]){

                ++sum0;

                sum+=a[k].x;

                continue;

            }

            if (b[a[k].v]>0) T[0].update(a[k].v,a[k].x),T[3].update(a[k].v,1);

            else T[1].update(a[k].v,a[k].x),T[4].update(a[k].v,1);

        }

        i=j+1;

    }

    //输出

    return 0;

}

巴特西

CF1311F Moving Points

思路

代码

最新文章

热门文章