考虑归并排序，问题即如何合并两个序列\(A,B\)
-
不妨假设\(|A|>|B|\)，将\(A\)按下标奇偶性划分为\(A_{0}\)和\(A_{1}\)
-
将\(A_{0}\)与\(B\)归并，得到序列\(C\)
-
对于\(A_{1}\)中的元素，仅需与（\(C\)中）\(A_{0}\)中相邻两数间的\(B\)中元素比较
比较次数为\(|B|\)，用莫队实现，操作次数为\(O(l\sqrt{|B|})\)（其中\(l\)为区间长度）
综上，复杂度即\(T(n)=T(\frac{n}{2})+O(l\sqrt{n})\)，由主定理得\(T(l)=O(l\sqrt{l})\)
在此基础上，原问题复杂度即\(T'(n)=2T'(\frac{n}{2})+O(n\sqrt{n})\)，由主定理得\(T'(n)=O(n\sqrt{n})\)
综上，总比较次数为\(O(n\log n)\)，总移动次数为\(O(n\sqrt{n})\)
#include<bits/stdc++.h>
#include "lancllords.h"
using namespace std;
typedef vector<int>vi;
const int N=150005;
int p,q,K;vi ans;
unordered_map<int,bool>mat[N];
struct Node{
int x,y;
bool operator < (const Node &n)const{
return (x/K!=n.x/K ? x/K<n.x/K : y<n.y);
}
};vector<Node>Q;
bool cmp(int x,int y){
if (mat[x].find(y)!=mat[x].end())return mat[x][y];
while (p<x)p++,inc_p();
while (p>x)p--,dec_p();
while (q<y)q++,inc_q();
while (q>y)q--,dec_q();
return mat[x][y]=cmp();
}
vi merge(int l,vi vx,vi vy){
int sx=vx.size(),sy=vy.size();
if (sx<sy)swap(vx,vy),swap(sx,sy);
if (!sy)return vx;
int k=0;vi v;
for(int i=1;i<sx;i+=2)v.push_back(vx[i]);
vy=merge(l,v,vy),sy=vy.size();
Q.clear();
for(int i=0;i<sx;i+=2){
while ((k<sy)&&((i==sx-1)||(vy[k]!=vx[i+1])))Q.push_back(Node{vx[i],vy[k++]});
if (k<sy)k++;
}
if (!Q.empty()){
K=max((int)(l/sqrt(Q.size())),1);
sort(Q.begin(),Q.end());
for(Node i:Q)cmp(i.x,i.y);
}
k=0,v.clear();
for(int i=0;i<sx;i+=2){
bool flag=0;
while ((k<sy)&&((i==sx-1)||(vy[k]!=vx[i+1]))){
if ((!flag)&&(cmp(vx[i],vy[k])))flag=1,v.push_back(vx[i]);
v.push_back(vy[k++]);
}
if (!flag)v.push_back(vx[i]);
if (k<sy)v.push_back(vy[k++]);
}
while (k<sy)v.push_back(vy[k++]);
return v;
}
vi solve(int l,int r){
if (l==r)return vi{l};
int mid=(l+r>>1);
return merge(r-l+1,solve(l,mid),solve(mid+1,r));
}
vi answer(int n){
vi v=solve(0,n-1);
ans.resize(n);
for(int i=0;i<n;i++)ans[v[i]]=i;
return ans;
}