为什么用树状数组求逆序对会全部RE

sel_fish @ 2019-11-14 18:14:19

#include<cstdio>
#include<cstring>
#define re register int
using namespace std;
typedef long long ll;
const int maxn=510000;
ll ans;
int n,A[maxn],c[maxn];
inline int read() {
    int x=0,cf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') cf=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*cf;
}
int query(int x) {
    int res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}
void add(int x,int v) {
    for(;x<=500000;x+=x&-x) c[x]+=v;
}
int main() {
    n=read();
    for(re i=1;i<=n;i++) A[i]=read();
    for(re i=1;i<=n;i++) {
        add(A[i],1);
        ans+=i-query(A[i]);
    }
    printf("%lld",ans);
    return 0;
}

by 1saunoya @ 2019-11-14 18:25:02

离散化，请

by 莫奈的崖径 @ 2019-11-14 18:25:24

qaq离散化啊

by therehello @ 2019-11-14 18:37:31

@sel_fish 离散化呐，大佬%%%

by 卡车cckk @ 2019-12-24 10:09:12

#include<bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
typedef long long ll;
#define max_ll 0x6fffffffffffffff
using namespace std;

#define to(x) lower_bound(b.begin(),b.end(),x)-b.begin()+1
ll n;
int a[500003];
int c[500003];
vector<int> b;
inline int lowbit(int x){return x&(-x);}
ll inquiry(ll x)
{
    ll ans=0;
    for(ll i=x;i>=1;i-=lowbit(i))
    {
        ans+=c[i];
    }
    return ans;
}
int inser(ll x)
{
    for(ll i=x;i<=n;i+=lowbit(i))
    {
        c[i]++;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    ll ans=n*(n-1)/2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];b.pb(a[i]);
    }
    sort(b.begin(),b.end());
    unique(b.begin(),b.end());
    for(int i=1;i<=n;i++)
    {
        ans-=inquiry(to(a[i]));
        inser(to(a[i]));
        cout<<to(a[i])<<endl;
    }
    cout<<ans;
    return 0;
}

同树状数组党 我也是re后去离散化了 （手动O2，不然容器太慢了）