1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<bits/stdc++.h>
#define REG register
#define MAXN 100005
#define IT set<int>::iterator
using namespace std;
inline int read(){
REG int x(0);
REG char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
int n,m,q;
#define Ls(now) (t[now].ls)
#define Rs(now) (t[now].rs)
#define mid ((l+r)>>1)
struct Tree{
int val,ls,rs;
}t[MAXN<<8];
int rt[MAXN],Direc[MAXN],tot;
void Update(int& now,int l,int r,int status){
t[now=++tot].val=1;
if(l==r) return;
if(mid>=status) Update(Ls(now),l,mid,status);
else Update(Rs(now),mid+1,r,status);
}
int GetPos(int now,int l,int r){
if(l==r) return l;
return Ls(now)?GetPos(Ls(now),l,mid):GetPos(Rs(now),mid+1,r);
}
int merge(int a,int b){
if(!a||!b) return a|b;
t[a].val+=t[b].val;
Ls(a)=merge(Ls(a),Ls(b));
Rs(a)=merge(Rs(a),Rs(b));
return a;
}
void split(int& x,int y,int k,int Dir){
if(t[y].val==k) return;
t[x=++tot].val=t[y].val-k,t[y].val=k;
if(Dir)
if(k<=t[Rs(y)].val) split(Rs(x),Rs(y),k,Dir),Ls(x)=Ls(y),Ls(y)=0;
else split(Ls(x),Ls(y),k-t[Rs(y)].val,Dir);
else
if(k<=t[Ls(y)].val) split(Ls(x),Ls(y),k,Dir),Rs(x)=Rs(y),Rs(y)=0;
else split(Rs(x),Rs(y),k-t[Ls(y)].val,Dir);
}
set<int> tree;
IT Split(int pos){
IT i=tree.lower_bound(pos);
if(*i==pos) return i;
--i,split(rt[pos],rt[*i],pos-*i,Direc[pos]=Direc[*i]);
return tree.insert(pos).first;
}
void Work(){
n=read(),m=read();
tree.insert(n+1);
for(REG int i=1;i<=n;++i)
Update(rt[i],1,n,read()),tree.insert(i);
for(REG int i=1;i<=m;++i){
int opt=read(),l=read(),r=read();
IT nowl=Split(l),nowr=Split(r+1);
for(IT i=++nowl;i!=nowr;++i) merge(rt[l],rt[*i]);
Direc[l]=opt,tree.erase(nowl,nowr);
}
q=read();
Split(q),Split(q+1);
printf("%d\n",GetPos(rt[q],1,n));
}
int main(){Work();}
|
