题意

原版题面

一个 1~n 的排列经过 m 次排序,问第 q 个位置上的数是什么。

作者の屁话

多年颓废 / 文化课之后 A 掉的第一道题。

这道题刷新了我对二分的认知.原来二分不只是一种在序列中找东西、求最大值最小的 sb 算法啊看来我太菜了

做法

考虑暴力模拟?

我们知道,通过“比较、交换”实现的排序复杂度下限为 $O(n \log n)$,那么对应到本题来,就是 $O(mn \log n)$,只要让你对整个区间升序一次、降序一次……这样循环下去就可以卡满。

不思考一个暴力能得多少分,先想办法把它卡满,不愧是我

可以得到 30% 的分,但是我是 PM 人但是这对于省选 Day1 T2 来说还是低了一点。


下面思考这个暴力差在哪里。

我们使用了“比较、交换”的排序,这就是它差的地方。当然这里不是要换成计数排序

那么,如果我们把问题转化为:如何对一个只有 0, 1 的序列排序,显然就有了更优秀的方法。

我们只需要统计目标区间内 1 的个数(记为 k),然后对这个区间进行修改,分两种情况:

  • 升序:将前 k 个(即$[l,l+k)$)改为 1,其余改成0;
  • 降序:将后 k 个(即$(r-k,r]$)改为1,其余改为0。

然后排序就完成了。

现在要将原序列转化为一个 01 序列,方法如下:

二分答案 x,将原序列中大于等于 x 的赋为 1,其余为 0。

操作完后,如果第 q 个位置是 1,那么$l=mid+1$,否则$r=mid-1$。

这里我们需要一种可以快速维护区间和、区间修改的数据结构,那就是线段树。

时间复杂度为$n\log^2n$

代码

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
#include<bits/stdc++.h>
#define lc (u << 1)
#define rc (u << 1 | 1)
#define lson lc, l, mid
#define rson rc, mid + 1, r
using namespace std;

inline int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N = 1e5 + 5;
int n, m, A[N], B[N], q;
struct Change { int opt, l, r; } c[N];
struct Segment { int sum, tag, l, r; } t[N << 2];

inline void pushup(int u) { t[u].sum = t[lc].sum + t[rc].sum; }

inline void build(int u, int l, int r) {
t[u].l = l, t[u].r = r;
if(l == r) { t[u].tag = -1, t[u].sum = B[l]; return; }
int mid = (l + r) >> 1;
build(lson), build(rson);
pushup(u); t[u].tag = -1;
}

inline void pushdown(int u) {
if(t[u].tag == -1) return;
t[lc].tag = t[u].tag;
t[rc].tag = t[u].tag;
t[lc].sum = t[u].tag * (t[lc].r - t[lc].l + 1);
t[rc].sum = t[u].tag * (t[rc].r - t[rc].l + 1);
t[u].tag = -1;
}

inline int query(int u, int l, int r, int a, int b) {
if(a == l && r == b) return t[u].sum;
pushdown(u);
int mid = (l + r) >> 1;
if(b <= mid) return query(lson, a, b);
else if(a > mid) return query(rson, a, b);
else return query(lson, a, mid) + query(rson, mid + 1, b);
}

inline void update(int u, int l, int r, int a, int b, int v) {
if(a == l && r == b) {
t[u].sum = v * (r - l + 1);
t[u].tag = v;
return;
}
pushdown(u);
int mid = (l + r) >> 1;
if(b <= mid) update(lson, a, b, v);
else if(a > mid) update(rson, a, b, v);
else update(lson, a, mid, v), update(rson, mid + 1, b, v);
pushup(u);
}

inline bool chk(int x) {
for(register int i = 1; i <= n; i++) B[i] = (A[i] >= x);
build(1, 1, n);
for(register int i = 1; i <= m; i++) {
int l = c[i].l, r = c[i].r;
int cnt = query(1, 1, n, l, r);
if(cnt == 0) continue;
update(1, 1, n, l, r, 0);
if(c[i].opt) update(1, 1, n, l, l + cnt - 1, 1);
else update(1, 1, n, r - cnt + 1, r, 1);
}
int res = query(1, 1, n, q, q);
return res;
}

int main() {
n = get(), m = get();
for(register int i = 1; i <= n; i++) A[i] = get();
for(register int i = 1; i <= m; i++) c[i].opt = get(), c[i].l = get(), c[i].r = get();
q = get();
int l = 1, r = n, ans;
while(l <= r) {
int mid = (l + r) >> 1;
if(chk(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans << endl;
return 0;
}

彩蛋

由于这道题是在 linux 系统下写的且作者暂时不会使用 gdb(悲),所以这是原代码截图:

丢人代码