• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

4小时前 2次浏览

# (text{Solution})

(mid) 越小越容易，越大越困难，临界点即为答案

# (text{Code})

``````#include <cstdio>
#include <cstring>
#define ls (p << 1)
#define rs (ls | 1)
#define re register
using namespace std;

const int N = 1e5 + 5;
int n, m, q, a[N];
struct node{int op, l, r;}b[N];

{
x = 0; char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}

int tag[N << 2], sum[N << 2];

inline void pushup(int p){sum[p] = sum[ls] + sum[rs];}
inline void pushdown(int p, int l, int r)
{
if (tag[p] == -1) return;
int mid = (l + r) >> 1;
if (!tag[p]) sum[ls] = mid - l + 1, sum[rs] = r - mid;
else sum[ls] = sum[rs] = 0;
tag[ls] = tag[rs] = tag[p], tag[p] = -1;
}

void update(int p, int l, int r, int x, int y, int v)
{
if (x > r || y < l) return;
if (x <= l && r <= y)
{
tag[p] = v, sum[p] = (v ? 0 : r - l + 1);
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) update(ls, l, mid, x, y, v);
if (y > mid) update(rs, mid + 1, r, x, y, v);
pushup(p);
}

int query_0(int p, int l, int r, int x, int y)
{
if (x > r || y < l) return 0;
if (x <= l && r <= y) return sum[p];
pushdown(p, l, r);
int mid = (l + r) >> 1, res = 0;
if (x <= mid) res = query_0(ls, l, mid, x, y);
if (y > mid) res += query_0(rs, mid + 1, r, x, y);
return res;
}

inline int check(int mid)
{
memset(tag, 255, sizeof tag), memset(sum, 0, sizeof sum);
for(re int i = 1; i <= n; i++) update(1, 1, n, i, i, a[i] >= mid);
for(re int i = 1, l, r, num; i <= m; i++)
{
num = query_0(1, 1, n, b[i].l, b[i].r);
if (!b[i].op) l = b[i].l, r = b[i].l + num - 1,
update(1, 1, n, l, r, 0), update(1, 1, n, r + 1, b[i].r, 1);
else l = b[i].l, r = b[i].l + (b[i].r - b[i].l + 1 - num) - 1,
update(1, 1, n, l, r, 1), update(1, 1, n, r + 1, b[i].r, 0);
}
return !query_0(1, 1, n, q, q);
}

int main()
{
for(re int i = 1; i <= n; i++) read(a[i]);
int l = 1, r = n, mid, ans = 0;