题目描述
blablabla
样例
blablabla
算法1
(树状数组)
include [HTML_REMOVED]
using namespace std;
const int N = 200005;
long long n, a[N], ans1[N], ans2[N], c[200005], ans, cnt;
long long lowbit(long long x){
return x & (-x);
}
void modify(long long x, long long k){
for(long long i = x; i <= 200001; i += lowbit(i)){
c[i] += k;
}
}
long long getSum(long long x){
long long sum = 0;
for(long long i = x; i > 0; i-=lowbit(i)){
sum += c[i];
}
return sum;
}
int main(){
scanf(“%lld”, &n);
for(long long i = 1; i <= n; i){
scanf(“%lld”, &a[i]);
ans1[i] = getSum(a[i]);
modify(a[i], 1);
}
memset(c, 0, sizeof(c));
for(long long i = n; i >= 1; i–){
ans2[i] = getSum(a[i]);
modify(a[i], 1);
}
for(long long i = 1; i <= n; i){
ans += (n - i - ans2[i]) * (i - ans1[i] - 1);
cnt += ans2[i] * ans1[i];
}
printf(“%lld %lld”, ans, cnt);
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla