Problem:1688 新建题解

Solution_ID:30214            归并排序

                   时间复杂度:Θ(n^79865372867983) 空间复杂度:Θ(n^80937406874326)

#include <iostream>
#include <cstdio>
using namespace std; int m[100010];
long long ans; void Merge(int st,int mid,int en)
{
int i=st;
int j=mid+1;
int k=0;
int t[100010];
while(i<=mid&&j<=en)
{
if(m[i]>m[j])
{

ans+=mid-i+1;
t[++k]=m[j];
j++;
}
else
{
t[++k]=m[i];
i++;
}
}
while(i<=mid)
{
t[++k]=m[i];
i++;
}
while(j<=en)
{
t[++k]=m[j];
j++;
}
for(int i=1;i<=k;i++)
m[st+i-1]=t[i];

} void MergeSort(int st,int en)
{
int mid=(st+en)/2;
if(st<en)
{
MergeSort(st,mid);
MergeSort(mid+1,en);
Merge(st,mid,en);
}
} int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
cin >> m[i];
MergeSort(1,n);
cout << ans << endl;
return 0;
}


by 50967 十一月 19, 2017, 2:18 p.m.

Solution_ID:28695            好像不离散化更快

                   时间复杂度:Θ() 空间复杂度:Θ()

//不离散化:


#include<stdio.h>

#include<string.h>

const int maxn=100010;

long long tree[maxn*4];


long long query(int num,int l,int r,int x,int y)

{

    if(x<=l&&r<=y)

        return tree[num];

    if(x>r||y<l) return 0;

    int mid=(l+r)>>1;

    long long sum=0;

    if(x<=mid) sum+=query(num<<1,l,mid,x,y);

    if(y>mid) sum+=query(num<<1|1,mid+1,r,x,y);

    return sum;

}

void update(int num,int l,int r,int x)

{

    if(l==r&&x==l)

    {

        tree[num]++;

        return ;

    }

    int mid=(l+r)>>1;

    if(mid>=x) update(num<<1,l,mid,x);

    else update(num<<1|1,mid+1,r,x);

    tree[num]=tree[num<<1]+tree[num<<1|1];

}

int main()

{

    int n;

    scanf("%d",&n);

    memset(tree,0,sizeof(tree));

    long long sum=0;

    int x;

    for(int i=0; i<n; i++)

    {

        scanf("%d",&x);

        sum+=query(1,1,maxn,x+1,maxn);

        update(1,1,maxn,x);

    }

    printf("%lld\n",sum);

    return 0;

}


//离散化


#include<stdio.h>

#include<string.h>

#include<map>

#include<algorithm>

using namespace std;

const int maxn=100010;

long long tree[maxn*4];

map<int,int>q;

int a[maxn],b[maxn];


long long query(int num,int l,int r,int x,int y)

{

    if(x<=l&&r<=y)

        return tree[num];

    if(x>r||y<l) return 0;

    int mid=(l+r)>>1;

    long long sum=0;

    if(x<=mid) sum+=query(num<<1,l,mid,x,y);

    if(y>mid) sum+=query(num<<1|1,mid+1,r,x,y);

    return sum;

}

void update(int num,int l,int r,int x)

{

    if(l==r&&x==l)

    {

        tree[num]++;

        return ;

    }

    int mid=(l+r)>>1;

    if(mid>=x) update(num<<1,l,mid,x);

    else update(num<<1|1,mid+1,r,x);

    tree[num]=tree[num<<1]+tree[num<<1|1];

}

int main()

{

    int n;

    scanf("%d",&n);

    memset(tree,0,sizeof(tree));

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    q.clear();

    long long sum=0;

    int x;

    int k=0;

    for(int i=0; i<n; i++)

    {

        scanf("%d",&a[i]);

        b[k++]=a[i];

    }

    sort(b,b+k);

    k=unique(b,b+k)-b;

    for(int i=0;i<k;i++)

      q[b[i]]=i;

    for(int i=0; i<n; i++)

    {

        sum+=query(1,0,k-1,q[a[i]]+1,k-1);

        update(1,0,k-1,q[a[i]]);

    }

    printf("%lld\n",sum);

    return 0;

}



