朦胧_XY @ 2022-04-30 23:40:49
#include<iostream>
#include<cstring>
#define N 500005
#define ll long long
using namespace std;
ll n, ans, a[N], c[N], r[N];
ll read(){
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
ll lowbit(ll x){
return x & -x;
}
void add(ll x, ll y){
for(ll i = x; i <= n; i += lowbit(i)){
c[i] += y;
}
}
ll getsum(ll x){
ll sum = 0;
for(ll i = x; i > 0; i -= lowbit(i)){
sum += c[i];
}
return sum;
}
int main(){
n = read();
for(ll i = 1; i <= n; i++){
a[i] = read();
}
for(ll i = n; i >= 1; i--){
r[i] = getsum(a[i] - 1);
add(a[i], 1);
ans += r[i];
}
printf("%lld", ans);
return 0;
}
我数组已经开够了,但还是全RE,求助QwQ
by irris @ 2022-05-01 00:45:02
by 朦胧_XY @ 2022-08-04 14:18:08
谢谢大佬,我才发现值域范围。。