「HEOI2016/TJOI2016」排序-线段树

在 $2016$ 年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个 $1$ 到 $n$ 的全排列,现在对这个全排列序列进行 $m$ 次局部排序,排序分为两种:

  • $(0,l,r)$表示将区间 $[l,r]$ 的数字升序排序
  • $(1,l,r)$表示将区间 $[l,r]$ 的数字降序排序
    最后询问第 $q$ 位置上的数字。

链接

Luogu P2824

题解

好题啊。

因为这个问题只有一个询问,所以我们考虑二分答案。

假设当前的考虑要判定的答案是 $mid$ 与 $p$ 位置上数的大小关系,通过 $O(\log n)$ 次二分,就可以求出最后这个位置上的数字。

所以问题转化为:求出 $p$ 位置上的数与 $k$ 的大小关系。我们关注到,如果我们只关心其位置上的数相对于某一个数的大小关系,那我们就可以将小于等于 $k$ 的数设置成 $0$ ,大于 $k$ 的数设置成 $1$,那么排序就比较容易了,只需要一个 $0/1$ 线段树,维护区间和,支持区间覆盖即可。每次我们查询到 $sum(l,r)$,然后根据这个 $sum$ 的值和排序的种类对区间进行覆盖,升序即为 $0…01…1$,降序则为 $1…10…0$。

最后查询 $q$ 这个位置上的值,如果是 $0$ ,就说明这个位置上的数小于等于 $k$ ,否则就是大于 $k$ 。

二分答案即可。

时间复杂度: $O(n \log^2 n)$


这题也有用可合并、分裂的线段树的做法,可以处理多组询问。

代码

点击切换显示状态
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
#include <cstdio>
using namespace std;

const int MAXN = 31000;

namespace SegTree{
#define lson (nown<<1)
#define rson (nown<<1|1)
#define mid ((l+r)>>1)
int sumn[MAXN<<2],lazy[MAXN<<2];// -1 -> no label
void add_label(int nown,int l,int r,int op){
lazy[nown] = op,sumn[nown] = (r-l+1)*op;
}
void push_down(int nown,int l,int r){
if(lazy[nown] != -1){
add_label(lson,l,mid,lazy[nown]);
add_label(rson,mid+1,r,lazy[nown]);
lazy[nown] = -1;
}
}
void push_up(int nown){
sumn[nown] = sumn[lson] + sumn[rson];
}
void build(int nown,int l,int r,int k,int *a){
lazy[nown] = -1;
if(l == r){
sumn[nown] = k < a[l];// 满足条件(<=)的 sumn 为 0
}
else{
build(lson,l,mid,k,a),build(rson,mid+1,r,k,a);
push_up(nown);
}
}
int query(int nown,int l,int r,int ql,int qr){
if(ql <= l && r <= qr){
return sumn[nown];
}
else{
push_down(nown,l,r);
int ans = 0;
if(ql <= mid)
ans += query(lson,l,mid,ql,qr);
if(qr >= mid+1)
ans += query(rson,mid+1,r,ql,qr);
return ans;
}
}
void update(int nown,int l,int r,int ql,int qr,int op){
if(ql <= l && r <= qr){
add_label(nown,l,r,op);
}
else{
push_down(nown,l,r);
if(ql <= mid)
update(lson,l,mid,ql,qr,op);
if(qr >= mid+1)
update(rson,mid+1,r,ql,qr,op);
push_up(nown);
}
}
void print(int nown,int l,int r){
printf("nown:%d l,r:%d %d sumn:%d lazy:%d\n",nown,l,r,sumn[nown],lazy[nown]);
if(l == r) return;
print(lson,l,mid);
print(rson,mid+1,r);
}
void sort(int n,int l,int r,int op){// op 为 0 正序 , op 为 1 逆序
int b = query(1,1,n,l,r),a = (r-l+1) - b;
//printf("a:%d b:%d\n",a,b);
if(op == 0){
if(a) update(1,1,n,l,l+a-1,0);
if(b) update(1,1,n,r-b+1,r,1);
}
else{
if(b) update(1,1,n,l,l+b-1,1);
if(a) update(1,1,n,r-a+1,r,0);
}
}
#undef lson
#undef rson
#undef mid
}

int n,m,q;
int a[MAXN];
int o[MAXN],l[MAXN],r[MAXN];
void init(){
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
scanf("%d",&a[i]);
for(int i = 1;i<=m;i++)
scanf("%d %d %d",&o[i],&l[i],&r[i]);
scanf("%d",&q);
}

bool check(int k){//检查 q 位置上的数是不是小于等于 k
SegTree::build(1,1,n,k,a);
for(int i = 1;i<=m;i++)
SegTree::sort(n,l[i],r[i],o[i]);
return SegTree::query(1,1,n,q,q) == 0;
}

void solve(){
int b = 1,e = n;
while(b!=e){
int mid = (b+e)>>1;
//printf("%d %d:%d\n",b,e,mid);
if(check(mid))
e = mid;
else
b = mid+1;
}
printf("%d\n",b);
}

int main(){
init();
solve();
return 0;
}