AcWing 788. 保序离散化+树状数组
原题链接
简单
作者:
九日ovo
,
2024-02-27 14:54:52
,
所有人可见
,
阅读 29
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int an[100010];
vector<int> alls;
int tr[100010];
int lowbit(int a) {
return a & (-a);
}
void add(int a, int b) {
for (int i = a; i <= 100000; i += lowbit(i)) {
tr[i] += b;
}
}
int query(int a) {
ll sum = 0;
for (int i = a; i > 0; i -= lowbit(i)) {
sum += tr[i];
}
return sum;
}
int find(int a) {
int left = 0, right = alls.size() - 1;
while (left < right) {
int mid = left + right >> 1;
if (alls[mid] < a)
left = mid + 1;
else
right = mid;
}
return left + 1;
}
int main() {
// freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> an[i];
alls.push_back(an[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
ll ans = 0;
for (int i = 1; i <= n; i++) {
add(find(an[i]), 1);
ans += query(100000) - query(find(an[i]));
}
cout << ans << "\n";
return 0;
}