P2824 [HEOI2016/TJOI2016]排序

链接:Miku

----------------------------

一道二分+线段树

-----------------------------

显然暴力模拟会T飞,可以用二分解决

-----------------------------

二分啥呢?二分mid与最后在q的位置的数的大小

但是怎么知道大还是小呢,既然我们只想要知道大还是小,那么那个点原来是

多大/多小是没有意义的,只有和mid的相对大小,那么我们就把比mid大的改成1,小于等于的改为0

然后进行排序

这样仅仅是不行的,对于排序,因为已经变成了0和1,那么我们只要知道区间1的个数就行了,然后把1都放到最前面/最后面即可

这个查询和修改可以用线段树来实现

----------------------------------

![]()![]()```

include<iostream>

include<cstdio>

include<algorithm>

using namespace std;
int n;
int m;
int l,r;
int mid;
int a[100005];
int b[100005];
int sum[400005];
int lazy[400005];
int q;
int f;
struct ch{
int l;
int r;
int f;
}change[100005];
void pushup(int x){
sum[x]=sum[x<<1]+sum[x<<1|1];
}
void pushdown(int x,int l,int r){
if(lazy[x]!=-1){
int mid=(l+r)>>1;
lazy[x<<1]=lazy[x];
lazy[x<<1|1]=lazy[x];
sum[x<<1]=lazy[x](mid-l+1);
sum[x<<1|1]=lazy[x]
(r-mid);
lazy[x]=-1;
return ;
}
return ;
}
void update(int x,int l,int r,int L,int R,int d){
if (L > R) return;
if(L<=l&&r<=R){
sum[x]=d(r-l+1);
lazy[x]=d;
return ;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(L<=mid) update(x<<1,l,mid,L,R,d);
if(R>mid) update(x<<1|1,mid+1,r,L,R,d);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return sum[x];
}
pushdown(x,l,r);
int mid=(l+r)>>1;
int ans=0;
if(L<=mid) ans+=query(x<<1,l,mid,L,R);
if(R>mid) ans+=query(x<<1|1,mid+1,r,L,R);
return ans;
}
bool check(int k){
for(int i=1;i<=4
n;++i){//每一次都要初始化
lazy[i]=-1;
sum[i]=0;
}
for(int i=1;i<=n;++i){
if(a[i]>=k){
update(1,1,n,i,i,1);//初始化
}
}
for(int i=1;i<=m;++i){
if(change[i].f==0){
int cnt=query(1,1,n,change[i].l,change[i].r);//只有0,1的排序
update(1,1,n,change[i].r-cnt+1,change[i].r,1);
update(1,1,n,change[i].l,change[i].r-cnt,0);
}
else{
int cnt=query(1,1,n,change[i].l,change[i].r);
update(1,1,n,change[i].l+cnt,change[i].r,0);
update(1,1,n,change[i].l,change[i].l+cnt-1,1);
}
}
if(query(1,1,n,q,q)){//查询一下大了还是小了
return 1;
}
return 0;
}
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",&change[i].f,&change[i].l,&change[i].r);
}
scanf("%d",&q);
l=1;//l永远成立
r=n+1;//r永不成立
while(r-l>1){//当然要小于1最后
mid=(l+r)>>1;
if(check(mid)){
l = mid;
}
else{
r = mid;
}
}
cout<<l;
return 0;
}



Ac

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。