Description

定义一个长度为奇数的区间的值为其所包含的的元素的中位数.

现给出$n$个数,求将所有长度为奇数的区间的值排序后,第$k$大的值为多少.

Input

第一行两个数$n$和$k$.第二行$n$个数$a_i$.

Output

一个数表示答案.

Sample Input

4 33 1 2 4

Sample Output

2

HINT

$1\;\leq\;n\;\leq\;10^5,k\;\leq\;$奇数区间的数量，$0\;\leq\;a_i<2^{31}$

Solution

二分答案$ans$,统计长度为奇数的区间的值$\;\geq\;ans$的区间数.

把所有$a_i\;\geq\;ans$的位置标为$1$,所有$a_i<ans$的位置标为$0$,求出前缀和$sum[\;]$.

则值$\;\geq\;ans$的区间$[j,i]$满足条件$sum_i-sum_{j-1}>\frac{i-j+1}{2}$($i,j$同号).

移项得,$2\;\times\;sum_i-i>2\;\times\;sum_{j-1}-(j-1)$.

即用树状数组维护顺序对即可.

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define N 100005using namespace std;typedef long long ll;ll a[N],b[N],k;int s[2][N*3],sum[N],n,m,l,r,mid;inline int lowbit(int x){ return x&(-x);}inline int ask(int k,int j){ int ret=0; for(int i=k;i;i-=lowbit(i)) ret+=s[j][i]; return ret;} inline void add(int k,int j){ for(int i=k;i<=m;i+=lowbit(i)) ++s[j][i];}inline bool chk(ll x){ ll cnt=0LL; memset(s,0,sizeof(s)); for(int i=1;i<=n;++i) if(a[i]>=x) sum[i]=sum[i-1]+1; else sum[i]=sum[i-1]; for(int i=1,tmp;i<=n;++i){ tmp=(sum[i]<<1)-i+n; cnt+=(ll)(ask(tmp,i&1^1)); add(tmp,i&1); if((i&1)&&(sum[i]<<1)-i>=0LL) ++cnt; } return cnt>=k;}inline void init(){ scanf("%d%lld",&n,&k); for(int i=1;i<=n;++i){ scanf("%lld",&a[i]); b[i]=a[i]; } l=1;r=n;m=n*3; sort(b+1,b+1+n); while(l
               
                >1; if(chk(b[mid])) l=mid; else r=mid-1; } printf("%lld\n",b[l]);}int main(){ freopen("kth.in","r",stdin); freopen("kth.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0;}