|
|
#include <cstdio>
|
|
|
#include <cstring>
|
|
|
#include <algorithm>
|
|
|
#include <iostream>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 2e5 + 5;
|
|
|
int n, m, q;
|
|
|
|
|
|
//输入的指令序列
|
|
|
struct Sort {
|
|
|
int op, l, r;
|
|
|
} s[N];
|
|
|
|
|
|
int a[N]; //原始数组
|
|
|
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int tag; // 0:升序 1：降序 2:初始值 lazy tag:懒标记 ，不想每次都做一遍，不查询不想做
|
|
|
int sum; //大于目标值的个数
|
|
|
} tr[N << 2];
|
|
|
|
|
|
//管辖区间长度
|
|
|
int len(int u) {
|
|
|
return tr[u].r - tr[u].l + 1;
|
|
|
}
|
|
|
|
|
|
//向父节点更新信息，写成Node &的方式目前看来是最合理的办法
|
|
|
void pushup(Node &c, Node &a, Node &b) {
|
|
|
c.sum = a.sum + b.sum;
|
|
|
}
|
|
|
|
|
|
//更新lazy tag标识
|
|
|
void pushdown(int u) {
|
|
|
if (tr[u].tag == 2) return; //如果没有下传标识，啥也不干
|
|
|
|
|
|
tr[u << 1].sum = len(u << 1) * tr[u].tag; //左儿子区间内所有数字都要加上tr[u].tag,sum值为累加
|
|
|
tr[u << 1 | 1].sum = len(u << 1 | 1) * tr[u].tag; //右儿子区间内所有数字都要加上tr[u].tag,sum值为累加
|
|
|
|
|
|
tr[u << 1].tag = tr[u << 1 | 1].tag = tr[u].tag; //左右儿子都修改标识为tag,一次只更新一层
|
|
|
|
|
|
tr[u].tag = 2; //标识已处理
|
|
|
}
|
|
|
|
|
|
//构建线段树,x:当前两分取到的值，用于建立线段树时判断每个叶子的初始值是1还是0
|
|
|
// a[l]>=x tr[u].sum=1
|
|
|
// a[l]<x tr[u].sum=0
|
|
|
// 本质上是记录了在区间内有多少个大于等于目标值的数字个数
|
|
|
void build(int u, int l, int r, int x) {
|
|
|
/*
|
|
|
① {l,r}为管控区间；
|
|
|
② 因为此时的操作运算有两种：0代表升序，1代表是降序，如果有这两个标识存在，都需要向下进行传递。
|
|
|
如果不是这两个标识，表示没有需要传递的操作，可是0和1都被占了，所以 tag=2,表示现在没有需要下传的标记
|
|
|
③ 默认的区间中比指定x大的数量还没有来的及计算，一会初始完或者更新完时，再通过pushup去更新，先写成0
|
|
|
*/
|
|
|
tr[u] = {l, r, 2, 0};
|
|
|
if (l == r) {
|
|
|
tr[u].sum = a[l] >= x; //大于等于x的都设置为1,小于x的设置为0
|
|
|
return;
|
|
|
}
|
|
|
//递归构建左右子树
|
|
|
int mid = (l + r) >> 1;
|
|
|
build(u << 1, l, mid, x), build(u << 1 | 1, mid + 1, r, x);
|
|
|
|
|
|
//向上更新统计信息
|
|
|
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
|
|
|
}
|
|
|
|
|
|
//查询区间内数字1的个数
|
|
|
int query(int u, int l, int r) {
|
|
|
if (l > tr[u].r || r < tr[u].l) return 0; //不在范围内的返回0
|
|
|
if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum; //整个区间命中，返回统计信息
|
|
|
|
|
|
// 分裂前要记得 lazy tag下传
|
|
|
pushdown(u);
|
|
|
//分裂查询 左儿子+右儿子
|
|
|
return query(u << 1, l, r) + query(u << 1 | 1, l, r);
|
|
|
}
|
|
|
|
|
|
//区间修改
|
|
|
void modify(int u, int l, int r, int c) {
|
|
|
if (l > r) return; //特判边界，防止越界
|
|
|
|
|
|
//如果命中区间，对区间的lazy tag和sum进行计算修改
|
|
|
if (l <= tr[u].l && r >= tr[u].r) {
|
|
|
tr[u].tag = c;
|
|
|
tr[u].sum = c * len(u);
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
//没有命中区间，需要递归向左右儿子传递修改消息
|
|
|
pushdown(u);
|
|
|
//修改左区间
|
|
|
if (l <= tr[u << 1].r) modify(u << 1, l, r, c);
|
|
|
//修改右区间
|
|
|
if (r >= tr[u << 1 | 1].l) modify(u << 1 | 1, l, r, c);
|
|
|
|
|
|
//因为子区间内容修改，需要向父节点更新统计信息
|
|
|
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
|
|
|
}
|
|
|
|
|
|
bool check(int x) {
|
|
|
build(1, 1, n, x); //每次全新构建线段树
|
|
|
|
|
|
for (int i = 1; i <= m; i++) { //枚举每个排序动作
|
|
|
int l = s[i].l, r = s[i].r, op = s[i].op; // 0:升序，1：降序
|
|
|
int c = query(1, l, r); //查询l,r之间数字1的个数,也是大于等于x的个数
|
|
|
|
|
|
//算法本质：忽略数字的正实值，只记录大小关系，大于等于记录为1，小于记录为0
|
|
|
if (op) //降序
|
|
|
modify(1, l, l + c - 1, 1), modify(1, l + c, r, 0); //比x大的个数是c个，如果是降序，[l,l+c-1]修改为1，表示区间都大于等于x,[l+c,r]修改为0，表示这区间小于x
|
|
|
else //升序
|
|
|
modify(1, l, r - c, 0), modify(1, r - c + 1, r, 1); //比x大的个数是c个，如果是升序，[l,r-c]修改为0，表示区间[l,r-c]都比x小，后面[r-c+1,r]都大于等于x
|
|
|
}
|
|
|
|
|
|
//按上面的操作序列要求，都模拟了一遍后，如果q这个位置上的数位是1，表示操作没有出现矛盾
|
|
|
return query(1, q, q) == 1;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
cin >> n >> m;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i]; //第二行为 n 个整数，表示 1 到 n 的一个排列
|
|
|
|
|
|
for (int i = 1; i <= m; i++) cin >> s[i].op >> s[i].l >> s[i].r; //记录排序的动作与范围
|
|
|
|
|
|
cin >> q; //查询第q个位置上的数字是多少
|
|
|
|
|
|
int l = 1, r = n; //开始二分,因为原始序列的数字，是从[1,n]的不重复序列排列，所以有二分时上下限就是决定好的[1,n]
|
|
|
while (l <= r) {
|
|
|
int mid = (l + r) >> 1; //来尝试位置q上的数字是多大，假设为mid
|
|
|
if (check(mid)) //此位置的值大于等于mid
|
|
|
l = mid + 1; //那么继续尝试l=mid+1,看看结果向右半区间走，也就是再大一点是不是可以
|
|
|
else
|
|
|
r = mid - 1; //向左半区间走，看看再小一点是不是可以
|
|
|
}
|
|
|
printf("%d\n", l - 1);
|
|
|
return 0;
|
|
|
} |
