Codeforces Round #624 (Div. 3) F 离散化+树状数组

Codeforces Round #624 (Div. 3) F

文章目录

• Codeforces Round #624 (Div. 3) F
• • 题目
  • 题目大意
  • 解题思路
  • 代码

题目

题目大意

给出 n 个点和他们的初始位置 x 和移动速度 v，问所有点对在任意时刻全部最小值的和是多少，不是同一时刻而是每个点对的最小值的和，可以是任意时刻。

解题思路

思考一下易得，其实就是若i，j两个点，存在 x i < x j 且 v i ≤ v j x_i\lt x_j 且 v_i \le v_j xi​<xj​且vi​≤vj​，则两个这两个点对答案的贡献就是abs( x i − x j x_i - x_j xi​−xj​），因为只需要速度的相对大小关系，所以我们可以进行离散化方便处理，离散化代码如下

sort(lsh, lsh+n);
    for(int i = 0; i < n; i++)
    {
        a[i].second = lower_bound(lsh, lsh+n, a[i].second) - lsh + 1;
    }
           

这样，a[i].second就记录了速度的大小关系，然后对整个数组按照坐标从小到大排序，那么这个时候依次依速度为小标插入树状数组并统计，注意：这个时候坐标已经按照小到大的顺序，那么我们每次依速度为小标插入一个数据的时候，就记录比现在这个点小的速度在树状数组有多少个就行了，这样就能保证这些点对满足 x i < x j 且 v i ≤ v j x_i\lt x_j 且 v_i \le v_j xi​<xj​且vi​≤vj​

为了方便计算，我们要两个树状数组，一个是统计比这个点小的点的个数，一个统计比这个点小的点数之和。

代码

a.first 记录坐标

a.second 记录速度/大小关系

lsh 离散化需要的暂时数组

f1 记录比这个点小的点的个数

f2 比这个点小的点数之和

#include <iostream>
#include <cstdio>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;
#define dbg(x) cerr << #x " = " << x <<endl;
typedef pair<int, int> P;
typedef long long ll;
inline int lowbit(int x)
{
    return x & -x;
}
const int MAXN = 2e5+5;
ll f1[MAXN << 2], f2[MAXN << 2];
P a[MAXN];
int lsh[MAXN];
int n;
ll sum(int x, ll *arr)
{
    ll ret = 0;
    while(x > 0)
    {
        ret += arr[x];
        x -= lowbit(x);
    }
    return ret;
}
void add(int x, ll d, ll *arr)
{
    while(x <= n)
    {
        arr[x] += d;
        x += lowbit(x);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].first;
    }
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].second;
        lsh[i] = a[i].second;
    }
    sort(lsh, lsh+n);
    for(int i = 0; i < n; i++)
    {
        a[i].second = lower_bound(lsh, lsh+n, a[i].second) - lsh + 1;
    }
    sort(a, a+n);
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        ll tmp1 = sum(a[i].second, f1);
        ll tmp2 = sum(a[i].second, f2);
        ans += tmp1 * a[i].first - tmp2;
        add(a[i].second, 1, f1);
        add(a[i].second, a[i].first, f2);
    }
    cout << ans << endl;
    return 0;
}