#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; void Rd(int&res){ res=0;char c; while(c=getchar(),c<48); do res=res*10+(c&15); while(c=getchar(),c>47); } const int N=100005; int n,m,num[N]; struct Segment_tree{ struct node{ int L,R,sum,flag; }tree[N<<2]; void up(int p){ tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum; } void down(int p){ if(~tree[p].flag){ tree[p<<1].sum=(tree[p<<1].R-tree[p<<1].L+1)*tree[p].flag; tree[p<<1|1].sum=(tree[p<<1|1].R-tree[p<<1|1].L+1)*tree[p].flag; tree[p<<1].flag=tree[p<<1|1].flag=tree[p].flag; tree[p].flag=-1; } } void build(int L,int R,int lim,int p){ tree[p].L=L,tree[p].R=R,tree[p].flag=-1; if(L==R){ if(num[L]>=lim)tree[p].sum=1; else tree[p].sum=0; return; } int mid=L+R>>1; build(L,mid,lim,p<<1); build(mid+1,R,lim,p<<1|1); up(p); } void update(int L,int R,int v,int p){ if(tree[p].L==L&&tree[p].R==R){ tree[p].sum=(R-L+1)*v; tree[p].flag=v; return; } down(p); int mid=tree[p].L+tree[p].R>>1; if(R<=mid)update(L,R,v,p<<1); else if(L>mid)update(L,R,v,p<<1|1); else update(L,mid,v,p<<1),update(mid+1,R,v,p<<1|1); up(p); } int query(int L,int R,int p){ if(tree[p].L==L&&tree[p].R==R)return tree[p].sum; down(p); int mid=tree[p].L+tree[p].R>>1; if(R<=mid)return query(L,R,p<<1); else if(L>mid)return query(L,R,p<<1|1); else return query(L,mid,p<<1)+query(mid+1,R,p<<1|1); } }T; int op[N],a[N],b[N],pos; bool check(int lim){ T.build(1,n,lim,1); for(int i=1;i<=m;i++){ int cnt_1=T.query(a[i],b[i],1); int cnt_0=b[i]-a[i]+1-cnt_1; if(op[i]==1){ if(cnt_1)T.update(a[i],a[i]+cnt_1-1,1,1); if(cnt_0)T.update(b[i]-cnt_0+1,b[i],0,1); }else{ if(cnt_0)T.update(a[i],a[i]+cnt_0-1,0,1); if(cnt_1)T.update(b[i]-cnt_1+1,b[i],1,1); } } return T.query(pos,pos,1); } int main(){ Rd(n),Rd(m); for(int i=1;i<=n;i++) Rd(num[i]); for(int i=1;i<=m;i++) Rd(op[i]),Rd(a[i]),Rd(b[i]); Rd(pos); int L=1,R=n,res=-1; while(L<=R){ int mid=L+R>>1; if(check(mid)){ res=mid; L=mid+1; }else R=mid-1; } printf("%d\n",res); return 0; }
|