|
|
/*
|
|
|
二分答案记为x 将小于等于x的数置为1 其余置为0 这样就可以处理排序操作 最后判一下目标位置处是否为1即可
|
|
|
|
|
|
二分的值越大 整个区间内的1数量越多,每次排序操作都会把1全部挪到左边或右边,1越多越有可能覆盖到目标位置,
|
|
|
具有单调性。
|
|
|
*/
|
|
|
#include <iostream>
|
|
|
#include <string.h>
|
|
|
#include <stdio.h>
|
|
|
#include <vector>
|
|
|
#include <map>
|
|
|
#include <queue>
|
|
|
#include <algorithm>
|
|
|
#include <math.h>
|
|
|
#include <cstdio>
|
|
|
//宏定义左右儿子
|
|
|
#define ls u << 1
|
|
|
#define rs (u << 1) | 1
|
|
|
using namespace std;
|
|
|
const int N = 2e5 + 5;
|
|
|
int n, m, k;
|
|
|
|
|
|
struct Query {
|
|
|
int op, l, r;
|
|
|
} q[N];
|
|
|
|
|
|
int a[N];
|
|
|
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int val; // 0:升序 1：降序 -1:无操作
|
|
|
int sum;
|
|
|
} tr[N << 2];
|
|
|
|
|
|
//线段树取管辖区间长度，适用于lazy tag统一变化时sum的快速计算
|
|
|
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].val == -1) return; //如果没有下传标识，啥也不干
|
|
|
tr[ls].sum = len(ls) * tr[u].val; //如果有下传标识，左儿子区间内所有数字都要加上tr[u].add,sum值为累加
|
|
|
tr[rs].sum = len(rs) * tr[u].val; //如果有下传标识，右儿子区间内所有数字都要加上tr[u].add,sum值为累加
|
|
|
tr[ls].val = tr[rs].val = tr[u].val; //左右儿子都修改标识为val,一次只更新一层
|
|
|
tr[u].val = -1; //标识已处理
|
|
|
}
|
|
|
|
|
|
//构建线段树,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) {
|
|
|
tr[u] = {l, r, -1, 0}; //注意这里初始化，val=-1,否则会被认为需要将lazy tag=0,将区间内所有值设置为0
|
|
|
if (l == r) {
|
|
|
tr[u].sum = a[l] >= x; //大于等于x的都设置为1,小于x的设置为0
|
|
|
return;
|
|
|
}
|
|
|
int mid = (l + r) >> 1;
|
|
|
build(ls, l, mid, x), build(rs, mid + 1, r, x);
|
|
|
//更新父节点信息
|
|
|
pushup(tr[u], tr[ls], tr[rs]);
|
|
|
}
|
|
|
|
|
|
//查询区间内数字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(ls, l, r) + query(rs, l, r);
|
|
|
}
|
|
|
|
|
|
//区间修改
|
|
|
void modify(int u, int l, int r, int v) {
|
|
|
//特判边界，防止越界
|
|
|
if (l > r) return;
|
|
|
//如果命中区间，对区间的lazy tag和sum进行计算修改
|
|
|
if (l <= tr[u].l && r >= tr[u].r) {
|
|
|
tr[u].val = v;
|
|
|
tr[u].sum = v * len(u);
|
|
|
return;
|
|
|
}
|
|
|
//没有命中区间，需要递归向左右儿子传递修改消息
|
|
|
pushdown(u);
|
|
|
//修改左区间
|
|
|
if (l <= tr[ls].r) modify(ls, l, r, v);
|
|
|
//修改右区间
|
|
|
if (r >= tr[rs].l) modify(rs, l, r, v);
|
|
|
//因为子区间内容修改，需要向父节点更新统计信息
|
|
|
pushup(tr[u], tr[ls], tr[rs]);
|
|
|
}
|
|
|
|
|
|
bool check(int x) {
|
|
|
//每次本新构建线段树
|
|
|
build(1, 1, n, x);
|
|
|
//根据输入排序的次序，范围，由大到小：1 ，由小到大：0
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
int l = q[i].l, r = q[i].r, op = q[i].op;
|
|
|
//到一个大于等于x就是1，小于x就是0的线段树中去查找
|
|
|
int c = query(1, l, r); //查询l,r之间数字1的个数
|
|
|
if (op == 1) //由大到小排序,所有1在前，所有0在后
|
|
|
modify(1, l, l + c - 1, 1), modify(1, l + c, r, 0);
|
|
|
else //由小到大排序,所有0在前，所有1在后
|
|
|
modify(1, l, r - c, 0), modify(1, r - c + 1, r, 1);
|
|
|
}
|
|
|
//经过上面的这些操作，
|
|
|
//如果第k个位置上是1，说明现在第k个位置上对应原数组中的数字是大于等于答案x的，应该试一下大的。
|
|
|
//如果第k个位置上是0，说明现在第k个位置上对应原数组中的数字是小于答案x的，应该试一下小的。
|
|
|
return query(1, k, k) == 1;
|
|
|
}
|
|
|
int main() {
|
|
|
//优化读入
|
|
|
ios::sync_with_stdio(false);
|
|
|
cin.tie(0);
|
|
|
cout.tie(0);
|
|
|
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
cin >> n >> m;
|
|
|
//原始序列
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
//排序的动作与范围
|
|
|
for (int i = 1; i <= m; i++) cin >> q[i].op >> q[i].l >> q[i].r;
|
|
|
|
|
|
//查询第k个位置上的数字是多少
|
|
|
cin >> k;
|
|
|
|
|
|
int l = 1, r = n; //左右边界，最小是1，最大是n
|
|
|
while (l <= r) {
|
|
|
//假设第k个位置上的数为mid，看看会发生什么
|
|
|
int mid = (l + r) >> 1; //二分查找
|
|
|
if (check(mid)) //如果mid符合条件
|
|
|
l = mid + 1; //似乎由于check是用==作为判断条件的，l不能取到mid,需要二刷时仔细思考下
|
|
|
else
|
|
|
r = mid - 1;
|
|
|
}
|
|
|
printf("%d\n", l - 1);
|
|
|
}
|
|
|
return 0;
|
|
|
} |
