BZOJ4552：[HEOI2016/TJOI2016]排序—

BZOJ4552：[HEOI2016/TJOI2016]排序——题解

阅读量：6141 次

发布时间：2019-06-21

本文共 2290 字，大约阅读时间需要 7 分钟。

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

听说你用桶排过了这道题？

听说这是一道套路题？

（好的啥也不会的我瑟瑟发抖……）

那让我讲一遍套路吧。

当序列变成01序列的时候，利用线段树即可O(logn)局部排序（就是变成了区间查询1的个数，然后左右区间修改为0/1）

我们利用这个性质，二分答案mid，则大于等于mid的数为1，小于的为0，进行排序后看q位置是否为1即可。

正确性很好证，设答案为k，则mid>k时p位置一定为0，否则一定为1.

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef double dl;const int N=1e5+5;inline int read(){    int X=0,w=0;char ch=0;    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();    return w?-X:X;}struct data{    int op,l,r;}q[N];int n,m,p,b[N],c[N];int tr[N*4],lazy[N*4];inline void push(int a,int l,int r){    if(lazy[a]==-1)return;    int mid=(l+r)>>1;    tr[a<<1]=(mid-l+1)*lazy[a];tr[a<<1|1]=(r-mid)*lazy[a];    lazy[a<<1]=lazy[a<<1|1]=lazy[a];    lazy[a]=-1;}inline void build(int a,int l,int r){    if(l==r){        tr[a]=c[l];        return;    }    int mid=(l+r)>>1;    build(a<<1,l,mid);build(a<<1|1,mid+1,r);    tr[a]=tr[a<<1]+tr[a<<1|1];}inline int query(int a,int l,int r,int l1,int r1){    if(r
          
           
            >1; push(a,l,r); return query(a<<1,l,mid,l1,r1)+query(a<<1|1,mid+1,r,l1,r1);}inline void modify(int a,int l,int r,int l1,int r1,int w){ if(r
            
             
              >1; push(a,l,r); modify(a<<1,l,mid,l1,r1,w);modify(a<<1|1,mid+1,r,l1,r1,w); tr[a]=tr[a<<1]+tr[a<<1|1];}bool check(int k){ memset(lazy,-1,sizeof(lazy)); for(int i=1;i<=n;i++) if(b[i]>=k)c[i]=1; else c[i]=0; build(1,1,n); for(int i=1;i<=m;i++){ int l=q[i].l,r=q[i].r; int cnt=query(1,1,n,l,r); if(!q[i].op){ modify(1,1,n,l,r-cnt,0); modify(1,1,n,r-cnt+1,r,1); }else{ modify(1,1,n,l,l+cnt-1,1); modify(1,1,n,l+cnt,r,0); } } return query(1,1,n,p,p);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)b[i]=read(); for(int i=1;i<=m;i++){ q[i].op=read(),q[i].l=read(),q[i].r=read(); } p=read(); int l=1,r=n; while(l
              
               >1; if(check(mid))l=mid; else r=mid-1; } printf("%d\n",l); return 0;}