萌新刚学OI，救救孩子吧P1908

由比滨丶雪乃 @ 2019-07-31 09:42:29

#include <iostream>
#include <cstdio> 
#include <cstring>
#include <algorithm>
#define ll long long
ll const maxn=5e5+5;

using namespace std;
ll a[maxn],b[maxn];
ll n,ans;

inline int read(){
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}
void merge_sort(ll l,ll r)
{
    if(l==r) return;
    ll mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    ll p1=l;
    ll p2=mid+1;
    for(ll i=l;i<=r;++i)
    {
        if(p1<=mid && p2<=r)
        {
            if(a[p1]<a[p2]) b[i]=a[p1++];
            else b[i]=a[p2++],ans+=mid-p1+1;
        }
        else
        {
            if(p1<=mid) b[i]=a[p1++];
            else b[i]=a[p2++];
        }
    }
    for(ll i=l;i<=r;i++)
        a[i]=b[i];
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)  a[i]=read();
    merge_sort(1,n);
    printf("%lld",ans);
    return 0;
}

by 由比滨丶雪乃 @ 2019-07-31 09:43:14

为什么只有三十分（雾）

by Leap_Frog @ 2019-07-31 09:47:55

看到归并排序（光速逃

by 由比滨丶雪乃 @ 2019-07-31 09:48:32

@小跳蛙 (雾）

by 由比滨丶雪乃 @ 2019-07-31 09:49:51

洛谷上1和l区别不明显啊= =

by Gary818 @ 2019-07-31 09:50:27

@由比滨丶雪乃
点开

by AFO蒟蒻选手 @ 2019-07-31 09:50:39

@由比滨丶雪乃

//1311求逆序对
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int a[maxn],r[maxn],n;
long long ans=0; 
void msort(int s,int t){
    if(s==t) return ;
    int mid=(s+t)/2;
    msort(s,mid),msort(mid+1,t);
    int i=s,j=mid+1,k=s;
    while(i<=mid&&j<=t){
        if(a[i]<=a[j]) r[k++]=a[i++];
        else r[k++]=a[j++],ans+=(long long)mid-i+1;
    }
    while(i<=mid) r[k]=a[i],k++,i++;
    while(j<=t) r[k]=a[j],k++,j++;
    for(int i=s;i<=t;i++) a[i]=r[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    msort(1,n);
    printf("%lld\n",ans);
    return 0;
}

by 由比滨丶雪乃 @ 2019-07-31 09:54:41

一定要定个变量来记录b数组的下标码（雾）

by 由比滨丶雪乃 @ 2019-07-31 10:01:32

还是不知道我原先做法哪错了QAQ

by 禰豆子 @ 2019-07-31 10:16:22

写树状数组啊（雾）

by doyo @ 2019-07-31 10:36:06

@由比滨丶雪乃 a[p1]<a[p2]改成a[p1]<=a[p2]