P3391 【模板】文艺平衡树(Splay)

题目背景

这是一道经典的Splay模板题——文艺平衡树。

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

输入输出格式

输入格式:

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2, \cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次数

接下来m行每行两个数 [l,r][l,r] 数据保证 1 \leq l \leq r \leq n1≤l≤r≤n

输出格式:

输出一行n个数字,表示原始序列经过m次变换后的结果

输入输出样例

输入样例#1:

5 3
1 3
1 3
1 4

输出样例#1:

4 3 2 1 5

说明

n, m \leq 100000n,m≤100000

splay的模板题。

splay在解决区间问题的时候是先把l旋转到根节点,再把r旋转到根节点的右孩子,

然后给根节点的右孩子的左孩子打上标记。

递归修改即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=100001;
inline void read(int &n)
{	char c='+';int x=0;bool flag=0;
	while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
	while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
	n=flag==1?-x:x;
}
struct node
{
	int fa,ch[2];// 左右孩子 
	int size;//大小 
	bool rev; // 是否需要旋转
}tree[MAXN];
int root=0;
int n,m;
inline void update(int x)
{tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;}
inline void connect(int x,int f,bool how)
{tree[x].fa=f;	tree[tree[x].fa].ch[how]=x;}
inline void pushdown(int x)
{
	if(tree[x].rev)
		swap(tree[x].ch[0],tree[x].ch[1]),
		tree[tree[x].ch[0]].rev^=1,tree[tree[x].ch[1]].rev^=1,tree[x].rev=0;
}
int build(int l,int r)
{
	if(l>r)	return 0;
	int mid=(l+r)>>1;
	connect(build(l,mid-1),mid,0);	connect(build(mid+1,r),mid,1);
	tree[mid].rev=0;
	update(mid);	return mid;
}
inline bool get(int x)
{
	return tree[tree[x].fa].ch[1]==x;
}
inline int find(int x)
{
	--x;int now=root;pushdown(now);
	while(x!=tree[tree[now].ch[0]].size)
	{
		if(tree[tree[now].ch[0]].size<x)	x-=tree[tree[now].ch[0]].size+1,	now=tree[now].ch[1];
		else	now=tree[now].ch[0];
		pushdown(now);
	}
	return now;
}
inline void rotate(int x)
{
	int f=tree[x].fa;bool d=get(x);
	if(f==root)	root=x,tree[x].fa=0;
	else	connect(x,tree[f].fa,get(f));
	connect(tree[x].ch[!d],f,d);
	connect(f,x,!d);
	update(f);
}
inline void splay(int x,int r)
{
	if(x==r)	return ;
	for(int f;(f=tree[x].fa)!=r;)
	{
		if(tree[f].fa==r){rotate(x);break;}	
		rotate( (get(x)==get(f))?f:x );	rotate(x);
	}
	update(x);
}
inline void out(int x)
{
	if(!x)	return ;
	pushdown(x);
	out(tree[x].ch[0]);
	if(x!=1&&x!=n+2)	printf("%d ",x-1);
	out(tree[x].ch[1]);
}
int main()
{
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
	read(n);read(m);
	root=build(1,n+2);
	int l,r,tmp;
	for(int i=1;i<=m;i++)
	{
		read(l);read(r);
		splay(find(l),0);
		tmp=find(r+2);	splay(tmp,root);
		tree[tree[tmp].ch[0]].rev^=1;
	}
	out(root);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是业余自学C/C++的

矩阵

1405
来自专栏前端吧啦吧啦

数据结构(二)之算法基础

1294
来自专栏数据结构与算法

洛谷P1067 多项式输出(模拟)

题目描述 一元 n 次多项式可用如下的表达式表示: ? 其中,aixi称为 i 次项,ai 称为 i 次项的系数。给出一个一元多项式各项的次数和系数,请按照如下...

2985
来自专栏chenjx85的技术专栏

leetcode-884-两句话中的不常见单词

给定两个句子 A 和 B 。 (句子是一串由空格分隔的单词。每个单词仅由小写字母组成。)

1643
来自专栏前端儿

三角形面积

输入每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输...

1482
来自专栏程序生活

连续子数组的最大和

题目1 连续子数组的最大和 描述: 输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度...

2995
来自专栏决胜机器学习

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(六)——数组的相乘、广义表 (原创内容,转载请注明来源,谢谢) 本文接PHP数据结构(五)的内容。 4.2 行逻辑链接的顺序表 行逻辑链接的顺...

4519
来自专栏菜鸟程序员

【Java】随机数详解

2244
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1852
来自专栏人工智能头条

70个NumPy练习:在Python下一举搞定机器学习矩阵运算

2822

扫码关注云+社区

领取腾讯云代金券