Codeforce 1311F - Moving Points【树状数组或pbds】

题意：

  给出 $x$x 坐标轴上的 $n$n 个点，各点坐标为： $x_i$xi​（保证所有的 $x_i$xi​ 不相等），同时每个点有一个速度 $v_i$vi​，因此 $t$t 时刻，点 $x_i$xi​ 的位置可以表示为 $x_i+t\ast v_i$xi​+t∗vi​。 $d(i,j)$d(i,j) 表示点 $i$i 和点 $j$j 在运动过程中的相距距离的最小值。
求 ∑1≤i<j≤n​d(i,j)。

数据范围： $2\le n\le 2\cdot 10^5$2≤n≤2⋅105， $1\le x_i\le 10^8$1≤xi​≤108， $-10^8\le v_i\le 10^8$−108≤vi​≤108

树状数组解法：

  首先，先把各点按 $x$x 坐标升序排序。对于点 $i$i， 设前面一点为 $j$j 。那么，只有当 $v_j\le v_i$vj​≤vi​ 时，点 $j$j 时无法追上点 $i$i 的，即 $d(i,j)=x_i-x_j$d(i,j)=xi​−xj​。其余情况下， $d(i,j)=0$d(i,j)=0。因此，只需要考虑 xj​<xi​,vj​≤vi​ 的情况即可。对于点 $i$i ，假设其前面有 $cnt$cnt 个点满足上述关系，坐标之和为 $sum$sum。那么，此时的答案为 $cnt\ast x_i-sum$cnt∗xi​−sum 。遍历所有点，即可求出最终的答案。
  以速度为树状数组的下标（先离散化），第一个树状数组表示速度为该值的点的数量，第二个树状数组表示速度为该值的点的坐标和,即可求出 $cnt$cnt 和 $sum$sum。
复杂度： $O\left(nlogn\right)$O(nlogn)
代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
typedef pair<int,int> P;
P point[N];
int bit1[N],v[N],x[N],len;
ll bit2[N];
void update1(int p)
{
    while(p<=len)
    {
        bit1[p]++;
        p+=(p&-p);
    }
}
void update2(int p,int val)
{
    while(p<=len)
    {
        bit2[p]+=val;
        p+=(p&-p);
    }
}
int query1(int p)
{
    int res=0;
    while(p>0)
    {
        res+=bit1[p];
        p-=(p&-p);
    }
    return res;
}
ll query2(int p)
{
    ll res=0;
    while(p>0)
    {
        res+=bit2[p];
        p-=(p&-p);
    }
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&point[i].first);

    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&point[i].second);
        v[i]=point[i].second;
    }
    sort(point+1,point+1+n);
    sort(v+1,v+1+n);
    len=unique(v+1,v+1+n)-v-1;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(v+1,v+1+len,point[i].second)-v;
        int cnt=query1(p);
        update1(p);
        ll sum=query2(p);
        update2(p,point[i].first);
        ans+=(1LL*cnt*point[i].first-sum);
    }
    printf("%lld\n",ans);
    return 0;
}

pbds:

  pbds（平板电视），全称： $\text{Policy based data structures}$Policy based data structures
题解
题解代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef
tree<
	pair<int, int>,
	null_type,
	less<pair<int, int>>,
	rb_tree_tag,
	tree_order_statistics_node_update>
ordered_set;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<pair<int, int>> p(n);
	for (auto &pnt : p) cin >> pnt.first;
	for (auto &pnt : p) cin >> pnt.second;
	sort(p.begin(), p.end());
	
	ordered_set s;
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int cnt = s.order_of_key(make_pair(p[i].second + 1, -1));
		ans += cnt * 1ll * p[i].first;
		s.insert(make_pair(p[i].second, i));
	}
	s.clear();
	for (int i = n - 1; i >= 0; --i) {
		int cnt = int(s.size()) - s.order_of_key(make_pair(p[i].second - 1, n));
		ans -= cnt * 1ll * p[i].first;
		s.insert(make_pair(p[i].second, i));
	}
	
	cout << ans << endl;
	
	return 0;
}