给一个\(1 \sim n\)的排列，进行\(m\)次操作，可以将一个区间\([l,r]\)内的数升序排序或者降序排序，最后进行一次询问问第\(k\)个数字为多少。

Solution

二分答案，对于每一个二分的值\(x\)，将原排列中小于等于\(x\)的数视为\(0\)，大于\(x\)的树视为\(1\)，用线段树维护，排序操作可以用线段树的区间赋值实现。

/* Author: LargeDumpling Email: LargeDumpling@qq.com Edit History:    2018-07-24  File created.*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN=100050;struct jz{ int l,r,typ;}O[MAXN];int num[MAXN],sum[MAXN<<2],tag[MAXN<<2],L[MAXN<<2],R[MAXN<<2],n,m,k;void maintain(int root){ sum[root]=sum[root<<1]+sum[root<<1|1]; return;}void build(int root,int l,int r,int x){ L[root]=l; R[root]=r; tag[root]=-1; if(l==r) { sum[root]=(num[l]<=x)?0:1; return; } int mid=(l+r)>>1; build(root<<1,l,mid,x); build(root<<1|1,mid+1,r,x); maintain(root); return;}void down(int root){ if(tag[root]==-1) return; sum[root<<1]=tag[root]*(R[root<<1]-L[root<<1]+1); tag[root<<1]=tag[root]; sum[root<<1|1]=tag[root]*(R[root<<1|1]-L[root<<1|1]+1); tag[root<<1|1]=tag[root]; tag[root]=-1; return;}void change(int root,int l,int r,int x){ if(r
          
           >1; if(l<=mid) change(root<<1,l,r,x); if(mid
           
            >1; if(l<=mid) ans+=query(root<<1,l,r); if(mid
            
             >1; if(check(mid)) r=mid; else l=mid; } printf("%d\n",r); fclose(stdin); fclose(stdout); return 0;}
            
           
          
         
        
       
      
     
    

Other thing

傅大爷数据出的太好了，把我原来线段树的写法卡疯了。