蒟蒻求助!!!

P1908 逆序对

喵の耳 @ 2019-04-06 09:43:27

全都RE了

ORZ

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],c[1000005],b[1000005];
void add(int x,int y){
    for(;x<=n;x+=x&-x)c[x]+=y;
}
int ask(int x){
    int ans=0;
    for(;x;x-=x&-x)ans+=c[x];
    return ans;
}
bool cmp(int x,int y){
    return a[x]>a[y];
}
int main(){

    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,c[i]);
        b[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=n;i>=1;i--){
        ans+=ask(b[i]-1);
        add(b[i],1);
    }
    printf("%d",ans);

    return 0;
}

by aminoas @ 2019-04-06 09:57:30

用树状数组做逆序对?!


|