嘟嘟嘟
首先这题的暴力是十分好写的，而且据说能得不少分。
正解写起来不难，就是不太好想。
根据做题经验，我想到了给这个序列转化成01序列，但是接下来我就不会了。还是看了题解。
因为查询只有一个数，所以可以二分答案：把大于等于mid的数标记成1，小于mid的数为0.这样排序就是区间赋值了，线段树可做。
那怎么检验mid是否正确呢？其实这个是有单调性的：如果二分的是1，那么很显然最后位置(q)上一定是1，随着二分的值变大，位置(q)上是1的可能性就越小。这大抵就是二分的单调性？
（这只能算是感性理解吧）
或者说如果第(Q)位是1，那么答案就是([mid, R])，否则就是([L, mid - 1])。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, Q, a[maxn];
bool b[maxn];
struct Node
{
int op, L, R;
}q[maxn];
int l[maxn << 2], r[maxn << 2], sum[maxn << 2], lzy[maxn << 2];
In void build(int L, int R, int now)
{
l[now] = L, r[now] = R;
lzy[now] = -1;
if(L == R) {sum[now] = b[L]; return;}
int mid = (L + R) >> 1;
build(L, mid, now << 1);
build(mid + 1, R, now << 1 | 1);
sum[now] = sum[now << 1] + sum[now << 1 | 1];
}
In void change(int now, int flg)
{
sum[now] = (r[now] - l[now] + 1) * flg;
lzy[now] = flg;
}
In void pushdown(int now)
{
if(~lzy[now])
{
change(now << 1, lzy[now]), change(now << 1 | 1, lzy[now]);
lzy[now] = -1;
}
}
In void update(int L, int R, int now, int flg)
{
if(L > R) return;
if(l[now] == L && r[now] == R) {change(now, flg); return;}
pushdown(now);
int mid = (l[now] + r[now]) >> 1;
if(R <= mid) update(L, R, now << 1, flg);
else if(L > mid) update(L, R, now << 1 | 1, flg);
else update(L, mid, now << 1, flg), update(mid + 1, R, now << 1 | 1, flg);
sum[now] = sum[now << 1] + sum[now << 1 | 1];
}
In int query(int L, int R, int now)
{
if(l[now] == L && r[now] == R) return sum[now];
pushdown(now);
int mid = (l[now] + r[now]) >> 1;
if(R <= mid) return query(L, R, now << 1);
else if(L > mid) return query(L, R, now << 1 | 1);
else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1);
}
In bool judge(int x)
{
for(int i = 1; i <= n; ++i) b[i] = (a[i] >= x);
build(1, n, 1);
for(int i = 1; i <= m; ++i)
{
int tp = query(q[i].L, q[i].R, 1);
if(!q[i].op)
{
update(q[i].L, q[i].R - tp, 1, 0);
update(q[i].R - tp + 1, q[i].R, 1, 1);
}
else
{
update(q[i].L, q[i].L + tp - 1, 1, 1);
update(q[i].L + tp, q[i].R, 1, 0);
}
}
return query(Q, Q, 1);
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= m; ++i) q[i].op = read(), q[i].L = read(), q[i].R = read();
Q = read();
int L = 1, R = n;
while(L < R)
{
int mid = (L + R + 1) >> 1;
if(judge(mid)) L = mid;
else R = mid - 1;
}
write(L), enter;
return 0;
}