代码求助(不知为啥全RE)

P1908 逆序对

朦胧_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

谢谢大佬,我才发现值域范围。。


|