欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[2020.10.25NOIP模拟赛]序列【Splay】

程序员文章站 2022-06-25 16:10:58
正题题目链接:https://www.luogu.com.cn/problem/U136336?contestId=36038题目大意第iii次找到第iii大的数字位置xix_ixi​并且翻转[i,xi][i,x_i][i,xi​],求输出序列xxx解题思路记录一下每个排名在SplaySplaySplay中的位置,然后暴力翻转即可。codecodecode#include#include#include

正题

题目链接: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;
}

本文地址:https://blog.csdn.net/Mr_wuyongcong/article/details/109276339

相关标签: 数据结构 Splay