76 lines
2.3 KiB
C++
76 lines
2.3 KiB
C++
/*
|
||
树状数组解法 https://blog.csdn.net/m0_50299150/article/details/122729602
|
||
权值线段树解法
|
||
*/
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int N = 5e5 + 10;
|
||
int a[N], b[N];
|
||
int n;
|
||
// 344 ms
|
||
struct Node {
|
||
int l, r; //描述的范围[l,r]
|
||
int sum; // l,r之间数字的个数
|
||
} tr[N << 2]; // 线段树需要开4倍的空间
|
||
|
||
void build(int u, int l, int r) {
|
||
tr[u] = {l, r, 0};
|
||
if (l == r) return;
|
||
int mid = (l + r) >> 1;
|
||
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
|
||
}
|
||
void pushup(int u) {
|
||
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
|
||
}
|
||
void modify(int u, int p, int v) {
|
||
if (tr[u].l == p && tr[u].r == p) {
|
||
tr[u].sum += v;
|
||
return;
|
||
}
|
||
int mid = tr[u].l + tr[u].r >> 1;
|
||
if (p <= mid)
|
||
modify(u << 1, p, v);
|
||
else
|
||
modify(u << 1 | 1, p, v);
|
||
//更新父节点信息
|
||
pushup(u);
|
||
}
|
||
int query(int u, int l, int r) {
|
||
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(u << 1 | 1, l, r);
|
||
else {
|
||
if (r <= mid)
|
||
return query(u << 1, l, r);
|
||
else
|
||
return query(u << 1, l, mid) + query(u << 1 | 1, mid + 1, r);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//本题，如果使用vector+离散化，在AcWing可以正常AC，但在洛谷会有很多TLE，目前想来原因可能是因为vector的性能导致
|
||
//如果采用静态的数组进行离散化处理，就不会有这个问题
|
||
cin >> n;
|
||
|
||
//一般我们使用线段树，都喜欢从下标1开始，所以我们在处理数据时尽量让下标从1开始
|
||
for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
|
||
sort(a + 1, a + n + 1); //对原始数组进行排序
|
||
|
||
//这里没有进行离散化，只是对数据重新规范到范围[1,n]之间
|
||
for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + n + 1, b[i]) - a;
|
||
|
||
LL ans = 0;
|
||
|
||
//创建线段树
|
||
build(1, 1, n + 1);
|
||
//边查边添加,查找它后面比它大的数字个数
|
||
for (int i = 1; i <= n; i++) {
|
||
ans += query(1, b[i] + 1, n + 1);
|
||
modify(1, b[i], 1);
|
||
}
|
||
//输出答案
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |