fhq 全 tle 求助（和第一篇题解一样）

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#include<unordered_map>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}

template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MOD(1e9+7);
template<typename T>
inline T add(T x){return x;}
template<typename T,typename... types>
inline T add(T x,types... y){T z=add<T>(y...);return x+z>=MOD?x+z-MOD:x+z;}
template<typename T>
inline T mul(T x){return x;}
template<typename T,typename... types>
inline T mul(T x,types... y){return (ll)x*mul<T>(y...)%MOD;}
inline int sub(int x,int y){return add(x-y,MOD);}

const int MAXN(1e5+10);

int n,a[MAXN];

struct FHQ_Treap
{
	int val[MAXN],minn[MAXN],siz[MAXN],lc[MAXN],rc[MAXN],rnd[MAXN];
	bool tag[MAXN];
	int rt,tot;
	
	inline int New(int v)
	{
		int u=++tot;
		val[u]=v,minn[u]=v;
		siz[u]=1,rnd[u]=rand();
		return u;
	}
	
	inline void push_up(int u)
	{
		siz[u]=siz[lc[u]]+siz[rc[u]]+1;
		minn[u]=val[u];
		if(lc[u]) minn[u]=Min(minn[u],minn[lc[u]]);
		if(rc[u]) minn[u]=Min(minn[u],minn[rc[u]]);
		return;
	}
	
	inline void lazy_tag(int u)
	{
		if(!u) return;
		Swap(lc[u],rc[u]);
		tag[u]^=1;
		return;
	}
	
	inline void push_down(int u)
	{
		if(tag[u])
		{
			Swap(lc[u],rc[u]);
			if(lc[u]) tag[lc[u]]^=1;
			if(rc[u]) tag[rc[u]]^=1;
			tag[u]=false;
		}
		return;
	}
	
	inline void split(int u,int k,int&x,int&y)
	{
		if(!u) x=y=0;
		else
		{
			push_down(u);
			if(k>siz[lc[u]]) x=u,split(rc[u],k-siz[lc[u]]-1,rc[u],y);
			else y=u,split(lc[u],k,x,lc[u]);
			push_up(u);
		}
		return;
	}
	
	inline int unite(int x,int y)
	{
		if(!x||!y) return x+y;
		if(rnd[x]<rnd[y])
		{
			push_down(x);
			rc[x]=unite(rc[x],y);
			push_up(x);
			return x;
		}
		else
		{
			push_down(y);
			lc[y]=unite(x,lc[y]);
			push_up(y);
			return y;
		}
	}
	
	inline void Reverse(int l,int r)
	{
		int x,y,z;
		split(rt,r,x,y);
		split(x,l-1,x,z);
		tag[z]^=1;
		rt=unite(unite(x,z),y);
		return;
	}
	
	inline void Insert(int v)
	{
		rt=unite(rt,New(v));
		return;
	}
	
	inline int query(int l,int x)
	{
		int v,u;
		split(rt,l-1,v,u);
		int res=0,uu=u;
		while(true)
		{
			push_down(u);
			if(lc[u]&&minn[lc[u]]==x) u=lc[u];
			else if(val[u]!=x)
			{
				res=res+siz[lc[u]]+1;
				u=rc[u];
			}
			else
			{
				res+=siz[lc[u]];
				break;
			}
		}
		rt=unite(v,uu);
		return res+1;
	}
	
	inline int qp(int p)
	{
		int x,y,z;
		split(rt,p-1,x,y);
		split(y,1,y,z);
		int res=val[y];
		rt=unite(x,unite(y,z));
		return res;
	}
};
FHQ_Treap fhq;

int b[MAXN],tot;

int main()
{
	srand(time(0));
	n=read();
	rep(i,1,n)
	{
		a[i]=read();
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	rep(i,1,n) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	rep(i,1,n) fhq.Insert(a[i]);
	rep(i,1,n)
	{
		int k=fhq.query(i,i);
		printf("%d ",i+k-1);
		fhq.Reverse(i,i+k-1);
	}
	return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/