各位大佬帮忙看一下哪里错了

P1908 逆序对

神之右大臣 @ 2019-08-02 14:02:36

思路是树状数组+离散化

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[500010];
struct li{
    int v;
    int s;
}san[500010],hua[500010];
bool cmp(li x,li y)
{
    return x.v<y.v;
}
int c[500010];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x)
{
    while(x<=n){
        c[x]+=1;
        x+=lowbit(x);
    }
}
int read(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
signed main ()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        san[i].v=a[i];
        san[i].s=i;
    }
    sort(san+1,san+1+n,cmp);
    for(int i=1;i<=n;i++){
        hua[i].s=i;
        hua[i].v=san[i].s;
    }
    sort(hua+1,hua+1+n,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        add(hua[i].s);
        ans+=(read(n)-read(hua[i].s));
    }
    cout<<ans;  
}

by mendessy @ 2019-08-02 14:12:07

不太看得懂你的离散化,可以再网上搜一下模板


|