P1908求逆序对求助

Isenthalpic @ 2020-07-25 13:06:18

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,a[N],b[N],ans;
void mergesort(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    int i=l,j=mid+1;
    for(int k=l;k<=r;k++)
        if(j>r||i<=mid&&a[i]<a[j])
            b[k]=a[i++];
        else b[k]=a[j++],ans+=mid-i+1;
    for(int k=l;k<=r;k++)a[k]=b[k];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    mergesort(1,n);
    printf("%d",ans);
    return 0;
}

by jiangby @ 2020-07-25 13:39:04

@los_Xxh ans开long long

by fzj2007 @ 2020-07-25 13:50:49

@los_Xxh int？？？您在开玩笑吧

by JRzyh @ 2020-07-25 13:53:44

BIT多好啊

by Isenthalpic @ 2020-07-25 13:55:04

@卖报纸就找我 全开longlong还是30

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e5+10;
ll n,a[N],b[N],ans;
void mergesort(ll l,ll r){
    if(l==r)return;
    ll mid=(l+r)>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    ll i=l,j=mid+1;
    for(ll k=l;k<=r;k++)
        if(j>r||i<=mid&&a[i]<a[j])
            b[k]=a[i++];
        else b[k]=a[j++],ans+=mid-i+1;
    for(ll k=l;k<=r;k++)a[k]=b[k];
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    mergesort(1,n);
    printf("%lld",ans);
    return 0;
}