Description
给一个长度为 n 的排列，对它做 m 次操作，每次对 [l, r] 区间内进行升序/降序排序。
问最后的序列处于最中心的数是多少（n为奇数）。
Solution
是一类没有写过的题，参考题解。
二分答案，对于当前的 mid ，将大于等于 mid 的数设置为 1，小于 mid 的数设置为 0。这样一来，叶结点的值只有 0/1，区间操作时也可以直接对部分区间赋值为 1，部分区间赋值为0。最后单点查询中间值是否为1即可。
具体来说，对于一次升序的区间操作 [l,r]，先建树，并且查询其中1的数目sum。将[r-sum+1, r]的区间赋值为 1 ，[l, r-sum] 赋值为0。注意判断区间的合法性（\(l\leq r\)）。降序操作类似。
所以，我们需要支持的线段树操作只有区间求和、区间修改（改为0/1）。
关于 tag 的设置：为了方便，tag = 0 代表该区间需要全部覆盖为0，tag = 1代表该区间需要全部覆盖为1，tag = -1表示无需pushdown。
Code
// By DTTTTTTT 2023/6/1 六一快乐！
/*
* dtt每次都写错的线段树易错点小结：
* 1. 计算mid的时候只有build中是直接使用 l+r>>1，update和query中都是 t[p].l+t[p].r>>1;
* 2. update的末尾记得 t[p].sum=t[lc].sum+t[rc].sum
* 3. update和query的 l 与 r 是不需要改变/收缩范围的，如果改变需要讨论，会很容易错
* 4. pushdown中记得写直接return的两种情况（叶结点、没有tag）
*
* 小结一下线段树的各个操作流程：
* 1. build(int p,int l,int r)：
建树，需要初始化node的l/r/tag，叶结点直接赋sum并返回，非叶结点继续向下建树，建完后累加sum。
* 2. query(int p,int l,int r)：
若p结点的区间完全被涵盖在[l,r]区间中，直接返回其sum；
否则需要向下计算，先pushdown，然后分别看左右两个子区间是否与[l,r]有重合，有则需计算。
int ret=0, mid=t[p].l+t[p].r>>1;
if(l<=mid) ret+=query(p<<1,l,r); //这里的l与r无需改变
if(r>mid) ret+=query(p<<1|1,l,r);
return ret;
* 3. update(int p,int l,int r,int val)：//这里以将[l,r]区间内所有数变为val这个更新操作为例
若p结点的区间完全被涵盖在[l,r]区间中，直接更新sum并标记tag；
否则需要向下更新，先pushdown，然后分别看左右两个子区间是否与[l,r]有重合，有则需更新。
最后一定记得更新当前结点的sum。
int mid=t[p].l+t[p].r>>1;
if(l<=mid) update(p<<1,l,r,val);
if(r>mid) update(p<<1|1,l,r,val);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
* 4. pushdown(int p)：只需pushdown一层，无需递归操作
首先判断无需pushdown的情况：叶结点或者没有打lazy_tag
判断完毕后更新两个子区间的sum和tag
最后一定记得将自己的tag取消
t[p<<1].sum =..... ,t[p<<1|1].sum=...,t[p<<1].tag=t[p<<1|1].tag=t[p].tag;
t[p].tag = -1; //假设这里-1代表没有
其实觉得query和update的操作特别像，都是若全都包含在内则直接处理并返回，不然就要向下走。
特别注意的是update向下更新完毕后记得更新自己的sum。
*/
#include<iostream>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], b[N];
struct interval {
int l, r, op;
}inte[N];
struct node {
int l, r, sum, tag;
}t[N << 2];
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].tag = -1;
if (l == r) {
t[p].sum = b[l];
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
t[p].sum = t[lc].sum + t[rc].sum;
}
void pushdown(int p) {
if (t[p].l == t[p].r || t[p].tag == -1) //无需pushdown的两种情况
return;
t[lc].tag = t[rc].tag = t[p].tag;
t[lc].sum = (t[lc].r - t[lc].l + 1) * t[p].tag;
t[rc].sum = (t[rc].r - t[rc].l + 1) * t[p].tag;
//t[p].sum = t[lc].sum + t[rc].sum; 这里可以没有
t[p].tag = -1;
}
int query(int p, int l, int r) {
if (t[p].l >= l && t[p].r <= r)
return t[p].sum;
pushdown(p);
int mid = t[p].l + t[p].r >> 1, ret = 0;
//永远都会写错成 mid=l+r>>1 啊啊啊！！！！！！！rem！！！
if (l <= mid)
ret += query(lc, l, r); //这里的l与r无需改变
if (r > mid)
ret += query(rc, l, r);
return ret;
}
void update(int p, int l, int r, int val) {
if (l > r)
return;
if (t[p].l >= l && t[p].r <= r) {
t[p].sum = (t[p].r - t[p].l + 1) * val;
t[p].tag = val;
return;
}
pushdown(p);
int mid = t[p].l + t[p].r >> 1;
if (l <= mid)
update(lc, l, r, val);
if (r > mid)
update(rc, l, r, val);
t[p].sum = t[lc].sum + t[rc].sum; //这里不能落
}
bool check(int mid) {
for (int i = 1;i <= n;++i)
b[i] = (a[i] >= mid);
build(1, 1, n);
for (int i = 1;i <= m;++i) {
int l = inte[i].l, r = inte[i].r, op = inte[i].op;
int sum = query(1, l, r);
if (op == 1) //升序
update(1, l, r - sum, 0), update(1, r - sum + 1, r, 1);
else
update(1, l, l + sum - 1, 1), update(1, l + sum, r, 0);
}
return query(1, n / 2 + 1, n / 2 + 1);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;++i) cin >> a[i];
for (int i = 1;i <= m;++i) {
cin >> inte[i].l >> inte[i].r;
if (inte[i].l > inte[i].r)
swap(inte[i].l, inte[i].r), inte[i].op = 2; //降序
else
inte[i].op = 1; //升序
}
int l = 1, r = n, mid, ans = -1;
while (l <= r) {
mid = l + r >> 1;
if (check(mid))
ans = mid, l = mid + 1;
else
r = mid - 1;
}
cout << ans << endl;
return 0;
}