• 欢迎光临~

# FOJ Moving Points 题解

3
1 3 2
-100 2 3

3

### 代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e5 + 1;
struct node {
int x, v;
bool operator <(node other) const {
return x < other.x;
}
} a[N];
struct Pair {
int tot;
long long sum;
Pair operator +(Pair other) const {
return (Pair){tot + other.tot, sum + other.sum};
}
};
struct tree {
int l, r;
Pair dat;
} t[4 * N];
int n;
int mpv[N], m;
return lower_bound(mpv + 1, mpv + m + 1, x) - mpv;
}
void Build(int p, int l, int r) {
t[p].l = l; t[p].r = r;
if (l == r) {
t[p].dat = (Pair){0, 0}; return ;
}
int mid = (l + r) >> 1;
Build(p * 2, l, mid); Build(p * 2 + 1, mid + 1, r);
}
void change(int p, int x, int v1, int v2) {
if (t[p].l == t[p].r) {
t[p].dat = t[p].dat + (Pair){v1, v2}; return ;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) change(p * 2, x, v1, v2);
else change(p * 2 + 1, x, v1, v2);
t[p].dat = t[p * 2].dat + t[p * 2 + 1].dat;
}
Pair query(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) return t[p].dat;
int mid = (t[p].l + t[p].r) >> 1;
Pair ans = (Pair){0, 0};
if (l <= mid) ans = ans + query(p * 2, l, r);
if (r > mid) ans = ans + query(p * 2 + 1, l, r);
return ans;
}
int main() {
long long ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i].x);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i].v); mpv[i] = a[i].v;
}
sort(a + 1, a + n + 1);
sort(mpv + 1, mpv + n + 1);
m = unique(mpv + 1, mpv + n + 1) - (mpv + 1);
Build(1, 1, m);
for (int i = 1; i <= n; i++) {
Pair res = query(1, 1, ask(a[i].v));
ans += (long long)a[i].x * res.tot - res.sum;