题目大意：定义一个长度为奇数的区间的值为其所包含的的元素的中位数。现给出$n$个数的集合$a$，求将所有长度为奇数的区间的值排序后，第$K$大的值为多少。
思路：
考场上的我没有思路，于是弱智的我只会$60pts$主席树。
正解：
发现将数列排序后，所求的答案具有单调性。于是可以二分答案。
但是如何很快的求出一个区间的中位数呢？
我们可以将数列里大于当前二分查找的值的数置为1，等于的置为0，小于的置为-1。
这样，一个区间的和如果是0，中位数就是二分查找的数。
所以用树状数组维护区间和就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) x&-x using namespace std; int c[500005][2]; int a[500005],b[500005],d[500005]; int sum[500005]; int del=100005; int n,m; void add(int x,int num,int opt) { int i; for(i=x;i<=500000;i+=lowbit(i)) c[i][opt]+=num; } int query(int x,int opt) { int sum=0; for(int i=x;i;i-=lowbit(i)) sum+=c[i][opt]; return sum; } int check(int k) { memset(c,0,sizeof(c)); int i; int num1=0,num2=0; add(del,1,0); for(i=1;i<=n;i++) { if(a[i]<k) d[i]=-1; else if(a[i]==k) d[i]=0; else d[i]=1; sum[i]=sum[i-1]+d[i]; add(sum[i]+del,1,i%2); num1+=query(sum[i]+del,(i%2)^1)-query(sum[i]+del-1,(i%2)^1); num2+=query(sum[i]+del-1,(i%2)^1); } if(m>num1+num2) return 1; else if(m<num2) return 0; return 2; } int main() { freopen("Kth.in","r",stdin); freopen("Kth.out","w",stdout); scanf("%d%d",&n,&m); int i,j,l,r; for(i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); l=1; r=n; while(l<=r) { int mid=(l+r)>>1; int tmp=check(b[mid]); if(tmp==1) r=mid-1; else if(tmp==0) l=mid+1; else { cout<<b[mid]; break; } } }