01排序

Posted on Edited on In

题目大意：有一个数列 a[1..n]，它是 1~n 这 n 个正整数的一个排列。现在支持两种操作：0, l, r: 将 a[l..r]原地升序排序。1, l, r: 将 a[l..r]原地降序排序。操作完后，给定一个位置 q，输出 a[q]的值。

考虑暴力，显然就是对于每一次的操作都进行一边\(O(n\times logn)\)的排序，总复杂度：\(O(n^2\times logn)\)

这里就是瓶颈，我们可不可以给他优化成\(logn\)的时间复杂度呢

答案是可以的

再来考虑当我知道一个01序列里面1的个数之后，对一个01串进行排序，显然复杂度就是\(logn\)（线段树区间赋值）

由于这是一个排列，所以序列中每个数都不一样，所以我们来二分答案，二分最后p会变成哪一个数字

然后把大于等于mid的判定为1，小与的判定为0

然后对于每一个操作都是log的修改，最后查询q那个位置是否为1，总复杂度：\((n\times logn^2)\)

为什么可以二分？好多人的题解里面写的显然。。。我觉得一点也不显然

首先这个题目我们无法用最大最小值的定义来解释他，但是可以观察发现，这个值域是具有单调性的

比如说，我们二分出来的mid为1，显然当前所有数字都为1，也就意味着说，这个答案合理，我们应该往大于1的范围去找

就是l = mid，反之就是r = mid - 1

补：

来自一位dalao(Fighting_Peter)的讲解：答案具有单调性，不妨设现在二分答案是mid，那么进行01串转化后，如果答案最后大于mid那么该位置的数一定是1，如果最后答案小于mid该位置的数一定是0，答案范围是值域，我们现在要求最小的一个值满足在进行01串转化后所求位置的数是1。如果二分答案的值偏小那么该位置一定是1，如果二分答案的值偏大那么该位一定是0。根据上述不同即可一次次缩小范围确定答案。

代码如下：

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
#define int long long
using namespace std;

const int N = 1e5 + 66;

inline void up(int p)
{
    int l = p << 1, r = (p << 1) | 1;
    return (void)(tree[p].dat = tree[l].dat + tree[r].dat);
}

inline void down(int p)
{
    if (! tree[p].tag) return;
    int l = p << 1, r = (p << 1) | 1, c = tree[p].tag;
    tree[l].tag = tree[r].tag = c;
    if (tree[p].tag == 1) tree[l].dat = tree[r].dat = 0;
    else tree[l].dat = tree[l].len, tree[r].dat = tree[r].len;
    return (void)(tree[p].tag = 0);
}

inline void build(int p, int l, int r, int k)
{
    tree[p].len = (r - l + 1);
    if (l == r) return (void)(tree[p].dat = (a[l] >= k));
    int mid = (l + r) >> 1;
    build(p << 1, l, mid, k), build((p << 1) | 1, mid + 1, r, k);
    return (void)(up(p));
}

inline void updata(int p, int l, int r, int nl, int nr, int k)
{
    if (nl <= l && nr >= r)
    {
        tree[p].tag = k + 1;
        tree[p].dat = tree[p].len * k;
        return;
    }
    down(p);
    int mid = (l + r) >> 1;
    if (nl <= mid) updata(p << 1, l, mid, nl, nr, k);
    if (nr > mid) updata((p << 1) | 1, mid + 1, r, nl, nr, k);
    return (void)(up(p));
}

inline bool query(int p, int l, int r, int x)
{
    if (l == r) return tree[p].dat == 1;
    down(p);
    int mid = (l + r) >> 1;
    if (x <= mid) return query(p << 1, l, mid, x);
    return query((p << 1) | 1, mid + 1, r, x);
}

inline int query(int p, int l, int r, int nl, int nr)
{
    if (nl <= l && nr >= r) return tree[p].dat;
    down(p);
    int mid = (l + r) >> 1, res(0);
    if (nl <= mid) res = query(p << 1, l, mid, nl, nr);
    if (nr > mid) res += query((p << 1) | 1, mid + 1, r, nl, nr);
    return res;
}

inline bool pd(int k)
{
    memset(&tree, 0, sizeof tree);
    build(1, 1, n, k);
    for (int i = 1; i <= m; ++ i)
    {
        int cnt = query(1, 1, n, le[i], ri[i]);
        if (cnt == 0 || cnt == ri[i] - le[i] + 1) continue;
        if (opt[i] == 0)
        {
            updata(1, 1, n, le[i], ri[i] - cnt, 0);
            updata(1, 1, n, ri[i] - cnt + 1, ri[i], 1);
        }
        else 
        {
            updata(1, 1, n, le[i], le[i] + cnt - 1, 1);
            updata(1, 1, n, le[i] + cnt, ri[i], 0);
        }
    }
    return query(1, 1, n, q);
}

signed main()
{
    {
        n = read(), m = read();
        for (int i = 1; i <= n; ++ i) a[i] = read();
        for (int i = 1; i <= m; ++ i) opt[i] = read(), le[i] = read(), ri[i] = read();
        q = read();
    }
    {
        int l = 1, r = n, mid, res;
        while (l < r)
        {
            mid = (l + r + 1) >> 1;
            if (pd(mid)) l = mid;
            else r = mid - 1;
        }
        put(l);
    }
    return 0;
}