洛谷P3391 【模板】文艺平衡树(Splay)(FHQ Treap)

时间:2024-12-12 17:06:26

题目背景

这是一道经典的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

FHQ无敌,

解决区间问题的时候按照$r$分成两个

再按照$l$分成两个

那么我们就得到了需要翻转的区间

然后愉快的打标记就好啦

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
#define ls T[now].ch[0]
#define rs T[now].ch[1]
const int MAXN=1e6+;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=nc();}
while(c>=''&&c<=''){x=x*+c-'',c=nc();}
return x*f;
}
struct node
{
int ch[],val,siz,pri,mark;
}T[MAXN];
int tot=;
int x,y,z,root=,n,m;
int newnode(int v)
{
T[++tot].siz=;
T[tot].val=v;
T[tot].pri=rand();
return tot;
}
void update(int now)
{
T[now].siz=T[ls].siz+T[rs].siz+;
}
int Build(int l,int r)
{
if(l>r) return ;
int mid=(l+r)>>;
int now=newnode(mid-);
ls=Build(l,mid-);
rs=Build(mid+,r);
update(now);
return now;
}
void pushdown(int now)
{
if(T[now].mark&&now)
{
swap(ls,rs);
if(ls) T[ls].mark^=;
if(rs) T[rs].mark^=;
T[now].mark=;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) {x=y=;return ;}
pushdown(now);
if(T[ls].siz<k)
x=now,split(rs,k-T[ls].siz-,rs,y);
else
y=now,split(ls,k,x,ls);
update(now);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
pushdown(x);pushdown(y);
if(T[x].pri<T[y].pri)
{
T[x].ch[]=merge(T[x].ch[],y);
update(x);
return x;
}
else
{
T[y].ch[]=merge(x,T[y].ch[]);
update(y);
return y;
}
}
void dfs(int now)
{
pushdown(now);
if(T[now].ch[]) dfs(T[now].ch[]);
if(T[now].val>=&&T[now].val<=n) printf("%d ",T[now].val);
if(T[now].ch[]) dfs(T[now].ch[]);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
//srand((unsigned)time(NULL));
n=read(),m=read();
root=Build(,n+);
while(m--)
{
int l=read(),r=read();
int a,b,c,d;
split(root,r+,a,b);
split(a,l,c,d);
T[d].mark^=;
root=merge( merge(c,d) ,b );
}
dfs(root);
return ;
}