LOJ 2055 - 「TJOI / HEOI2016」排序

发表于 更新于 分类于 阅读次数：

题目链接：LOJ 2055

答案的区间是 \([1,n]\)，考虑二分答案。

在check的时候我们把当前假设的答案记为 \(u\)，比 \(u\) 大的位置记为 \(1\)，否则记为 \(0\)，得到一个新的 01 序列，用这个序列建线段树，维护区间和。当我们遇到对一个区间顺序排序的询问，就是把区间里的 1 放到区间的最后，否则把 0 放在区间最后。每次 check 需要做 \(m\) 个操作，操作结束之后如果目标位置的值为 \(1\)，就说明答案大于 \(u\)，否则小于等于 \(u\)。

渐进时间复杂度 \(O((n + m) \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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
int n, m, a[MAX_N], b[MAX_N], tree[MAX_N << 2], tag[MAX_N << 2];
int op[MAX_N], opL[MAX_N], opR[MAX_N];
int pos;
void makeTag(int u) {
    for (int i = 1; i <= n; ++i) b[i] = (a[i] > u ? 1 : 0);
    // printf("u = %d\n", u);
    // for (int i = 1; i <= n; ++i) printf("%d%c", b[i], i == n ? '\n' : ' ');
}
inline int ls(int o) {
    return o << 1;
}
inline int rs(int o) {
    return o << 1 | 1;
}
inline void pushUp(int o) {
    tree[o] = tree[ls(o)] + tree[rs(o)];
}
inline void pushDown(int o, int l, int r) {
    if (tag[o] == -1) return;
    tag[ls(o)] = tag[rs(o)] = tag[o];
    int mid = (l + r) >> 1;
    tree[ls(o)] = tag[o] * (mid - l + 1);
    tree[rs(o)] = tag[o] * (r - mid);
    tag[o] = -1;
}
void build(int o, int l, int r) {
    tag[o] = -1;
    if (l == r) {
        tree[o] = b[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(o), l, mid);
    build(rs(o), mid + 1, r);
    pushUp(o);
}
void update(int o, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) {
        tag[o] = v;
        tree[o] = v * (r - l + 1);
        return;
    }
    int mid = (l + r) >> 1;
    pushDown(o, l, r);
    if (L <= mid) update(ls(o), l, mid, L, R, v);
    if (R > mid) update(rs(o), mid + 1, r, L, R, v);
    pushUp(o);
}
int query(int o, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[o];
    int mid = (l + r) >> 1, ret = 0;
    pushDown(o, l, r);
    if (L <= mid) ret += query(ls(o), l, mid, L, R);
    if (R > mid) ret += query(rs(o), mid + 1, r, L, R);
    return ret;
}
int main() {
    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", op + i, opL + i, opR + i);
    scanf("%d", &pos);
    int l = 1, r = n;
    while (l < r) {
        // printf("l = %d, r = %d\n", l, r);
        int mid = (l + r) >> 1;
        makeTag(mid);
        build(1, 1, n);
        for (int i = 1; i <= m; ++i) {
            int sum = query(1, 1, n, opL[i], opR[i]);
            // printf("sum = %d\n", sum);
            switch (op[i]) {
                case 0: {
                    int k = opR[i] - sum + 1;
                    if (opL[i] <= k - 1) update(1, 1, n, opL[i], k - 1, 0);
                    if (opR[i] >= k) update(1, 1, n, k, opR[i], 1);
                    break;
                }
                case 1: {
                    int k = opL[i] + sum - 1;
                    if (opL[i] <= k) update(1, 1, n, opL[i], k, 1);
                    if (opR[i] >= k + 1) update(1, 1, n, k + 1, opR[i], 0);
                    break;
                }
            }
        }
        if (query(1, 1, n, pos, pos)) l = mid + 1;
        else r = mid;
    }
    printf("%d\n", l);
    return 0;
}