考虑归并排序，难点在于怎样合并两个有序序列。
我们假设要合并两个有序序列 \(A,B\)，不妨假设 \(|A|>|B|\)，考虑以下过程：
- 将 \(|A|\) 中的元素按下标奇偶性分成两个序列 \(A_0,A_1\)。
- 递归合并 \(A_0\) 与 \(B\)。
- 将 \(A_1\) 中的元素插入 \(A_0\) 与 \(B\) 得到的有序序列中，由于在 \(A\) 中我们可以知道 \(A_1\) 中每个元素位于哪两个相邻 \(A_0\) 的元素之前，所以这实际上相当于 \(O(|A_0|+B)\) 次比较操作。
- 用莫队处理这 \(O(|A_0|+B)\) 次比较操作。
考虑这样做的复杂度，设 \(T(x,y)\) 表示将长度为 \(x,y\) 的有序序列合并的复杂度，那么显然有 \(T(x,y)=T(\dfrac{x}{2},y)+(x+y)\sqrt{x+y}\)，由于我们假设 \(x>y\)，故每次分治下去的时候新序列长度至多是原来的 \(\dfrac{2}{3}\)，由 Master-Theorem 可知总移动次数也是 \(O(n\sqrt{n})\)。
const int MAXN=1.5e5;
struct qry{int l,r,rv,id;}q[MAXN+5];
int qn,B,P=0,Q=0,ls[MAXN+5];
bool CMP(qry x,qry y){
if(x.l/B!=y.l/B)return (x.l/B)<(y.l/B);
else return ((x.l/B)&1)?(x.r>y.r):(x.r<y.r);
}
vector<int>mrg(vector<int>x,vector<int>y,int l,int r){
if(x.size()<y.size())swap(x,y);
if(y.empty())return x;
vector<int>v0,v1,v2,pos,res;
for(int i=0;i<x.size();i++){
if(i%2==0)v0.pb(x[i]);
else v1.pb(x[i]);
}v2=mrg(v1,y,l,r);qn=0;
for(int i=0,j=0;i<v1.size();i++){
while(v2[j]!=v1[i])++j;
pos.pb(j);
}pos.pb(v2.size());
for(int i=0;i<v2.size();i++)ls[i]=0;
for(int i=0;i<v0.size();i++){
int L=i?(pos[i-1]+1):0,R=pos[i]-1;
for(int j=L;j<=R;j++)q[++qn]={v2[j]-l,v0[i]-l,0,j};
if(q[qn].l>q[qn].r)swap(q[qn].l,q[qn].r),q[qn].rv^=1;
}B=(int)(r-l+1)/sqrt(qn);sort(q+1,q+qn+1,CMP);
for(int i=1;i<=qn;i++){
while(P<q[i].l+l)inc_p(),++P;
while(P>q[i].l+l)dec_p(),--P;
while(Q<q[i].r+l)inc_q(),++Q;
while(Q>q[i].r+l)dec_q(),--Q;
ls[q[i].id]=cmp()^q[i].rv;
}
int cur=0;
for(int i=0;i<v0.size();i++){
while(cur<=(i?pos[i-1]:-1))res.pb(v2[cur++]);
while(ls[cur]&&cur<pos[i])res.pb(v2[cur++]);
res.pb(v0[i]);
}
while(cur<v2.size())res.pb(v2[cur++]);
return res;
}
vector<int>solve(int l,int r){
// cerr<<"solve "<<l<<" "<<r<<endl;
if(l==r){vector<int>tmp;tmp.pb(l);return tmp;}int mid=l+r>>1;
return mrg(solve(l,mid),solve(mid+1,r),l,r);
}
vector<int>answer(int n){
vector<int>A=solve(0,n-1),res(n);
// for(int i=0;i<n;i++)printf("%d ",A[i]);printf("\n");
for(int i=0;i<n;i++)res[A[i]]=i;
return res;
}
//g++ c.cpp grader.cpp -o c.exe -O2 -std=c++11
/*
8
7 0 3 2 1 5 4 6
*/