真的是假的吗?

题解 P2824 【[HEOI2016/TJOI2016]排序】
题解

首先,这道题只有一组查询,所以可以二分这个数的排名

每次二分一个要查询的数在序列中的大小排名

(排名指在升序的情况下的排名)

然后当val[i] >= mid 此位置就为1 反之则为0 这样一来,这道题就变成了一个01序列排序,所以就可以用线段树实现logn排序

线段树维护区间和,需要实现区间覆盖

每次排序前先查询排序一共有多少1

升序排序则将r-区间1的数量+1~r改为1 l~ r-区间1的数量改为0

最后再查询要询问的位置

若要查询的位置为1,那么就增加ta的排名(r=mid-1)

反之,就降低这个数排名

由于这个数列是1~n的全排列,所以二分出的结果就是答案

不过好像这题暴力给分挺多的,好像暴力能到80


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
# define ls now<<1
# define rs now<<1|1
const int M = 30005 ;
using namespace std;
inline int read(){
    char c=getchar(); int x=0,w=1;
    while(c>'9'||c<'0'){
        if(c=='-') w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*w;
}
struct Q{
    int opt,l,r;
}q[M];
int n,m,st[M],val[M],tag[M<<2],tree[M<<2],K;
inline void pushup(int now){
    tree[now]=tree[ls]+tree[rs];
}
void build(int l,int r,int now){
    tag[now]=-1;
    if(l==r){
        tree[now]=st[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls); build(mid+1,r,rs);
    pushup(now);
}
inline void pushdown(int now,int l,int r){
    if(tag[now]<0) return ;
    tag[ls]=tag[rs]=tag[now];
    tree[ls]=tag[now]*l; tree[rs]=tag[now]*r;
    tag[now]=-1;
}
void change(int L ,int R ,int val,int l,int r,int now){
    if(l>R||r<L) return ;
    if(l>=L&&r<=R){
        tree[now]=val*(r-l+1);
        tag[now]=val; return ;
    }
    int mid=(l+r)>>1;
    pushdown(now,mid-l+1,r-mid);
    change(L,R,val,l,mid,ls);
    change(L,R,val,mid+1,r,rs);
    pushup(now);
}
int query(int L, int R,int l,int r,int now){
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return tree[now];
    int mid=(l+r)>>1;
    pushdown(now,mid-l+1,r-mid);
    int Ans=0;
    Ans+=query(L, R, l,mid,ls);
    Ans+=query(L, R, mid+1,r,rs);
    return Ans;
}
inline int judge(int mid){
    for(register int i=1;i<=n;++i)
      if(val[i]>=mid) st[i]=1;
      else st[i]=0;
    build(1,n,1);
    for(register int i=1;i<=m;++i){
        int l =q[i].l, r= q[i].r ;
        if(q[i].opt==0){
        // 升序排列 
            int num1=query(l,r,1,n,1);
            change(r-num1+1,r,1,1,n,1);
            change(l,r-num1,0,1,n,1);
        }
        else{
        //  降序排列
            int num1=query(l,r,1,n,1);
            change(l,l+num1-1,1,1,n,1);
            change(l+num1,r,0,1,n,1);
        }
    }
    int tmp=query(K,K,1,n,1);
    return tmp;
}
int main(){
    n=read(); m=read();
    for(register int i=1;i<=n;++i) val[i]=read();
    for(register int i=1;i<=m;++i){
        q[i].opt=read(); q[i].l=read(); q[i].r=read();
    }
    K = read() ;
    int L=1 , R=n , Ans=0;
    while(L<=R){
        int mid=(L+R)>>1;
        if(judge(mid))  L=mid+1,Ans=mid ;
        else  R=mid-1;
    }
    printf("%d\n",Ans);
    return 0;
}
评论