by 62123 八月 15, 2017, 10:33 a.m.

Solution_ID:28464            线段树 一题代码A两题

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define f(i,l,r) for(int i=l;i<=r;i++)
#define maxn 1000010
#define lid id<<1
#define rid id<<1|1
typedef long long ll;
using namespace std;
int n,t=0;
int aa[maxn];
ll ans;
struct haha {
	int v,order;
} a[maxn];
struct node {
	int l,r;
	ll num;
} tr[maxn*4];
inline void build(int id,int l,int r) {
	tr[id].l=l;
	tr[id].r=r;
	tr[id].num=0;
	if(l==r)
		return;
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
}
inline void update(int id,ll x) {
	if(tr[id].l==x&&tr[id].r==x) {
		tr[id].num++;
		return;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(x<=mid)
		update(lid,x);
	else
		update(rid,x);
	tr[id].num=tr[lid].num+tr[rid].num;
}
inline ll find(int id,int l,int r) {
	if(tr[id].l==l&&tr[id].r==r) {
		return tr[id].num;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid)
		return find(lid,l,r);
	else if(l>mid)
		return find(rid,l,r);
	else
		return find(lid,l,mid)+find(rid,mid+1,r);

}
inline ll read() {
	char c=getchar();
	ll x=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	return x;
}
int cmp(haha a,haha b) {
	return a.v<b.v;
}
int main() {
	scanf("%d",&n);
	f(i,1,n)
	a[i].v=read(),a[i].order=i;
	sort(a+1,a+n+1,cmp);
	f(i,1,n) {
		if(a[i].v!=a[i-1].v)
			t++;
		aa[a[i].order]=t;
	}
	build(1,1,n);
	f(i,1,n) {
		update(1,aa[i]);
		ans+=i-find(1,1,aa[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

by 51192 八月 4, 2017, 6 p.m.

Solution_ID:28420            归并排序

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

using namespace std;

int a[200005];

int temp[200005];

long long int ans=0;

void mergesort(int l,int mid,int r)

{

int i=l;

int j=mid+1;

 

int k=0;  

   while(i<=mid&&j<=r)

{

   if(a[i]<=a[j])

{

   temp[k++]=a[i++];

}

   else

{

temp[k++]=a[j++];


 ans+=mid-i+1;

                 

   }

  while(i<=mid)

    temp[k++]=a[i++];

    

   while(j<=r)

    temp[k++]=a[j++];

    

for(int m=0;m<k;m++)

a[l+m]=temp[m];

}

void sort_it(int l,int r)

{

if(l<r)

{

int mid=(l+r)>>1;

 

  sort_it(l,mid);

  sort_it(mid+1,r);

  

  mergesort(l,mid,r);

    }

}

int main()

{

     int n;

     scanf("%d",&n);

     

         for(int i=1;i<=n;i++)

         scanf("%d",&a[i]);

         

         sort_it(1,n);

         

         //for(int i=1;i<=n;i++)

         //cout<<a[i]<<" ";

     

         printf("%lld",ans);

        

        

    return 0;



by 59175 八月 3, 2017, 2:10 p.m.

Solution_ID:28406            树状数组 离散化

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500005;
struct Node{
    int val;
    int pos;
}node[N];
int c[N],reflect[N],n;

bool cmp(Node a,Node b){
      if(a.val!=b.val)
          return a.val<b.val;
      return a.pos<b.pos;
}

int lowbit(int x) {return x & (-x);}

void update(int x){
    while (x <= n){
        c[x]+=1;
        x +=lowbit(x);
    }
}

long long getsum(int x){
    long long sum = 0;
    while (x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

int main(){
    while (scanf("%d", &n) != EOF && n){
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &node[i].val);
            node[i].pos = i;
        }
        sort(node+1,node+n+1,cmp);   //排序
        for (int i=1;i<=n;i++) reflect[node[i].pos]=i;   //离散化
        for (int i=1;i<=n;i++) c[i]=0;   //初始化树状数组
        long long ans=0;
        for (int i=1;i<=n;i++){
            update(reflect[i]);
            ans+=i-getsum(reflect[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}


by 43387 八月 2, 2017, 8:18 p.m.

Solution_ID:28398            线段树 没有离散化 勉强过

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cmath>

#define lid id*2

#define rid id*2+1

#define maxn 1000010

#define f(i,l,r) for(int i=l;i<=r;i++)

using namespace std;

typedef long long ll;

int n,a[maxn];

ll ans;

int aa[maxn],b[maxn];

struct haha {

int l,r;

ll num;

} tr[maxn*4];

inline void build(int id,int l,int r) {

tr[id].l=l;

tr[id].r=r;

tr[id].num=0;

if(l==r)

return;

int mid=(l+r)/2;

build(lid,l,mid);

build(rid,mid+1,r);

tr[id].num=tr[lid].num+tr[rid].num;

}

inline ll search(int id,int l,int r) {

if(l==tr[id].l&& r==tr[id].r)

return tr[id].num;

int  mid=(tr[id].l+tr[id].r)/2;

if(r<=mid)

return search(lid,l,r);

else if(l>mid)

return search(rid,l,r);

else

return search(lid,l,mid)+search(rid,mid+1,r);

}

inline void insert(int id,int x) {

if(x==tr[id].l&&x==tr[id].r) {

tr[id].num++;

return;

}

int mid=(tr[id].l+tr[id].r)/2;

if(x<=mid)

insert(lid,x);

else

insert(rid,x);

tr[id].num=tr[rid].num+tr[lid].num;

}

inline int read() {

char c=getchar();

int x=0;

while(c<'0'||c>'9') c=getchar();

while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

return x;

}

int main() {

cin>>n;

f(i,1,n)

a[i]=read();

build(1,1,1000000);

f(i,1,n) {

insert (1,a[i]);

ans+=i-search(1,1,a[i]);

}

cout<<ans;

return 0;

}


by 51192 八月 2, 2017, 3:04 p.m.

Solution_ID:26582            数据好水啊

                   时间复杂度:Θ() 空间复杂度:Θ()

树状数组完全错误的做法得了70

惊了


by 19235 四月 28, 2017, 7:11 p.m.

Solution_ID:24906            我草你妈

                   时间复杂度:Θ() 空间复杂度:Θ()

这里写题解


by 52392 二月 8, 2017, 4:36 p.m.

Solution_ID:24675            归并排序

                   时间复杂度:Θ(O(nlogn)) 空间复杂度:Θ()

这里写题解


by 19018 一月 25, 2017, 4:57 p.m.

Solution_ID:24608            好气喔

                   时间复杂度:Θ(o(nlogn)) 空间复杂度:Θ(o(n))

裸树状数组/归并排序,但是需要用longlong存答案。。不然会炸。。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

int a[200000],b[200000],c[200000],n;
unsigned long long ans;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int tot=unique(b+1,b+1+n)-b;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot,a[i])-b;
    for(int i=1;i<=n;ans+=i++){
        for(int j=a[i];j<=n;j+=j&-j)c[j]++;
        for(int j=a[i];j;j-=j&-j)ans-=c[j];
    }
    printf("%lld\n",ans);
}


by 25879 一月 23, 2017, 8:54 a.m.

Solution_ID:24440            树状数组(好气啊)

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>


using namespace std;


long long n,x,ans=0;

long long c[100100],b[100100];


struct node{

long long x,id,id1;

}a[100100];


long long lowbit(long long x)

{

return x&(-x);

}


void add(long long i,long long x)

{

while(i<=n)

{

c[i]+=x;

i+=lowbit(i);

}

}


long long sum(long long i)

{

long long s=0;

while(i>0)

{

s+=c[i];

i-=lowbit(i);

}

return s;

}


bool cmp1(node a,node b)

{

return a.x==b.x?a.id<b.id:a.x<b.x;

}


bool cmp2(node a,node b)

{

return a.id<b.id;

}


int main()

{

ans=0;

memset(c,0,sizeof(c));

scanf("%lld",&n);

for(long long i=1;i<=n;i++)

{

scanf("%lld",&a[i].x);

a[i].id=i;

}

sort(a+1,a+n+1,cmp1);

a[1].id1=1;

for(int i=2;i<=n;i++)

{

        if(a[i].x==a[i-1].x)

a[i].id1=a[i-1].id1;

        else 

a[i].id1=a[i-1].id1+1;

    }

    sort(a+1,a+n+1,cmp2);

for(long long i=1;i<=n;i++)

{

x=a[i].id1;

add(x,1);

ans+=(i-sum(x));

}

printf("%lld\n",ans);

}


by 28966 一月 17, 2017, 11:05 a.m.

Solution_ID:24430            很巧妙的方法,十分简洁

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdlib>

#include<iostream>

#include<cstdio>

using namespace std;

int n,a[500010],c[1000001],maxn=0;

long long int tot;

int lowbit(int x)

{

return x&(-x);

}

void add(int x)

{

for(int i=x;i<=maxn;i+=lowbit(i))

c[i]++;

}

int sum(int x)

{

if(x<0) return 0;

if(x==0) return c[0];

long long int total=0;

for(;x>0;x-=lowbit(x))

total+=c[x];

return total;

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

if(a[i]>maxn) maxn=a[i];

}

for(int i=n;i>=1;i--)

{

tot+=sum(a[i]-1);

add(a[i]);

}

printf("%lld\n",tot);

return 0;

}


by 28870 一月 17, 2017, 8:45 a.m.

Solution_ID:23999            归并排序

                   时间复杂度:Θ() 空间复杂度:Θ()

program merge_sort;

var

  a:array[0..100000] of longint;

  i,n:longint;

  •   tot:int64;

procedure msort(left,right:longint);

var

  temp:array[0..100000] of longint;

  j,jishu,mid,left_pin,right_pin:longint;

begin

  if left=right then exit;  // 只有一个元素跳跳跳

  

  mid:=(left+right) div 2;

  left_pin:=left;   right_pin:=mid+1;

  jishu:=left;              //记录合并了几个

  

  msort(left_pin,mid);

  msort(right_pin,right);     //分解结构

  

  while (left_pin<=mid) and (right_pin<=right) do 

    begin

       if a[left_pin]<=a[right_pin] then 

                                    begin

                                      temp[jishu]:=a[left_pin];

                                      inc(left_pin);

                                    end

        else begin

               tot:=tot+mid-left_pin+1;

               temp[jishu]:=a[right_pin];

               inc(right_pin);

             end;

       inc(jishu);

    end;

  while left_pin<=mid do begin 

                           temp[jishu]:=a[left_pin];

                           inc(left_pin);

                           inc(jishu);

                         end;

  while right_pin<=right do begin 

                           temp[jishu]:=a[right_pin];

                           inc(right_pin);

                           inc(jishu);

                         end;                          //汇总到临时数组

                         

  for j:= left to right do                             //存储结果

    a[j]:=temp[j];

end;


begin

  readln(n);

  for i:= 1 to n do 

    read(a[i]);

  msort(1,n);

  //for i:= 1 to n-1 do 

  //  write(a[i],' ');

  //writeln(a[n]);

writeln(tot);

end.


by 37293 十二月 17, 2016, 4:48 p.m.

Solution_ID:23737            党爹的第一个题解

                   时间复杂度:Θ(advbhjhjkdasvjkl) 空间复杂度:Θ()

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
const int inf=100000000; 
int lowbit(int x){
	return x&(-x);
}
struct num{
	int w,pos;
}a[100001];
int c[100001];
int reflect[100001];
bool cmp(num x,num y) {return(x.w<y.w);}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
void jia(int x){
	while(x<=n)		
	{
		c[x]++;
		x+=lowbit(x);
	}
} //+1
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].w;
		a[i].pos=i;
	}
	sort(a+1,a+n+1,cmp);
	int reflection=0;a[0].w=-inf;
	for(int i=1;i<=n;i++){
		if(a[i].w!=a[i-1].w)
		reflection++;
		reflect[a[i].pos]=reflection;
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		jia(reflect[i]);
		ans+=i-sum(reflect[i]);
	}
	cout<<ans;
	return 0;
}


by 45337 十一月 29, 2016, 4:47 p.m.

Solution_ID:23248            WA了两次以后才发现坑……

                   时间复杂度:Θ(o(n log n)) 空间复杂度:Θ(o(n))

var

        n,i:longint;

        a,b:array[0..1000001] of longint;

        ans:int64;   //没错,罪魁祸首就是他



procedure m(s1,s2,e:longint);

var

        i,j,k:longint;

begin

        i:=s1;

        j:=s2;

        k:=s1;

        while (i<s2)and(j<=e) do

        begin

                if a[i]<=a[j] then

                begin

                        b[k]:=a[i];

                        inc(i);

                end

                else

                begin

                        b[k]:=a[j];

                        ans:=ans+s2-i;

                        inc(j);

                end;

                inc(k);

        end;

        while i<s2 do

        begin

                b[k]:=a[i];

                inc(i);

                inc(k);

        end;

        while j<=e do

        begin

                b[k]:=a[j];

                inc(j);

                inc(k);

        end;

        for i:=s1 to e do

        a[i]:=b[i];

end;



procedure sort(l,r:longint);

begin

        if l=r then

        exit;

        sort(l,(l+r)>>1);

        sort((l+r)>>1+1,r);

        m(l,(l+r)>>1+1,r);

end;



begin

        read(n);

        for i:=1 to n do

        read(a[i]);

        ans:=0;

        sort(1,n);

        write(ans);

end.


by 31738 十一月 11, 2016, 9:05 p.m.

Solution_ID:21430            树状数组

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <cstdio>

using namespace std;

int a[100050],b[100050],n;

long long ans=0;


int zxr(int x){ //修改(第x个+1)

    for (; x<=100000; x+=x&-x) b[x]++;

}


int xyl(int x){ //求和(前x项)

    long long k=0;

    for (; x; x-=x&-x) k+=b[x];

    return k;

}


int main(){

    scanf("%d",&n);

    for (int i=1; i<=n; i++)scanf("%d",&a[i]);

    for (int i=n; i>=1; i--){

        ans+=xyl(a[i]-1);

        zxr(a[i]);

    }

    printf("%lld",ans);

}


by 26907 九月 17, 2016, 4:39 p.m.

Solution_ID:21226            WATER

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

int a[100001],b[100001];

long long ans;


void msort(int l,int r)

{

if(l>=r)return;

int mid=(l+r)/2;

msort(l,mid);

msort(mid+1,r);

int i=l,j=mid+1,t=l-1;

while(i<=mid&&j<=r)

{

if(a[i]<=a[j])b[++t]=a[i++];

else

{

ans+=mid-i+1;

b[++t]=a[j++];

}

}

while(i<=mid)b[++t]=a[i++];

while(j<=r)b[++t]=a[j++];

for(i=l;i<=r;i++)a[i]=b[i];

return;

}


int main()

{

int n,m,i,j,k;

cin>>n;

for(i=1;i<=n;i++)

{

cin>>a[i];

}

msort(1,n);

cout<<ans<<endl;

return 0;

}


by 34878 九月 7, 2016, 9:02 p.m.

Solution_ID:21076            我真傻,真的

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

struct node{

int data,pos;

}d[150000];

int n,c[150000],m[150000]; 

int lowbit(int x){

return x&(-x);

}

int cmp(node x,node y){

return x.data<y.data;

}

void add(int x,int v){

for(;x<=n;x+=lowbit(x)){

c[x]+=v;

}

}

int work(int x){

int sum=0;

for(;x;x-=lowbit(x)){

sum+=c[x];

}

return sum;

}

int main(){

cin>>n;

for(int i=1;i<=n;i++){

cin>>d[i].data;

d[i].pos=i;

}

sort(d+1,d+n+1,cmp);

for(int i=1;i<=n;i++) m[i]=0;

int tmp=1;

m[d[1].pos]=tmp;

for(int i=2;i<=n;i++){

if(d[i].data==d[i-1].data) m[d[i].pos]=tmp;

else m[d[i].pos]=++tmp;

}

for(int i=1;i<=n;i++) c[i]=0; 

long long sum=0;

//for(int i=1;i<=n;i++) cout<<d[i].pos<<" "<<d[i].data<<endl;

for(int i=1;i<=n;i++){

add(m[i],1);

//cout<<work(m[i])<<endl;

sum+=(i-work(m[i]));

}

cout<<sum;


by 30993 八月 29, 2016, 4:35 p.m.

Solution_ID:20906            归排 || 树状数组

                   时间复杂度:Θ() 空间复杂度:Θ()

树状数组:

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define mmm 99999997

#define maxint 100005

using namespace std;

struct aaa{

int x,i;

bool operator <(const aaa &g) const{ if(x==g.x) return i<g.i;return x<g.x;}

}p[maxint];

int n,a[maxint];

long long c[maxint];

void add(int x)

{

int i;

for(i=x;i<=n;i+=i&(-i)) c[i]++;

}

long long query(int x)

{

int i;

long long ans=0;

for(i=x;i>=1;i-=i&(-i)) ans+=c[i];

return ans;

}

int main()

{

int i;

long long ans=0;

scanf("%d",&n);

for(i=1;i<=n;i++)

{

scanf("%d",&a[i]);

p[i].i=i;p[i].x=a[i];

}

sort(p+1,p+1+n);

for(i=1;i<=n;i++)

{

a[p[i].i]=i;

}

add(a[1]);

for(i=2;i<=n;i++) 

{

add(a[i]);

ans+=query(n)-query(a[i]);

}

printf("%lld",ans);

//for(i=1;i<=n;i++) printf("%d _ %d\n",p[i].x,p[i].i);  //调试用

}

归排:

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <iostream>

#include <cstring>

#include <string>

using namespace std;

long long a[100005],ans=0;int n;

void merge_sort(int  l1,int  r1,int l2,int r2)

{

int i,tmpt=1,t1=l1,t2=l2; 

long long tmp[100005];

while(t1<=r1&&t2<=r2)

{

if(a[t1]<=a[t2])

{

tmp[tmpt++]=a[t1++];

}

else

{

ans+=(r1-t1+1);

tmp[tmpt++]=a[t2++];

}

}

while(t1<=r1)

{

tmp[tmpt++]=a[t1++];

}

while(t2<=r2)

{

tmp[tmpt++]=a[t2++];

}

for(i=1;i<tmpt;i++)

{

a[i+l1-1]=tmp[i];

}

}

void merge(int l,int r)

{

if(l>=r) return;

int mid=(l+r)/2;

merge(l,mid);

merge(mid+1,r);

merge_sort(l,mid,mid+1,r);

}

int main()

{

int i;

scanf("%d",&n);

for(i=1;i<=n;i++) scanf("%lld",&a[i]);

merge(1,n);

for(i=1;i<=n;i++) printf("%lld ",a[i]);

printf("\n%lld",ans);

}


by 20586 八月 22, 2016, 10:19 a.m.

Solution_ID:20359            泥嚎Long Long

                   时间复杂度:Θ() 空间复杂度:Θ()

Long Long再一次成功坑人。


by 35287 八月 4, 2016, 5:07 p.m.