楼兰图腾
本题用树状数组来储存每个数是否出现过。
首先正向做一遍,并且将大于i位置数的个数和小于i位置数的个数预处理。
然后反向做一遍,把大于i位置个数和预处理的左边大于i位置数个数相乘作为答案,小于的也一样。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int a[N], tr[N];
int lowr[N], greatr[N];
int n;
int lowbit(int x) {
return x & -x;
}
int add(int x, int d) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}
int query(int x) {
int sum = 0;
for (int i = x; i; i -= lowbit(i)) sum += tr[i];
return sum;
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
int y = a[i];
greatr[i] = query(n) - query(y);
lowr[i] = query(y - 1);
add(y, 1);
}
LL sumv = 0, suma = 0;
memset(tr, 0, sizeof tr);
for (int i = n; i; i--) {
int y = a[i];
sumv += (LL)greatr[i] * (query(n) - query(y));
suma += (LL)lowr[i] * query(y - 1);
add(y, 1);
}
cout << sumv << ' ' << suma << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}