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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include<bits/stdc++.h>
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define PII pair<int,int>
const int MOD=998244353;
const int N=10000002;
const int M=10000001;
using namespace std;
inline int read(){register char c=getchar();register int s=0,f=1;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-'0';return s*f;}
int n,m,q;
int a[N],f[N];
int t[N],l[N],r[N];
struct node{
int l,r,d,add;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define d(x) tr[x].d
#define add(x) tr[x].add
} tr[N];
void build(int p,int l,int r){
l(p)=l,r(p)=r,add(p)=2;
if(l==r){
d(p)=f[l];
return ;
};
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
d(p)=d(p*2)+d(p*2+1);
}
inline void pushdown(int p){
if(add(p)!=2){
d(p*2)=add(p)*(r(p*2)-l(p*2)+1);
d(p*2+1)=add(p)*(r(p*2+1)-l(p*2+1)+1);
add(p*2)=add(p*2+1)=add(p);
add(p)=2;
}
}
void change(int p,int l,int r,int d){
if(l<=l(p)&&r(p)<=r){
add(p)=d;
d(p)=d*(r(p)-l(p)+1);
return ;
}
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid)change(p*2,l,r,d);
if(r>mid)change(p*2+1,l,r,d);
d(p)=d(p*2)+d(p*2+1);
}
int asksum(int p,int l,int r){
if(l<=l(p)&&r(p)<=r) return d(p);
pushdown(p);
int mid=(l(p)+r(p))>>1;
int ans=0;
if(l<=mid)ans+=asksum(p*2,l,r);
if(r>mid)ans+=asksum(p*2+1,l,r);
return ans;
}
int ask(int p,int k){
if(l(p)==r(p)) return d(p);
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(k<=mid)return ask(p*2,k);
else return ask(p*2+1,k);
}
int ll,rr;
bool check(int mid){
for(int i=1;i<=n;i++){
f[i]=(a[i]>=mid);
}
build(1,1,n);
for(int i=1;i<=m;i++){
if(!t[i]){
int sum=asksum(1,l[i],r[i]);
change(1,l[i],r[i]-sum,0);
change(1,r[i]-sum+1,r[i],1);
}
else {
int sum=asksum(1,l[i],r[i]);
change(1,l[i],l[i]+sum-1,1);
change(1,l[i]+sum,r[i],0);
}
}
return ask(1,q);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)t[i]=read(),l[i]=read(),r[i]=read();
q=read();
ll=1,rr=n;
while(ll<=rr){
int mid=(ll+rr)>>1;
if(check(mid))ll=mid+1;
else rr=mid-1;
}
printf("%d",ll-1);
return 0;
}
|