很久以前写过二分答案离线的做法，比较好理解。事实上这还是一个线段树合并+分裂的板子题，相比离线做法以更优的复杂度做了更多的事情。具体不说了。怎么交了一遍luogu上就跑第一了啊
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;
#define N 100010
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int n,m,root[N],rev[N],cnt;
struct data{int l,r,x;
}tree[N<<];
struct data2
{
int l,r;
bool operator <(const data2&a) const
{
return r<a.r;
}
};
set<data2> q;
void ins(int &k,int x,int l,int r)
{
if (!k) k=++cnt;tree[k].x++;
if (l==r) return;
int mid=l+r>>;
if (x<=mid) ins(tree[k].l,x,l,mid);
else ins(tree[k].r,x,mid+,r);
}
void split(int &x,int &y,int rk,int op)
{
if (!x) return;
tree[y=++cnt].x=tree[x].x-rk,tree[x].x=rk;
if (op==)
{
if (tree[tree[x].l].x==rk)
{
tree[y].r=tree[x].r,tree[x].r=;
return;
}
else if (tree[tree[x].l].x>rk)
{
tree[y].r=tree[x].r,tree[x].r=;
split(tree[x].l,tree[y].l,rk,op);
}
else split(tree[x].r,tree[y].r,rk-tree[tree[x].l].x,op);
}
else
{
if (tree[tree[x].r].x==rk)
{
tree[y].l=tree[x].l,tree[x].l=;
return;
}
else if (tree[tree[x].r].x>rk)
{
tree[y].l=tree[x].l,tree[x].l=;
split(tree[x].r,tree[y].r,rk,op);
}
else split(tree[x].l,tree[y].l,rk-tree[tree[x].r].x,op);
}
}
void merge(int &x,int &y,int l,int r)
{
if (!x||!y) {x|=y;return;}
tree[x].x+=tree[y].x;
if (l<r)
{
int mid=l+r>>;
merge(tree[x].l,tree[y].l,l,mid);
merge(tree[x].r,tree[y].r,mid+,r);
}
}
int query(int k,int l,int r,int x,int op)
{
if (l==r) return l;
int mid=l+r>>;
if (op==)
{
if (tree[tree[k].l].x>=x) return query(tree[k].l,l,mid,x,op);
else return query(tree[k].r,mid+,r,x-tree[tree[k].l].x,op);
}
else
{
if (tree[tree[k].r].x>=x) return query(tree[k].r,mid+,r,x,op);
else return query(tree[k].l,l,mid,x-tree[tree[k].r].x,op);
}
}
void print(int k,int l,int r)
{
if (!tree[k].x) return;
if (l==r) {cout<<l<<' ';return;}
int mid=l+r>>;
print(tree[k].l,l,mid),print(tree[k].r,mid+,r);
}
int main()
{
n=read(),m=read();
for (int i=;i<=n;i++) ins(root[i],read(),,n),q.insert((data2){i,i});
while (m--)
{
int op=read(),l=read(),r=read();
set<data2>::iterator it=q.lower_bound((data2){l,l});
if ((*it).l<l)
{
split(root[(*it).l],root[l],l-(*it).l,rev[(*it).l]);
int L=(*it).l,R=(*it).r;
q.erase(it);
q.insert((data2){L,l-});
q.insert((data2){l,R});
rev[l]=rev[L];
}
it=q.lower_bound((data2){r+,r+});
if (it!=q.end()&&(*it).l<=r)
{
split(root[(*it).l],root[r+],r-(*it).l+,rev[(*it).l]);
int L=(*it).l,R=(*it).r;
q.erase(it);
q.insert((data2){L,r});
q.insert((data2){r+,R});
rev[r+]=rev[L];
}
it=q.lower_bound((data2){l,l});it++;
while (it!=q.end()&&(*it).r<=r) merge(root[l],root[(*it).l],,n),it++;
it=q.lower_bound((data2){l,l});
while (it!=q.end()&&(*it).r<=r) q.erase(it),it=q.lower_bound((data2){l,l});
q.insert((data2){l,r});
rev[l]=op;
//it=q.begin();while (it!=q.end()) cout<<(*it).l<<' '<<(*it).r<<" ",print(root[(*it).l],1,n),it++,cout<<endl;cout<<endl;
//it=q.begin();while (it!=q.end()) cout<<(*it).l<<' '<<(*it).r<<endl,it++;cout<<endl;
}
int x=read();
set<data2>::iterator it=q.lower_bound((data2){x,x});
cout<<query(root[(*it).l],,n,x-(*it).l+,rev[(*it).l]);
/*for (int x=1;x<=n;x++)
{
set<data2>::iterator it=q.lower_bound((data2){x,x});
cout<<query(root[(*it).l],1,n,x-(*it).l+1,rev[(*it).l])<<' ';
}*/
}