bzoj4278: [ONTAK2015]Tasowanie

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
const int N = 4e5+1000; 
//int a[N],b[N];
struct dat{
    int x,y,i;
    bool operator < (const dat&b)const{return x<b.x||x==b.x&&y<b.y;}
    bool operator != (const dat b){return x!=b.x||y!=b.y;}
}p[N];
int log[N];
    int n,m;int a[N*2];
    int rk[N*4],sa[N*2];
    void pre(){
        scanf("%d",&n);
        For(i,1,n) scanf("%d",&a[i]);
        a[n+1]=1e9;n++;
        scanf("%d",&m);
        For(i,1,m) scanf("%d",&a[i+n]);
        n+=m+1;m++;a[n]=1e9;
        For(i,1,n) rk[i]=a[i];
        For(j,0,log[n]){
            For(i,1,n) p[i]=(dat){rk[i],rk[i+(1<<j)],i};
            sort(p+1,p+n+1);
            int k=1;
            For(i,1,n){
                rk[p[i].i]=k;
                if(p[i]!=p[i+1])k++;
            }
        }
        For(i,1,n) sa[rk[i]]=i;
    }
 
int s[N];
int main(){
//  freopen("1.in","r",stdin);
    log[0]=-1;For(i,1,N-1) log[i]=log[i>>1]+1;
    pre();
    int t1=1,t2=n-m+1;
    For(i,1,n){
        if((t2>n)||(t1<=n-m&&rk[t1]<=rk[t2])) s[i]=a[t1++];
        else s[i]=a[t2++];
    }
    For(i,1,n-2) printf("%d ",s[i]);
}