题目传送门(BZOJ)
>原文链接<

题解 :

直接求看起来不太可做, 但是如果我们变成已知是哪个数然后验证似乎就变得有一点可做了.

我们先二分一个mid, 对于所有的a[i] < mid , 令其为0, 否则为1,

每次操作相当于把区间里的1放到一侧,把区间里的0放到另一侧

当所有操作都做完之后, 若查询的位置答案是1, 代表实际答案大于等于当前mid, 否则小于当前mid,

更改边界继续二分即可

一共会二分出\log N次答案, 每次操作\log N, 总共复杂度O(N\log^2N)

代码 :

#include <cstdio>#include <cstring>#include <iostream>#define ls p << 1#define rs p << 1|1using namespace std;const int N = 110000;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}int t[N<<2], laz[N<<2];int a[N], opt[N], x[N], y[N], b[N], n, m;void build(int l, int r, int p) { laz[p] = -1; if(l == r) return t[p] = b[l], void(); int mid = (l+r) >> 1; build(l, mid, ls); build(mid+1, r, rs); t[p] = t[ls]+t[rs];}inline void pd(int l, int r, int p) { if(~laz[p]) { laz[ls] = laz[rs] = laz[p]; int mid = (l+r) >> 1; t[ls] = (mid-l+1)*laz[p]; t[rs] = (r-mid)*laz[p]; laz[p] = -1; }}void change(int l, int r, int p, int x, int y, int c) { if(x <= l && y >= r) return t[p] = (r-l+1)*c, laz[p] = c, void(); pd(l, r, p); int mid = (l+r) >> 1; if(x <= mid) change(l, mid, ls, x, y, c); if(y > mid) change(mid+1, r, rs, x, y, c); t[p] = t[ls]+t[rs];}int query(int l, int r, int p, int x, int y) { if(x <= l && y >= r) return t[p]; pd(l, r, p); int mid = (l+r) >> 1, re = 0; if(x <= mid) re = query(l, mid, ls, x, y); if(y > mid) re+= query(mid+1, r, rs, x, y); return re;}inline void init(int mid) { for(int i = 1; i <= n; i ++ ) b[i] = a[i] >= mid; build(1, n, 1);}inline void work() { for(int i = 1; i <= m; i ++ ) { int s = query(1, n, 1, x[i], y[i]); change(1, n, 1, x[i], y[i], 0); if(s) opt[i] == 1 ? change(1, n, 1, x[i], x[i]+s-1, 1) : change(1, n, 1, y[i]-s+1, y[i], 1); }}inline int solve(int k) { int l = 1, r = n; while(l < r) { int mid = (l+r) >> 1; init(mid); work(); if(query(1, n, 1, k, k) == 1) l = mid+1; else r = mid; } return l-1;}int main() { n = rd(), m = rd(); for(int i = 1; i <= n; i ++ ) a[i] = rd(); for(int i = 1; i <= m; i ++ ) opt[i] = rd(), x[i] = rd(), y[i] = rd(); printf("%d\n", solve(rd()));}