|
|
// 权值线段树解法
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 5e5 + 10;
|
|
|
int a[N], b[N];
|
|
|
int n;
|
|
|
|
|
|
// 线段树区间和模板
|
|
|
#define ls u << 1
|
|
|
#define rs u << 1 | 1
|
|
|
|
|
|
struct Node {
|
|
|
int l, r; // 范围
|
|
|
int sum; // 区间内数字个数
|
|
|
} tr[N << 2]; // 4倍空间
|
|
|
|
|
|
// 创建
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r;
|
|
|
if (l == r) return;
|
|
|
int mid = l + r >> 1;
|
|
|
build(ls, l, mid), build(rs, mid + 1, r);
|
|
|
}
|
|
|
|
|
|
// 向上更新统计信息
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
|
}
|
|
|
|
|
|
// 修改点的值
|
|
|
void modify(int u, int x, int v) {
|
|
|
if (tr[u].l == x && tr[u].r == x) {
|
|
|
tr[u].sum += v;
|
|
|
return;
|
|
|
}
|
|
|
int mid = tr[u].l + tr[u].r >> 1;
|
|
|
if (x <= mid)
|
|
|
modify(ls, x, v);
|
|
|
else
|
|
|
modify(rs, x, v);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 查询区间和
|
|
|
int query(int u, int l, int r) {
|
|
|
if (l > r) return 0;
|
|
|
if (tr[u].l == l && tr[u].r == r) return tr[u].sum;
|
|
|
int mid = tr[u].l + tr[u].r >> 1;
|
|
|
if (mid < l) return query(rs, l, r);
|
|
|
if (r <= mid) return query(ls, l, r);
|
|
|
return query(ls, l, mid) + query(rs, mid + 1, r);
|
|
|
}
|
|
|
|
|
|
LL ans;
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
// 一般使用线段树，都喜欢从下标1开始，所以我们在处理数据时尽量让下标从1开始
|
|
|
// b[]在下面的代码中有两个阶段的含义，目前的含义是a[i]的备份，因为一会a[]由小到大排序后，原始数组就丢失了位置信息就不见了，需要b备份出来
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
|
|
|
|
|
|
// ① 原始数组由小到大排序
|
|
|
sort(a + 1, a + n + 1);
|
|
|
|
|
|
// ② 离散化，遍历原始数组b[i],找出它的排名，即b[2]=3表示第2个输入的是排名第3的
|
|
|
for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + n + 1, b[i]) - a;
|
|
|
|
|
|
// 构建线段树
|
|
|
build(1, 1, n); // n个数字
|
|
|
|
|
|
// 边查边添加
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
modify(1, b[i], 1); // 占据b[i]这个位置
|
|
|
ans += query(1, b[i] + 1, n); // 出现的比我早，号还比我大的有多少个
|
|
|
}
|
|
|
|
|
|
// 输出
|
|
|
printf("%lld\n", ans);
|
|
|
return 0;
|
|
|
} |
