题意：给n个数，求出所有子区间的中位数，组成另外一个序列，求出它的中位数
这里的中位数的定义是：将当前区间排序后，设区间长度为m，则中位数为第m/2+1个数
做法：二分+前缀和+树状数组维护
极其妙的一个做法。
效率$O(nlognlogA)$这里的A指的是原序列中的最大值
二分一下最后的中位数，然后将原序列中大于当前二分出来的值标为1，小于的标为-1，处理出前缀和。
那么只要一段区间的和大于0，那么这段区间的中位数就一定大于等于当前二分出来的值。
所以问题就变成了，求出当前这个序列的顺序对个数（两个数是顺序对，当且仅当$ai<aj,i<j$），用类似于逆序对的方法求
那么做法就很显然了，用树状数组维护一下，单次check的效率就是$O(nlogn)$
要注意的一个点是，这里的树状数组不能有负数，所以得加个1e5强制转正（因为是下标）
至于check的$true$和$false$，如果最后算出来的顺序对个数大于$n*(n-1)/4$那么就是$true$（一共有$n*(n-1)/2$个区间，然后因为我们要求的中位数在中间，所以要再除一次2）
#include <cstdio> #include <cstring> #include <algorithm> #define ll long long #define inf 1<<30 #define il inline #define in1(a) read(a) #define in2(a,b) in1(a),in1(b) #define in3(a,b,c) in2(a,b),in1(c) #define in4(a,b,c,d) in2(a,b),in2(c,d) il void readl(ll &x){ x=0;ll f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=f; } il void read(int &x){ x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=f; } using namespace std; /*===================Header Template=====================*/ #define N 100010 #define lowbit(x) x&-x int c[N*10]; int n,a[N],s[N*10]; void add(int x){ for(int i=x;i<=2*N;i+=lowbit(i))c[i]++; } ll query(int x){ ll sum=0; for(int i=x;i>0;i-=lowbit(i))sum+=c[i]; return sum; } bool check(int x){ for(int i=1;i<=2*N;i++)c[i]=0; s[0]=0; for(int i=1;i<=n;i++) s[i]=s[i-1]+(a[i]>=x?1:-1); ll sum=0; for(int i=0;i<=n;i++){ sum+=query(s[i]+N); add(s[i]+N); } return sum>=1ll*n*(n+1)/4; } int main(){ in1(n); int l=0,r=0; for(int i=1;i<=n;i++){ in1(a[i]); r=max(r,a[i]); } int ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid))l=mid+1; else r=mid-1; } printf("%d ",r); }