BZOJ 4552: [Tjoi2016&Heoi2016]排序

Description

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

1:(0,l,r)表示将区间[l,r]的数字升序排序

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

Input

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5，1 <= m <= 10^5

Output

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

Sample Input

6 3

1 6 2 5 3 4

0 1 4

1 3 6

0 2 4

Sample Output

Solution

这是一道良心的基础数据结构题。

我们二分a[k]的值，假设当前是mid，然后把大于mid的数字标为1，不大于mid的数字标为0。然后对所有操作做完以后检查一下a[k]位置上是0还是1。

因为只有两种值，所以操作还是不难做的。只要用一个线段树，支持区间求和、区间赋值即可。这样要排序一个区间时只要查询一下里面有几个1和几个0，然后把前半段赋值为0，后半段赋值为1即可（降序的话就是反过来）。

复杂度是\(O(m\log ^2 n)\)的。

这题用其他玄学做法或者用更加厉害的平衡树做法也是有可能AC的。

jcvb大神的题解，感觉这道题真的很棒啊！这种做法还是第一次遇到。。。貌似是Bestcoder的原题。。。（好好打Bestcoder啦~）

Code

 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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int mid, Q, n, m;
int laz[400005], sum[400005], l[400005], r[400005];
int A[100005], B[100005], L[100005], R[100005];
void add(int now, int val) {
    laz[now] = val;
    sum[now] = (r[now]-l[now]+1)*val;
}
void pd(int now) {
    if (laz[now] != -1) {
        add(now << 1, laz[now]);
        add(now << 1 | 1, laz[now]);
        laz[now] = -1;
    }
}
void pu(int now) {
    sum[now] = sum[now << 1] + sum[now << 1 | 1];
}
void build(int now, int ll, int rr) {
    l[now] = ll; r[now] = rr; laz[now] = -1;
    if (ll == rr) {
        sum[now] = (A[ll] >= mid);
        return;
    }
    int mid = (ll + rr) >> 1;
    build(now << 1, ll, mid);
    build(now << 1 | 1, mid + 1, rr);
    pu(now);
}
int query(int now, int ll, int rr) {
    if (ll <= l[now] && r[now] <= rr)
        return sum[now];
    pd(now);
    int mid = (l[now] + r[now]) >> 1, ret = 0;
    if (ll <= mid) ret += query(now << 1, ll, rr);
    if (rr > mid) ret += query(now << 1 | 1, ll, rr);
    return ret;
}
void change(int now, int ll, int rr, int val) {
    if (ll <= l[now] && r[now] <= rr) {
        add(now, val);
        return;
    }
    pd(now);
    int mid = (l[now] + r[now]) >> 1;
    if (ll <= mid) change(now << 1, ll, rr, val);
    if (rr > mid) change(now << 1 | 1, ll, rr, val);
    pu(now);
}
bool check() {
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int s = query(1, L[i], R[i]);
        if (B[i]) {
            change(1, L[i], L[i] + s - 1, 1);
            change(1, L[i] + s, R[i], 0);
        } else {
            s = R[i] - L[i] + 1 - s;
            change(1, L[i], L[i] + s - 1, 0);
            change(1, L[i] + s, R[i], 1);
        }
    }
    return query(1, Q, Q);
}
int main() {
    n = getint(); m = getint();
    for (int i = 1; i <= n; ++i)
        A[i] = getint();
    for (int i = 1; i <= m; ++i) {
        B[i] = getint();
        L[i] = getint();
        R[i] = getint();
    }
    Q = getint();
    int l = 1, r = n;
    while (l < r) {
        mid = (l + r + 1) >> 1;
        if (check()) l = mid;
        else r = mid - 1;
    }
    printf("%d", r);
    return 0;
}