为什么全RE啊!求救

P1908 逆序对

Rorou @ 2024-02-06 23:15:00

#include<bits/stdc++.h>
#define int long long 
#define N 500005
using namespace std;
int a[N],t[N],n,q;
int logg(int x){return x&(-x);}
void add(int x){
    for(int i=x;i<=n;i+=logg(i))t[i]++;
    return;
}
int sum(int x){
    int num=0;
    for(int i=x;i;i-=logg(i)){
        num+=t[i];
    }
    return num;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        add(a[i]);
        q+=i-sum(a[i]);
    }
    cout<<q;

    return 0;
} 

by 心灵震荡 @ 2024-02-07 07:21:00

注意 a_i \le 10^9,需要一个离散化


by Pink_Cut_Tree @ 2024-02-07 14:30:03

@Canthy_zy 排序+离散化,注意值域(lrh 好像把事情解释的很明白了)


by Rorou @ 2024-02-07 19:32:49

@Present_Coming_Time @心灵震荡 万分感谢大佬们!


by Rorou @ 2024-02-07 19:33:21

调试代码go!此贴结


by Pink_Cut_Tree @ 2024-02-07 20:09:39

@Canthy_zy 读入时给数据编号


|