题目传送门
问题转化
发现询问有且仅有一次，且仅询问一个位置。
因此无需得出整个序列，得出排序后的 \(a_q\) 即可。区间排序实在不好做，因此考虑能否找到一种方式转化。
答案与 \(a_q\) 正相关，其余其实并不重要。因此不妨有：
\[a_i\leftarrow
\begin{cases}
1&a_i\geq a_q\\
0&a_i<a_q
\end{cases}
\]
这样，排序即可视为区间赋值。
枚举答案 \(a_q=x\)，可以 \(\mathcal O(m\log n)\) 维护区间赋值，若最后 \(a_q=1\)，则说明 \(x\) 是可能的解，且真实的 \(a_q\geq x\)。
因此可以二分。
时间复杂度 \(\mathcal O(m\log^2n)\)。
AC 代码
只有一次查询，因此使用 ODT 实现。时间复杂度同线段树。
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
constexpr const int N=1e5,M=1e5;
int n,m,q,backup[N+1],a[N+1];
struct operation{int op,l,r;
}op[M+1];
struct ODT{struct node{int l,r;mutable int value;};friend bool operator <(node a,node b){return a.l<b.l;}set<node>t;void build(int l,int r){t.insert({l,r+1});}void clear(){t.clear();}auto split(int x){auto p=t.lower_bound({x});if(p!=t.end()&&p->l==x){return p;}p=prev(p);int l=p->l,r=p->r,value=p->value;t.erase(p);t.insert({l,x-1,value});return t.insert({x,r,value}).first;}void assign(int l,int r,int value){auto pr=split(r+1),pl=split(l);t.erase(pl,pr);t.insert({l,r,value});}void ascending(int l,int r){auto pr=split(r+1),pl=split(l);int cnt=0;for(auto i=pl;i!=pr;i=next(i)){if(i->value){cnt+=i->r - i->l + 1;}}assign(l,r-cnt,0);assign(r-cnt+1,r,1);}void descending(int l,int r){auto pr=split(r+1),pl=split(l);int cnt=0;for(auto i=pl;i!=pr;i=next(i)){if(i->value){cnt+=i->r - i->l + 1;}}assign(l,l+cnt-1,1);assign(l+cnt,r,0);}int perform(int x){auto pr=split(x+1),pl=split(x);return pl->value;}
}t;
bool check(int mid){t.clear();t.build(1,n);for(int i=1;i<=n;i++){t.assign(i,i,a[i]>=mid);}for(int i=1;i<=m;i++){switch(op[i].op){case 0:t.ascending(op[i].l,op[i].r);break;case 1:t.descending(op[i].l,op[i].r);break;}}return t.perform(q);
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::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>>op[i].op>>op[i].l>>op[i].r;}cin>>q;int l=0,r=n;while(l<r){int mid=l+r+1>>1;if(check(mid)){l=mid;}else{r=mid-1;}}cout<<l<<'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}