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
| #include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;
int n, m, k, a[maxn], b[maxn];
struct Query {
int opt, l, r;
} Q[maxn];
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
int f0, f1, v;
} T[maxn * 4];
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; }
void build(int i, int l, int r) {
T[i].f0 = T[i].f1 = 0;
if (l == r) return (void) (T[i].v = b[l]);
int m = l + r >> 1;
build(lc, l, m); build(rc, m + 1, r);
maintain(i);
}
inline void Up0(int i, int l, int r) { T[i].f1 = T[i].v = 0; T[i].f0 = 1; }
inline void Up1(int i, int l, int r) { T[i].f0 = 0; T[i].v = r - l + 1; T[i].f1 = 1; }
inline void pushdown(int i, int l, int r) {
int &f0 = T[i].f0, &f1 = T[i].f1, m = l + r >> 1;
if (!f0 && !f1) return ;
if (f0) Up0(lc, l, m), Up0(rc, m + 1, r);
else Up1(lc, l, m), Up1(rc, m + 1, r);
f0 = f1 = 0;
}
void up0(int i, int l, int r, int L, int R) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return Up0(i, l, r);
int m = l + r >> 1; pushdown(i, l, r);
up0(lc, l, m, L, R); up0(rc, m + 1, r, L, R);
maintain(i);
}
void up1(int i, int l, int r, int L, int R) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return Up1(i, l, r);
int m = l + r >> 1; pushdown(i, l, r);
up1(lc, l, m, L, R); up1(rc, m + 1, r, L, R);
maintain(i);
}
int query(int i, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (L <= l && r <= R) return T[i].v;
int m = l + r >> 1; pushdown(i, l, r);
return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
}
int query(int i, int l, int r, int k) {
if (l == r) return T[i].v;
int m = l + r >> 1; pushdown(i, l, r);
if (k <= m) return query(lc, l, m, k);
else return query(rc, m + 1, r, k);
}
inline void solve_0(int o) {
int l = Q[o].l, r = Q[o].r, s0, s1;
s1 = query(1, 1, n, l, r); s0 = r - l + 1 - s1;
up0(1, 1, n, l, l + s0 - 1); up1(1, 1, n, l + s0, r);
}
inline void solve_1(int o) {
int l = Q[o].l, r = Q[o].r, s0, s1;
s1 = query(1, 1, n, l, r); s0 = r - l + 1 - s1;
up1(1, 1, n, l, l + s1 - 1); up0(1, 1, n, l + s1, r);
}
bool check(int x) {
for (int i = 1; i <= n; ++i) b[i] = a[i] >= x;
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int opt = Q[i].opt;
if (!opt) solve_0(i);
else solve_1(i);
}
return query(1, 1, n, k);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &Q[i].opt, &Q[i].l, &Q[i].r); cin >> k;
int l = 1, r = n, ans, mid;
while (l <= r) {
mid = l + r >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
} cout << ans << endl;
return 0;
}
|