51 NOD 1685 第K大区间2 二分+BIT

时间:2024-10-14 18:35:44

题目描述:

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

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

  样例解释:

  [l,r]表示区间的值
  [1]:3
  [2]:1
  [3]:2
  [4]:4
  [1,3]:2
  [2,4]:2

  第三大是2

输入:

  第一行两个数n和k(1<=n<=100000,k<=奇数区间的数量) 第二行n个数,0<=每个数<2^31

输出:

  一个数表示答案。

题解:

  二分答案t,统计中位数大于等于t的区间有多少个。

   设a[i]为前i个数中有a[i]个数>=t,若奇数区间[l,r]的中位数>=t,

  则(a[r]-a[l-1])*2>=r-l+1,即(a[r]*2-r)>=(a[l-1]*2-l+1)。

  b[i]=a[i]*2-i,

  这样题目就变成了统计 b[i]>=b[j] i与j奇偶性不同,BIT

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+, M = 1e5+, mod = 1e9+, inf = 2e9;
typedef long long ll; int C[N][],n;
int a[N],b[N];
ll k;
void update(int x,int p) {
if(x==) return ;
for(int i=x;i<N;i+=i&(-i)) C[i][p]+=;
}
int getsum(int x,int p) {
int s = ;
for(int i=x;i;i-=i&(-i)) s+=C[i][p];
return s;
}
ll ask(int t)
{
memset(C,,sizeof(C));
b[]=;
for(int i=;i<=n;i++) b[i]=a[i]>=t?:,b[i]+=b[i-];
for(int i=;i<=n;i++) b[i] = b[i]*-i+M;
ll s=;
update(M,);
for(int i=;i<=n;i++) {
s+=getsum(b[i],(i&)^);
update(b[i],(i&));
}
return s;
}
int main(){
scanf("%d%lld",&n,&k);
int mx = ;
for(int i=;i<=n;i++) scanf("%d",&a[i]),mx = max(mx, a[i]);
int l=,r=mx,ans=;
// cout<<ask(2)<<endl;//return 0;
while(l<=r) {
int mid = (l+r)>>;
if(ask(mid)>=k) l=mid+,ans=mid;
else r=mid-;
}
printf("%d\n",ans);
}