首页 > 其他 > 详细

【luogu1908/1774】 逆序对 [逆序对]

时间:2019-07-12 20:07:11      阅读:104      评论:0      收藏:0      [点我收藏+]

1908 逆序对

 1774 最接近神的人_NOI导刊2010提高(02)

 

并归排序看得我一愣一愣的.....大概我真的不适合队列 排序啥的 我是个废人 瘟得伤心

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)>(y)?(y):(x)
const int N=500000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,a[N],rk[N];
ll ans=0ll;
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch==-,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

void mergesort(int l,int r){
    if(l>=r) return;
    int mid=(l+r)>>1,pl=l,pr=mid+1,k=l;
    mergesort(l,mid),mergesort(mid+1,r);
    while(pl<=mid&&pr<=r)
    if(a[pl]<=a[pr]) rk[k++]=a[pl++];
    else rk[k++]=a[pr++],ans+=(ll)mid-pl+1;
    while(pl<=mid) rk[k]=a[pl],++k,++pl;
    while(pr<=r) rk[k]=a[pr],++k,++pr;
    for(int i=l;i<=r;++i) a[i]=rk[i];
}

int main(){
//    freopen("in.txt","r",stdin);
    rd(n);
    for(int i=1;i<=n;++i) rd(a[i]);
    mergesort(1,n);
    printf("%lld",ans);
    return 0;
}
 

 

【luogu1908/1774】 逆序对 [逆序对]

原文:https://www.cnblogs.com/lxyyyy/p/11178011.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!