【二分答案】【平衡树】Atcoder ARC101D Median of Medians

分析：

答案的单调性是显然的，所以可以二分答案，把最值问题转化为判定性问题。

现在要求的就是：满足区间的中位数不超过$x$的区间数量。（x为我们二分的值）

定义一个$p$数组，满足$p_i=p_{i-1}+[a_i>x]$
说白了就是求出：前i个数中有多少个超过了x

那么如果一个序列满足条件，就可以转化为满足这个式子：
$r-l>2\times (p_r-p_l)$
注意，由于题目鬼扯的中位数定义，这里必须是严格大于。

这个式子的意思就是：这个区间中，大于x的数不会达到一半。

但这个式子跟两个位置的值有关，所以需要转化一下：
$r-2\times p_r>l-2\times p_l$

这样两边都只跟一个位置的值有关了。

所以可以用一个平衡树，存储在每个位置的$i-2\times p_i$，在它前面找小于它的值的个数，就是以i为右端点，且满足条件的区间数。

注意。。。区间总数会爆int。。。。（为了这个wa了3次。。。）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#define SF scanf
#define PF printf
#define MAXN 100010
#define INF 0x3FFFFFFF
using namespace std;
typedef long long ll;
int a[MAXN],p[MAXN];
ll n;
struct node *NIL;
struct node{node *ch[2],*fa;int val,sum,num;bool Dir(){return this==fa->ch[1];}void setchild(node *x,int d){ch[d]=x;if(x!=NIL)x->fa=this;}void pushup(){//pushdown();//if(x->ch[0]!=NIL)x->ch[0]->pushdown();//if(x->ch[1]!=NIL)x->ch[1]->pushdown();sum=ch[0]->sum+ch[1]->sum+num;}
}tree[MAXN],*root,*ncnt;
node * Newnode(node *x,int val){x->ch[0]=x->ch[1]=x->fa=NIL;x->val=val;x->sum=x->num=1;return x;
}
void Rotate(node *x){node *y=x->fa;//y->pushdown(),x->pushdown();int d=x->Dir();if(y==root)root=x,x->fa=NIL;elsey->fa->setchild(x,y->Dir());y->setchild(x->ch[!d],d);x->setchild(y,!d);y->pushup();
}
void Splay(node *x,node *rt){//x->pushdown();while(x->fa!=rt){node *y=x->fa;if(y->fa==rt){Rotate(x);break;}if(x->Dir()==y->Dir())Rotate(y);elseRotate(x);Rotate(x);}x->pushup();
}
void Ins(node *&root,int val){if(root==NIL){root=Newnode(++ncnt,val);return ;}node *y=root;int d;while(1){y->sum++;if(y->val==val){y->num++;Splay(y,NIL);return ;}d=(y->val)<val;if(y->ch[d]==NIL)break;y=y->ch[d];}y->setchild(Newnode(++ncnt,val),d);Splay(y->ch[d],NIL);
}
node *find(node *x,int val){if(x->val==val)return x;return find(x->ch[(x->val)<val],val);
}
ll check(int x){ncnt=root=NIL;for(int i=1;i<=n;i++)p[i]=0;for(int i=1;i<=n;i++)p[i]=p[i-1]+(a[i]>x)*2;ll res=0;Ins(root,0);for(int i=1;i<=n;i++){Ins(root,i-p[i]);node *x=find(root,i-p[i]);Splay(x,NIL);res+=x->ch[0]->sum;}return res;
}
int main(){NIL=&tree[0];NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;root=ncnt=NIL;SF("%lld",&n);for(int i=1;i<=n;i++)SF("%d",&a[i]);int l=1,r=INF,ans=INF;while(l<=r){int mid=(l+r)>>1;if(check(mid)<(n*(n+1ll)/4ll+1ll))l=mid+1;else{ans=mid;r=mid-1;}}PF("%d",ans);
}