「CQOI2014」排序机械臂-Splay

维护一个序列,第$i$次操作时寻找第i小的数的所在位置$Pi$,并将$(P_{i-1},P_{i}]$的区间翻转。

如果有相同的数,必须保证排序后它们的相对位置关系与初始时相同。

链接

Luogu P3165

题解

这道题的大意是区间寻找,区间翻转,所以我们可以用Splay来做,维护一个$size$值和区间翻转的$rev$标记。虽然我前几天还说再也不用Splay了(逃。

注意到每次操作都会使第$i$个数排序完成,所以我们每次的$P_{i}$事实上就是数组下标的$i-1$。


对于区间的寻找,我们注意到可以在开始的时候就记录下来第$i$小的数的位置,也就是把他们的指针存在一个数组里面。

看不到的话假装有图吧

然后在查询的时候,先把第$i-1$大的节点splay到根;找到第$i$小的数对应的节点指针,寻找其在排序二叉树中的后继节点(图中红色节点),然后把后继splay到根的右子树。

但注意在实际查找中,因为寻找后继会破坏根结点,所以要先找到后继节点,然后再完成上述操作。

然后关于位置,我们可以看出,根节点左边(包括根结点),也就是图中的绿色部分应当有$i-1$个数,而其他在$i$左边(包括$i$)的数应该就是图中的蓝色部分,所以只要将蓝色部分的$size$加上一个$i-1$就是每一次操作的结果


翻转就是常规的区间翻转,打标记pushdown什么的。


为了方便满足一些它的要求,我还事先做了离散化的处理。(其实并没有什么用

另外还有就是我写的时候还因为少push_down了几次被坑了一下。不过最后一次过评测还是蛮开心的。

代码

点击切换显示状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <algorithm>
using namespace std;

struct wupin{
int id,h;
}w[100100];

struct splay_t{
struct node_t{
int val,size;
bool rev;
node_t *p,*son[2],**root,**null;
inline bool get_p(){return p->son[1] == this;}
inline void init(node_t **root,node_t **null){this->null = null,this->root = root;}
inline int lsize(){return son[0]->size;} inline int rsize(){return son[1]->size;}
inline void update(){size = lsize()+rsize()+1;}
inline void link(node_t *dst,int tmp){
dst->son[tmp] = this;
this->p = dst;
}
inline void push_down(){
if(this == *null) return;
if(rev){
swap(son[0],son[1]);
son[0]->rev^=1,son[1]->rev^=1;
rev = 0;
}
}
inline void rotate(){
p->push_down(),push_down();
node_t *rp = p;bool re = get_p();
link(rp->p,rp->get_p());
son[1-re]->link(rp,re);
rp->link(this,1-re);
rp->update(),update();
if(p == *null) *root = this;
}
inline node_t* splay(node_t *tar = NULL){
if(tar == NULL) tar = *null;
p->push_down(),push_down();
while(p!=tar){
if(p->p == tar)
rotate();
else if(p->get_p() == get_p())
p->rotate(),rotate();
else
rotate(),rotate();
}
return this;
}
inline node_t *upper(){
splay();
node_t *r = son[1];
while(true){
r->push_down();
if(r->son[0] == *null) break;
r = r->son[0];
}
return r;
}
};
int cnt;
node_t pool[110000],*to[110000],*null,*root;
splay_t(){
cnt = 0;
null = newnode();
null->size = 0;
}
node_t *newnode(int val = 0){
node_t *r = &pool[cnt++];
r->init(&root,&null);
r->val = val,r->size = 1,r->rev = 0;
r->p = r->son[0] = r->son[1] = null;
return r;
}
node_t* build(wupin *a,int l,int r){
if(l>r) return null;
int mid = (l+r)>>1;
node_t *ret = newnode(a[mid].h);
to[a[mid].h] = ret;
build(a,l,mid-1)->link(ret,0);
build(a,mid+1,r)->link(ret,1);
ret->update();
return ret;
}
};

splay_t s;

int n;

bool cmp1(wupin a,wupin b){return a.id<b.id;}
bool cmp2(wupin a,wupin b){
if(a.h!=b.h) return a.h<b.h;
else return a.id<b.id;
}

void find(){
for(int i = 1;i<=n;i++){
//找到应操作节点的后继
splay_t::node_t *rbound = s.to[i]->upper();
//把前面归位好的最后一个节点旋到根节点
s.to[i-1]->splay();
//把后继旋转到根节点的右儿子
rbound->splay(s.to[i-1]);
//打印位置
printf("%d ",i + rbound->lsize()-1);
//添加lazy标记
rbound->son[0]->rev^=1;
}
}

int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&w[i].h);
w[i].id = i;
}
//预处理
sort(w+1,w+n+1,cmp2);
for(int i = 1;i<=n;i++)
w[i].h = i;
sort(w+1,w+n+1,cmp1);
w[0].h = 0;
w[n+1].h = n+1;
//正式操作
s.root = s.build(w,0,n+1);
find();
return 0;
}