50分求助,后面10个点WA了

P1908 逆序对

kanchui666 @ 2022-08-10 18:39:59

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,ans;
int a[N],b[N],t[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))
    {
        t[i]+=y;    
    }
}
int query(int x){
    int anss=0; 
    for(int i=x;i;i-=lowbit(i))
    {
        anss+=t[i];
    }
    return anss;
}
int cmp(int x,int y){
    return a[x]<a[y];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=i;
    }
    stable_sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        a[b[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        add(a[i],1);    
        ans+=(i-query(a[i]));
    } 
    printf("%d",ans);
    return 0;   
} 

by Eason2009 @ 2022-08-10 18:44:12

开long long,还有你这个离散化遇到重复数字就会炸啊


by irris @ 2022-08-10 18:53:07

你离散化了个你好寂寞


by 老_王 @ 2022-08-10 19:06:26

这不归并排序板子吗


by C201529 @ 2022-08-10 19:49:54

ans 定为 long long 即可 \ (记得把下面的 scanf 写成 "%lld")


|