没有权限号的同学可以到 BZOJ 3506 交一下……
同 OJ 1552
不管怎么翻转，如果我们只交换左右儿子的索引而不是信息，第 \(K\) 大的结点永远都是不变的。
所以我们可以先排一次序，并在按原序列插入时记录每个第 \(K\) 大的结点。
那么问题就转到如何求一个结点的名次。
我们从根结点到这个结点把翻转标记全部下传，然后依次加入左子树的结点数 + 1 并逐步跳到根结点。
然后区间翻转就是 FHQ Treap 一个简单的操作了……
代码： 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
132
133
134
135
136
137
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 1e5;
int n,a[N + 10],rk[N + 10],kth[N + 10];
struct rec
{
int id,val;
inline bool operator<(const rec &a) const
{
return val < a.val || (val == a.val && id < a.id);
}
} b[N + 10];
struct node
{
int val,rnd,sz;
int rev;
int lson,rson,fa;
} tree[N + 10];
inline int new_node(int v)
{
static int tot = 0;
tree[++tot].val = v;
tree[tot].rnd = rand();
tree[tot].sz = 1;
return tot;
}
inline void up(int p)
{
tree[p].sz = tree[ls(p)].sz + 1 + tree[rs(p)].sz;
if(ls(p))
tree[ls(p)].fa = p;
if(rs(p))
tree[rs(p)].fa = p;
}
inline void down(int p)
{
if(tree[p].rev)
{
swap(ls(p),rs(p));
if(ls(p))
tree[ls(p)].rev ^= 1;
if(rs(p))
tree[rs(p)].rev ^= 1;
tree[p].rev = 0;
}
}
inline void down_from_top(int p)
{
if(tree[p].fa)
down_from_top(tree[p].fa);
down(p);
}
void split(int p,int k,int &x,int &y)
{
if(!p)
{
x = y = 0;
return ;
}
down(p);
if(tree[ls(p)].sz < k)
x = p,split(rs(p),k - tree[ls(p)].sz - 1,rs(p),y);
else
y = p,split(ls(p),k,x,ls(p));
up(p);
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
down(x),down(y);
if(tree[x].rnd < tree[y].rnd)
{
rs(x) = merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y) = merge(x,ls(y));
up(y);
return y;
}
}
int get_rank(int p)
{
down_from_top(p);
int ret = tree[ls(p)].sz + 1;
while(tree[p].fa)
{
if(rs(tree[p].fa) == p)
ret += tree[ls(tree[p].fa)].sz + 1;
p = tree[p].fa;
}
return ret;
}
int p,x,y,z,t;
int main()
{
read(n);
for(register int i = 1;i <= n;++i)
read(a[i]),b[i] = (rec){i,a[i]};
sort(b + 1,b + n + 1);
for(register int i = 1;i <= n;++i)
rk[b[i].id] = i;
for(register int i = 1;i <= n;++i)
p = merge(p,kth[rk[i]] = new_node(a[i]));
for(register int i = 1;i <= n;++i)
{
t = get_rank(kth[i]);
printf("%d ",t);
split(p,t,x,z);
split(x,i - 1,x,y);
tree[y].rev ^= 1;
p = merge(merge(x,y),z);
}
}