1794.cpp

这些是我到目前在PKU上做出的题目

#include <iostream>
using namespace std;

int sumRvs,nn,n,m,i,ii,A[60002][2],L[60002][2],R[60002][2];

void merge(int p,int q,int r)
{
    int i,j,k;
	for (i=0;i<q-p+1;i++)
    {
		L[i][0]=A[p+i][0];
		L[i][1]=A[p+i][1];
	}
    for (i=0;i<r-q;i++)
	{
        R[i][0]=A[q+1+i][0];
		R[i][1]=A[q+1+i][1];
	}
    i=0;j=0;
    for (k=p;k<=r;k++)
    {
        if (i!=q-p+1 && j!=r-q)
            if (L[i][1]<R[j][1] || (L[i][1]==R[j][1] && L[i][0]>=R[j][0]))
            {
                A[k][0]=L[i][0];
				A[k][1]=L[i][1];
                i++;
            }
            else
            {
                A[k][0]=R[j][0];
				A[k][1]=R[j][1];
                j++;
            }
        else
            if (i==q-p+1)
            {
				A[k][0]=R[j][0];
				A[k][1]=R[j][1];
                j++;
            }
            else
            {
                A[k][0]=L[i][0];
				A[k][1]=L[i][1];
                i++;
            }                        
    }   
}

void merge_sort(int p,int r)
{
    int q=(p+r)/2;
    if (p<q)
    {
        merge_sort(p,q);
    }
    if (q+1<r)
    {    
        merge_sort(q+1,r);
    }    
    merge(p,q,r);
}

void merge2(int p, int q, int r)
{
    int *L=new int[q-p+1],*R=new int[r-q],i,j,k;
    for (i=0;i<q-p+1;i++)
		L[i]=A[p+i][0];
    for (i=0;i<r-q;i++)
        R[i]=A[q+1+i][0];
    i=0;j=0;
    for (k=p;k<=r;++k)
    {
        if (i!=q-p+1 && j!=r-q)
            if (L[i]<=R[j])
            {
                sumRvs+=j;
                A[k][0]=L[i];
                ++i;
            }
            else
            {
                A[k][0]=R[j];
                ++j;
            }
        else
            if (i==q-p+1)
            {
                A[k][0]=R[j];
                ++j;
            }
            else
            {
                sumRvs+=j;
                A[k][0]=L[i];
                ++i;
            }                        
    }
    
    delete [] L;
    delete [] R;
}

void merge_sort2(int p,int r)
{
    int q=(p+r)/2;
    if (p<q)
    {
        merge_sort2(p,q);
    }
    if (q+1<r)
    {    
        merge_sort2(q+1,r);
    }    
    merge2(p,q,r);
}
    
int main()
{
	cin>>nn;
	for (ii=1;ii<=nn;ii++)
	{
		cin>>n>>m;
		sumRvs=0;
		for (i=0;i<n+m;i++)
			cin>>A[i][0]>>A[i][1];
		merge_sort(0,n+m-1);
		merge_sort2(0,n+m-1);
		cout<<"Scenario #"<<ii<<":\n"<<sumRvs<<"\n\n";
	}
    return 0;
}