洛谷 P3391 文艺平衡树
2024-10-20 15:49:52
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
--by洛谷
http://daniu.luogu.org/problem/show?pid=3391
裸的平衡树反转；
方法是按序列位置为关键字排序；
反转（l,r）：
则将l-1置于根处，将r+1作为根的右儿子，这样，r+1的左子树就是需要反转的区间；
然后对r+1的左儿子，反转其左右儿子，并打上线段树一样的lazy标记，待以后反转她的子树；
一开始，企图把位置维护为关键字，然后排序；
这样，
若点A为父节点的左儿子，则key[A]=key[fa[A]]-size[rs[A]]-1;
若点A为父节点的右儿子，则key[A]=key[fa[A]]+size[ls[A]]+1;
然后查找直接按查询关键字的方法找，十分方便；
然而关键字是时时变化的，不好维护，
另一种方法是直接在初次建好树后就再也不考虑维护关键字的问题，
直接按第K大的方法搜索，（从某种意义上讲她早已不是一般意义上的查找树了）
怎么办，选哪种方法继续呢？
一个很好的方法是把两个都写出来，
反正差不多
多好啊，还能对拍，是吧
代码如下：
#include<cstdio>
using namespace std;
int n,m;
struct dt{
int cnt,size,key,lz;
int ch[],fa;
};
struct Splay{
int root,tot;
dt data[];
void in(){
root=tot=;
data[].fa=data[].cnt=data[].size=data[].key=;
}
void splay(int x,int end){
int fa,fafa;
for(fa=data[x].fa;(fa=data[x].fa)!=end;roll(x)){
fafa=data[fa].fa;
if(fafa!=end){
if((data[fafa].ch[]==fa)^(data[fa].ch[]==x))
roll(x);
else
roll(fa);
}
}
if(!end)
root=x;
}
void roll(int x){
int fa=data[x].fa,fafa=data[fa].fa;
int wh=data[fa].ch[]==x;
data[fa].ch[wh]=data[x].ch[wh^];data[data[x].ch[wh^]].fa=fa;
data[x].ch[wh^]=fa;data[fa].fa=x;
if(fafa)
data[fafa].ch[data[fafa].ch[]==fa]=x;
data[x].fa=fafa;
up(fa);up(x);
}
void up(int x){
data[x].size=data[data[x].ch[]].size+data[data[x].ch[]].size+;
}
void buil_splay(int l,int r,int&nu,int fa){
int mid=(l+r)>>;
nu=++tot;
data[nu].key=mid;
data[nu].fa=fa;
data[nu].cnt=data[nu].size=;
if(l==r)return;
if(l<mid)
buil_splay(l,mid-,data[nu].ch[],nu);
if(r>mid)
buil_splay(mid+,r,data[nu].ch[],nu);
data[nu].size=data[data[nu].ch[]].size+data[data[nu].ch[]].size+;
}
int find(int x){
int i=root;
while(!(data[data[i].ch[]].size<x&&x<=data[i].size-data[data[i].ch[]].size)){
if(data[i].lz){
change(data[i].ch[]);
change(data[i].ch[]);
data[i].lz=;
}
if(x<=data[data[i].ch[]].size)
i=data[i].ch[];
else{
x-=(data[i].size-data[data[i].ch[]].size);
i=data[i].ch[];
}
}
if(data[i].lz){
change(data[i].ch[]);
change(data[i].ch[]);
data[i].lz=;
}
return i;
}
void change(int x){
int fa=data[x].fa,i;
i=data[x].ch[];data[x].ch[]=data[x].ch[];data[x].ch[]=i;
data[x].lz^=;
}
void print(int now){
if(data[now].lz){
change(data[now].ch[]);
change(data[now].ch[]);
data[now].lz=;
}
if(data[now].ch[])
print(data[now].ch[]);
if(data[now].key!=&&data[now].key!=n+)
printf("%d ",data[now].key);
if(data[now].ch[])
print(data[now].ch[]);
}
};
Splay splay;
int main()
{
int i,j,k,l;
scanf("%d%d",&n,&m);
splay.buil_splay(,n+,splay.root,);
for(i=;i<=m;i++){
scanf("%d%d",&j,&k);
if(j==k)continue;
l=splay.find(j);
splay.splay(l,);
l=splay.find(k+);
splay.splay(l,splay.root);
splay.change(splay.data[splay.data[splay.root].ch[]].ch[]);
}
splay.print(splay.root);
}
#include<cstdio>
using namespace std;
int n,m;
struct dt{
int value,cnt,size,key,lz;
int ch[],fa;
};
struct Splay{
int root,tot;
dt data[];
void in(){
root=tot=;
data[].fa=data[].cnt=data[].size=data[].value=data[].key=;
}
void splay(int x,int end){
int fa,fafa;
for(fa=data[x].fa;(fa=data[x].fa)!=end;roll(x)){
fafa=data[fa].fa;
if(fafa!=end){
if((data[fafa].ch[]==fa)^(data[fa].ch[]==x))
roll(x);
else
roll(fa);
}
}
if(!end)
root=x;
}
void roll(int x){
int fa=data[x].fa,fafa=data[fa].fa;
int wh=data[fa].ch[]==x;
data[fa].ch[wh]=data[x].ch[wh^];data[data[x].ch[wh^]].fa=fa;
data[x].ch[wh^]=fa;data[fa].fa=x;
if(fafa)
data[fafa].ch[data[fafa].ch[]==fa]=x;
data[x].fa=fafa;
up(fa);up(x);
}
void up(int x){
data[x].size=data[data[x].ch[]].size+data[data[x].ch[]].size+;
}
void buil_splay(int l,int r,int&nu,int fa){
int mid=(l+r)>>;
nu=++tot;
data[nu].value=data[nu].key=mid;
data[nu].fa=fa;
data[nu].cnt=data[nu].size=;
if(l==r)return;
if(l<mid)
buil_splay(l,mid-,data[nu].ch[],nu);
if(r>mid)
buil_splay(mid+,r,data[nu].ch[],nu);
data[nu].size=data[data[nu].ch[]].size+data[data[nu].ch[]].size+;
}
int find(int x){
int i=root;
while(){
change(data[i].ch[]);
change(data[i].ch[]);
data[i].lz=;
if(data[i].value==x)
break;
i=data[i].ch[data[i].value<x];
}
return i;
}
void change(int x){
int fa=data[x].fa,i;
if(data[fa].lz){
i=data[x].ch[];data[x].ch[]=data[x].ch[];data[x].ch[]=i;
data[x].lz^=;
}
if(data[fa].ch[]==x)
data[x].value=data[fa].value-data[data[x].ch[]].size-;
else
data[x].value=data[fa].value+data[data[x].ch[]].size+;
}
void print(int now){
change(data[now].ch[]);
change(data[now].ch[]);
data[now].lz=;
if(data[now].ch[])
print(data[now].ch[]);
if(data[now].key!=&&data[now].key!=n+)
printf("%d ",data[now].key);
if(data[now].ch[])
print(data[now].ch[]);
}
};
Splay splay;
int main()
{
int i,j,k,l;
scanf("%d%d",&n,&m);
splay.buil_splay(,n+,splay.root,);
for(i=;i<=m;i++){
scanf("%d%d",&j,&k);
if(j==k)continue;
l=splay.find(j-);
splay.splay(l,);
l=splay.find(k+);
splay.splay(l,splay.root);
splay.data[splay.data[splay.root].ch[]].lz=;
splay.change(splay.data[splay.data[splay.root].ch[]].ch[]);
splay.data[splay.data[splay.root].ch[]].lz=;
}
splay.print(splay.root);
}
another_way
祝AC
最新文章
- Dell DRAC的重启方法
- Graphic geometry
- mac 隐藏、显示文件
- spring DI原理
- leetcode 155. Min Stack --------- java
- HTML ISO-8859-1 参考手册
- 时间紧迫，写一些 NavigationController 一次性返回2级界面甚至更多级的界面
- “ORA-12545: 因目标主机或对象不存在，连接失败”怎么办？
- 小程序使用wx.chooseAddress获取用户手机号码，微信chooseAddress接口获取用户收货信息
- mongodb 3.4 集群搭建：分片+副本集
- Golang 网络爬虫框架gocolly/colly 四
- SSM学习笔记
- 【Linux基础】history查看历史命令
- char类型的数值转换
- [学习笔记]CDQ分治和整体二分
- 注意字符串的strlen与sizeof的差别
- 解决Cydia出现红字提示“Sub-process/usr/bin/dpkg returned an error code(2)
- JS-随机div颜色
- Big Table中文翻译
- 亚马逊拟斥资15亿美元建航空货运中心 - Amazon to spend $1.49 bln on air cargo hub, fans talk of bigger ambitions - ReutersFebruary 1, 2017