题面

大秦为你打开题目传送门

题目描述

在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。

这个难题是这样子的：给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：

  • 0 l r 表示将区间 $[l,r]$ 的数字升序排序
  • 1 l r 表示将区间 $[l,r]$ 的数字降序排序

注意，这里是对下标在区间 $[l,r]$ 内的数排序。
最后询问第 $q$ 位置上的数字。

输入格式

输入数据的第一行为两个整数 $n$ 和 $m$，$n$ 表示序列的长度，$m$ 表示局部排序的次数。

第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。

接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$，$\text{op}$ 为 $0$ 代表升序排序，$\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。

最后输入一个整数 $q$，表示排序完之后询问的位置

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

样例输出 #1

1
5

提示

河北省选2016第一天第二题。

对于 $30\%$ 的数据，$n,m\leq 1000$

对于 $100\%$ 的数据，$n,m\leq 10^5$，$1\leq q\leq n$

思路

首先拿到这道题目，不难发现：只有一个询问。如果是单纯的排序，我们发现时间非常的长。排序一次就得 $O(n\log n)$ 这是不允许的。我们考虑如何转化。

如果我们拿到的是一个 $\tt 01$ 序列，这个怎么做？设有 $x$ 个 0 ，那么只需要把前 $x$ 个变成 0，后 $len-x$ 个变成 1 就可以了。那么如果我们二分一个中间值，把序列大于他的设为 1 ，小于他的设成 0 。这样是满足单调性的，如果你二分出来的这个值，变成 01 后，q 位置是 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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 100010;

int n, m, q;
int a[N];
struct Que {
    int op, l, r;
}Q[N];

class SegTree {
private :
    struct Node {
        int L, R;
        int sum, lazy;
    }node[N << 2];
public :
    void Add(int p, int v) {
        node[p].sum = (node[p].R - node[p].L + 1) * v;
        node[p].lazy = v;
    }
    void PushDown(int p) {
        if(node[p].lazy == -1) return ;
        Add(p << 1, node[p].lazy);
        Add(p << 1 | 1, node[p].lazy);
        node[p].lazy = -1;
    }

    void Build(int p, int L, int R, int x) {
        node[p].L = L, node[p].R = R, node[p].lazy = -1;
        if(L == R) {
            node[p].sum = (a[L] >= x);
            return;
        }
        int mid = L + R >> 1;
        Build(p << 1, L, mid, x);
        Build(p << 1 | 1, mid + 1, R, x);
        node[p].sum = node[p << 1].sum + node[p << 1 | 1].sum;
    }
    void Modify(int p, int L, int R, int v) {
        if(L <= node[p].L && node[p].R <= R) {
            Add(p, v);
            return ;
        }
        PushDown(p);
        int mid = (node[p].L + node[p].R) >> 1; 
        if(L <= mid) Modify(p << 1, L, R, v);
        if(R > mid) Modify(p << 1 | 1, L, R, v);
        node[p].sum = node[p << 1].sum + node[p << 1 | 1].sum;
    }
    int Query(int p, int L, int R) {
        if(L <= node[p].L && node[p].R <= R) {
            return node[p].sum;
        }
        PushDown(p);
        int mid = (node[p].L + node[p].R) >> 1; 
        int ans = 0;
        if(L <= mid) ans += Query(p << 1, L, R);
        if(R > mid) ans += Query(p << 1 | 1, L, R);
        return ans;
    }
};

SegTree tree;

void Input() {
    read(n, m);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    for(int i = 1; i <= m; i++) {
        read(Q[i].op, Q[i].l, Q[i].r);
    }
    read(q);
}

bool Check(int mid) {
    tree.Build(1, 1, n, mid);
    for(int i = 1; i <= m; i++) {
        int cnt1 = tree.Query(1, Q[i].l, Q[i].r);
        if(cnt1 == 0 || cnt1 == Q[i].r - Q[i].l + 1) continue;
        if(Q[i].op) {
            tree.Modify(1, Q[i].l, Q[i].l + cnt1 - 1, 1);
            tree.Modify(1, Q[i].l + cnt1, Q[i].r, 0);
        }
        else {
            tree.Modify(1, Q[i].l, Q[i].r - cnt1, 0);
            tree.Modify(1, Q[i].r - cnt1 + 1, Q[i].r, 1);
        }
    }
    return tree.Query(1, q, q);
}

void Work() {
    int l = 1, r = n, best = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(Check(mid)) {
            l = mid + 1;
            best = mid;
        }
        else {
            r = mid - 1;
        }
    }
    printf("%d", best);
}

int main() {
    Input();
    Work();
    return 0;
}