本题采用线段树,将排序的操作巧妙转化为0/1序列的区间覆盖问题
首先我们先二分最终答案(ans)
之所以答案有单调性,是因为我们进行了如下转换
-
将原序列(A)变为0/1序列(A'),若(a_i < ans) 则 (a'_i = 0) 否则 (a'_i = 1),z这样我们就得到了0/1序列(A')
-
将操作转换为区间覆盖: 设操作区间为([l,r]),操作符为(opt),首先统计区间(1)的个数,若为升序排序,则区间([l,r-x])覆盖为(0),区间([r-x+1,r])覆盖为(1);若为降序排序,则区间([l,l+x-1])覆盖为(1),区间([l+x,r])覆盖为(0). 这样排序本质上只是把两类不同的数区分开来,并不是真正的排序,因此复杂度优秀.
3.操作结束后,查询(pos)位的值((pos)即为题目要求查询的位置),是(0)还是(1).若为(0),说明(ans)过大,返回(r=mid-1),否则返回(ans=mid,l=mid+1)
答案的单调性,是因为原序列一定,操作一定,所以(pos)位上最终的数是确定唯一的,这个数同时又在([1,n])的区间内,因此可以二分答案,并用以上转化进行(check)
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ls (nod<<1)
#define rs (nod<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
int read(){
int x=0; char c; int flag=1;
for(c=getchar();!isdigit(c);c=getchar()) if(c=='-') flag=-1;
for(;isdigit(c);c=getchar()) x=((x+(x<<2))<<1)+(c^48);
return x*flag;
}
const int N=1e5+10;
int n,m,pos;
int a[N];
struct operation{
int opt,l,r;
}b[N];
struct node{
int l,r,len;
int s[2];
int tag;
}t[N<<2];
void pushup(int nod){
for(int i=0;i<=1;i++) t[nod].s[i]=t[ls].s[i]+t[rs].s[i];
}
void pushdown(int nod){
if(t[nod].tag==-1) return ;
int v=t[nod].tag; t[nod].tag=-1;
t[ls].s[v]=t[ls].len; t[ls].s[1-v]=0;
t[rs].s[v]=t[rs].len; t[rs].s[1-v]=0;
t[ls].tag=t[rs].tag=v;
}
void build(int nod,int l,int r,int d){
t[nod].l=l,t[nod].r=r,t[nod].len=r-l+1;
t[nod].s[0]=t[nod].s[1]=0;
t[nod].tag=-1;
if(l==r){
t[nod].s[a[l]>=d]=1;
return ;
}
build(lson,d); build(rson,d);
pushup(nod);
}
void update(int nod,int l,int r,int ll,int rr,int v){
if(ll>rr) return ;
if(l==ll&&r==rr){
t[nod].s[v]=t[nod].len; t[nod].s[1-v]=0;
t[nod].tag=v;
return ;
}
pushdown(nod);
if(rr<=mid) update(lson,ll,rr,v);
else if(ll>mid) update(rson,ll,rr,v);
else update(lson,ll,mid,v),update(rson,mid+1,rr,v);
pushup(nod);
}
int query(int nod,int l,int r,int ll,int rr){
if(ll>rr) return 0;
if(l==ll&&r==rr) return t[nod].s[1];
pushdown(nod);
if(rr<=mid) return query(lson,ll,rr);
else if(ll>mid) return query(rson,ll,rr);
else return query(lson,ll,mid)+query(rson,mid+1,rr);
}
int check(int d){
build(1,1,n,d);
//cout<<"ok1"<<endl;
for(int i=1;i<=m;i++){
int x=query(1,1,n,b[i].l,b[i].r);
//cout<<"ok2"<<endl;
if(b[i].opt){
update(1,1,n,b[i].l,b[i].l+x-1,1);
update(1,1,n,b[i].l+x,b[i].r,0);
}else{
update(1,1,n,b[i].l,b[i].r-x,0);
update(1,1,n,b[i].r-x+1,b[i].r,1);
}
//cout<<"ok3"<<endl;
}
return query(1,1,n,pos,pos);
}
signed main() {
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++){
b[i].opt=read(),b[i].l=read(),b[i].r=read();
}
pos=read();
int l=1,r=n,ans=-1;
while(l<=r){
int Mid=(l+r)>>1;
if(check(Mid)) { ans=Mid; l=Mid+1; }
else r=Mid-1;
}
printf("%d",ans);
return 0;
}