rt，自己yy了一种，边上的块暴力分裂，然后暴力插入分块中，如果边上的块小于 $len$ 就合并到相邻的块中，区间 $\text{split}$ 有一点毒瘤，不知道写对了没有（尤其是复杂度有没有假）

下面是P3165的代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<algorithm>

using namespace std;

typedef long long ll;

namespace mstd{

	//change it if ll

	inline void qread(int &x)
	{
		int f=1; x=0; static char c=getchar();
		while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
		while(isdigit(c)) x=x*10+c-'0',c=getchar();
		x*=f; return ;
	}

}

const int maxn=100030;
const int maxm=4030;

int vis[maxm][maxm];
int a[maxn],len,tmp[maxn],tot;
int n,m,b[maxn],sz[maxn],bl[maxn];
int mtot=0;

bitset <maxn> bt[maxm];

struct block{
	int stinv,edinv,*f,tob,tov,swaptag;
}c[maxn],mtp[maxn];

inline void m_intreverse(int tov,int stinv,int edinv)
{
	int i,j;
	for(i=stinv,j=edinv;i<=edinv;i++,j--) tmp[i]=vis[tov][j];
	for(i=edinv,j=edinv;i>=stinv;i--,j--) vis[tov][i]=tmp[j];
	return ;
}

inline void m_blockreverse(int st,int ed)
{
	int i,j;
	for(i=st,j=ed;i<=ed;i++,j--) mtp[j]=c[i];
	for(i=ed,j=ed;i>=st;i--,j--) c[i]=mtp[j],c[i].swaptag^=1;
	return ;	
}

inline void m_blockfront(int st,int ed)
{
	int i;	for(i=st;i<=ed;i++) c[i]=c[i+1];
}

inline void m_blockback(int st,int ed)
{
	int i;	for(i=ed;i>=st;i--) c[i+1]=c[i];
}

inline void m_intback(int tov,int st,int ed,int k)
{
	int i; for(i=ed;i>=st;i--) vis[tov][i+k]=vis[tov][i]; 
}

inline int mpla(int x)
{
	for(int i=1;i<=tot;i++)  if(bt[c[i].tob][x]) return i; 
	return 0;
}

inline int mjtpla(int x,int pla)
{
	if(c[pla].swaptag) m_intreverse(c[pla].tov,c[pla].stinv,c[pla].edinv),c[pla].swaptag=0;
	for(int i=c[pla].stinv;i<=c[pla].edinv;i++) 
	if(vis[c[pla].tov][i]==x) return i-c[pla].stinv+1;
	return 0;
}

inline int ask_sz(int x)
{
	int ans=0,i;
	for(i=1;i<=x;i++) ans+=c[i].edinv-c[i].stinv+1;
	return ans;
}

inline void split(int pla,int x)
{
	if(c[pla].edinv+1==x) return ;
	int t1=len*3/2;
	int t2=len*3;
	int nextlen=c[pla+1].edinv-c[pla+1].stinv+1;
	int l1,l2,i,j;
	l1=x-c[pla].stinv;
	l2=c[pla].edinv-x+1;
	if(l2+nextlen<=t2&&l2<=t1&&pla+1<=tot) 
	{
		if(c[pla+1].swaptag) m_intreverse(c[pla+1].tov,c[pla+1].stinv,c[pla+1].edinv),c[pla+1].swaptag=0;
		m_intback(c[pla+1].tov,c[pla+1].stinv,c[pla+1].edinv,l2);
		for(j=1;j<=l2;j++)
		{
			vis[c[pla+1].tov][c[pla+1].stinv+j-1]=vis[c[pla].tov][c[pla].stinv+l1+j-1];
			bt[c[pla].tob][vis[c[pla].tov][c[pla].stinv+l1+j-1]]=0;
			bt[c[pla+1].tob][vis[c[pla].tov][c[pla].stinv+l1+j-1]]=1;
			vis[c[pla].tov][c[pla].stinv+l1+j-1]=0;
		}
		c[pla].edinv-=l2;
		c[pla+1].edinv+=l2;
	}
	else
	{
		m_blockback(pla,tot); 
		mtot++,tot++;
		c[pla+1].stinv=1;
		c[pla+1].edinv=l2;
		c[pla+1].f=vis[mtot];
		c[pla+1].tob=c[pla+1].tov=mtot;
		for(i=1;i<=l2;i++) vis[mtot][i]=vis[c[pla].tov][c[pla].stinv+l1+i-1],vis[c[pla].tov][c[pla].stinv+l1+i-1]=0;
		for(i=1;i<=l2;i++) bt[c[pla].tob][vis[mtot][i]]=0,bt[c[pla+1].tob][vis[mtot][i]]=1;
		c[pla].edinv-=l2;
	}
}

inline void era(int pla)
{
	m_intreverse(c[pla].tob,c[pla].stinv,c[pla].edinv);
	c[pla].swaptag=0;
	c[pla].stinv++;
	if(c[pla].stinv>c[pla].edinv) m_blockfront(1,tot),tot--;
}

int main()
{
//	freopen("sort.in","r",stdin);
//	freopen("sort.out","w",stdout);
	int i,j;
	mstd::qread(n);
	for(i=1;i<=n;i++) mstd::qread(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	memset(sz,-1,sizeof(sz));
	for(i=1;i<=n;i++) 
	{
		int targetpla=lower_bound(b+1,b+n+1,a[i])-b;
		sz[targetpla]++;
		a[i]=targetpla+sz[targetpla];
	} 
	len=sqrt(n);
	for(i=1;i<=n;i++) bl[i]=(i-1)/len+1;
	for(i=1;i<=bl[n];i++)
	{
		c[i].tob=i;
		c[i].tov=i;
		c[i].f=vis[i];
		c[i].stinv=1;
		c[i].edinv=(i*len>n?n%len:len);
		int cnt=0;
		for(j=(i-1)*len+1;j<=i*len;j++)
		{
			vis[i][++cnt]=a[j];
			bt[i][a[j]]=1;
		}
	}
	tot=bl[n];
	mtot=tot;
	for(i=1;i<=n;i++)
	{
		int mp=mpla(i);
		int mjt=mjtpla(i,mp);
		printf("%d ",ask_sz(mp-1)+mjt+(i-1));
		split(mp,c[mp].stinv+mjt);
		m_blockreverse(1,mp);
		era(1);
	}
}