正题

题目链接:https://www.luogu.com.cn/problem/U136336?contestId=36038

题目大意

第 i i i次找到第 i i i大的数字位置 x i x_i xi​并且翻转 [ i , x i ] [i,x_i] [i,xi​]，求输出序列 x x x

解题思路

记录一下每个排名在 S p l a y Splay Splay中的位置，然后暴力翻转即可。

c o d e code code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,root,t[N][2],val[N],p[N],siz[N],fa[N],r[N]; bool Direct(int x) {return t[fa[x]][1]==x;} void Connect(int x,int y,int dir) {t[x][dir]=y;fa[y]=x;return;} void PushUp(int x) {siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;} void rev(int x){ 	swap(t[x][0],t[x][1]); 	r[x]^=1;return; } void PushDown(int x){ 	if(!r[x])return; 	rev(t[x][0]);rev(t[x][1]); 	r[x]=0;return; } void Rotate(int x){ 	PushDown(fa[x]);PushDown(x); 	int y=fa[x],z=fa[y]; 	int xs=Direct(x),ys=Direct(y); 	Connect(y,t[x][xs^1],xs);  	Connect(x,y,xs^1); 	Connect(z,x,ys); 	PushUp(y);PushUp(x); 	return; } void Downdata(int x){ 	if(!x)return; 	Downdata(fa[x]); 	PushDown(x); 	return; } void Splay(int x,int z){ 	Downdata(x); 	while(fa[x]!=z){ 		int y=fa[x]; 		if(fa[y]==z)Rotate(x); 		else if(Direct(x)==Direct(y)) 			Rotate(y),Rotate(x); 		else Rotate(x),Rotate(x); 	} 	if(!z)root=x; 	return; }  int rk(int x){ 	Splay(x,0); 	return siz[t[x][0]]; } int find(int x,int k){ 	PushDown(x); 	if(k<=siz[t[x][0]])return find(t[x][0],k); 	if(siz[t[x][0]]+1==k)return x; 	return find(t[x][1],k-siz[t[x][0]]-1); } bool cmp(int x,int y){ 	if(val[x+1]==val[y+1])return x<y; 	return val[x+1]<val[y+1]; } void print(int x){ 	if(!x)return; 	print(t[x][0]); 	printf("%d ",val[x]); 	print(t[x][1]); } int main() { 	freopen("31.in","r",stdin); 	freopen("data.out","w",stdout); 	scanf("%d",&n);siz[1]=1; 	for(int i=2;i<=n+1;i++){ 		scanf("%d",&val[i]); 		t[i][0]=i-1;fa[i-1]=i; 		p[i-1]=i-1;PushUp(i); 	} 	sort(p+1,p+1+n,cmp); 	t[n+2][0]=n+1;fa[n+1]=n+2; 	PushUp(n+2);root=n+2; 	for(int i=1;i<=n;i++){ 		int w=rk(p[i]+1);  		printf("%d ",w); //		print(root);putchar('n'); 		int x=find(root,i),y=find(root,w+2); 		Splay(x,0); 		Splay(y,x);  		rev(t[y][0]); //		print(root);putchar('n'); 	} 	return 0; } 

c/c++开发分享[2020.10.25NOIP模拟赛]序列【Splay】地址：https://blog.csdn.net/Mr_wuyongcong/article/details/109276339