题面
分析
此题是道好题！
首先要跳出思维定势，不是去想如何用数据结构去直接维护排序过程，而是尝试二分a[p]的值
设二分a[p]的值为x
我们将大于x的数标记为1，小于等于x的数标记为0
则整个序列只由01组成,记为b
将一个区间升序排序，则相当于将1全部移到右边,0全部移到左边，降序排序反之
例：
a={1,6,5,2,4,3}.x=4
标记后的序列b为{0,1,1,0,0,0}
此时对[1,5]进行升序排序,a={1,2,4,5,6,3}
标记后的序列b为{0,0,0,1,1,0}
因此可以用线段树维护标记后的序列，直接区间求和得到1的个数，再区间更新即可
如果排完序后b[p]=0,则说明a[p]<=x,继续减小x
否则增大x
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,m,qa;
struct node {
int l;
int r;
int v;
int mark;
int len() {
return r-l+1;
}
} tree[maxn<<2];
int a[maxn];
struct sort_seg {
int l;
int r;
int type;
} q[maxn];
void push_up(int pos) {
tree[pos].v=tree[pos<<1].v+tree[pos<<1|1].v;
}
void build(int l,int r,int pos,int middle) {
tree[pos].l=l;
tree[pos].r=r;
tree[pos].v=0;
tree[pos].mark=-1;
if(l==r) {
tree[pos].v=(a[l]>middle);
return;
}
int mid=(tree[pos].l+tree[pos].r)>>1;
build(l,mid,pos<<1,middle);
build(mid+1,r,pos<<1|1, middle);
push_up(pos);
}
void push_down(int pos) {
if(tree[pos].mark!=-1) {
tree[pos<<1].mark=tree[pos].mark;
tree[pos<<1|1].mark=tree[pos].mark;
tree[pos<<1].v=tree[pos].mark*tree[pos<<1].len();
tree[pos<<1|1].v=tree[pos].mark*tree[pos<<1|1].len();
tree[pos].mark=-1;
}
}
void update(int L,int R,int v,int pos) {
if(R<tree[pos].l||L>tree[pos].r) return;
if(L<=tree[pos].l&&R>=tree[pos].r) {
tree[pos].v=v*tree[pos].len();
tree[pos].mark=v;
return;
}
push_down(pos);
int mid=(tree[pos].l+tree[pos].r)>>1;
if(L<=mid) update(L,R,v,pos<<1);
if(R>mid) update(L,R,v,pos<<1|1);
push_up(pos);
}
int query(int L,int R,int pos) {
if(R<tree[pos].l||L>tree[pos].r) return 0;
if(L<=tree[pos].l&&R>=tree[pos].r) {
return tree[pos].v;
}
push_down(pos);
int mid=(tree[pos].l+tree[pos].r)>>1;
int ans=0;
if(L<=mid) ans+=query(L,R,pos<<1);
if(R>mid) ans+=query(L,R,pos<<1|1);
return ans;
}
int check(int x) {
build(1,n,1,x);
for(int i=1; i<=m; i++) {
int sum=query(q[i].l,q[i].r,1);
if(q[i].type==0) {
update(q[i].l,q[i].r-sum,0,1);
update(q[i].r-sum+1,q[i].r,1,1);
} else {
update(q[i].l,q[i].l+sum-1,1,1);
update(q[i].l+sum,q[i].r,0,1);
}
}
if(query(qa,qa,1)==1) return 0;
else return 1;
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
for(int i=1; i<=m; i++) {
scanf("%d %d %d",&q[i].type,&q[i].l,&q[i].r);
}
int l=1,r=n;
int ans=n+1;
scanf("%d",&qa);
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) {
ans=min(ans,mid);
r=mid-1;
} else {
l=mid+1;
}
}
printf("%d
",ans);
}