P2839 [国家集训队]middle

---

好妙的题啊，，，，

首先二分一个答案k，把数列里>=k的数置为1，=0就是k>=中位数，<0就是k<中位数

数列的最大和很好求哇

左边的最大后缀+中间+右边的最大前缀

主席树搞搞

完事了

// It is made by XZZ#include
    
     #include
     
      #define il inline#define rg register#define vd void#define sta staticusing namespace std;il int gi(){    rg int x=0,f=1;rg char ch=getchar();    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x*f;}const int maxn=20010;int a[maxn],b[maxn];const int maxd=500001;struct node{    int tot,lmax,rmax;    node operator+(const node&x)const{        return (node){tot+x.tot,max(lmax,tot+x.lmax),max(x.rmax,rmax+x.tot)};    }}s[maxd];int rt[maxn],ls[maxd],rs[maxd],id;struct yyb{int p,a;}c[maxn];il bool operator<(const yyb&a,const yyb&b){return a.a
      
       >1)il vd build(int&x,int l,int r){    x=++id;    s[x]=(node){r-l+1,r-l+1,r-l+1};    if(l==r)return;    build(ls[x],l,mid),build(rs[x],mid+1,r);}il vd update(int&x,int l,int r,const int&p,const int&o){    ++id,ls[id]=ls[x],rs[id]=rs[x],s[id]=s[x];    x=id;    if(l==r){s[x]=(node){o,o,o};return;}    if(p<=mid)update(ls[x],l,mid,p,o);    else update(rs[x],mid+1,r,p,o);    s[x]=s[ls[x]]+s[rs[x]];}il node query(const int&x,int l,int r,const int&L,const int&R){    if(L>R)return(node){0,0,0};    if(L<=l&&r<=R)return s[x];    if(L<=mid)        if(mid
       
        >1)+1;            sum=query(rt[mid],1,n,l1,r1).rmax+query(rt[mid],1,n,l2,r2).tot+query(rt[mid],1,n,l3,r3).lmax;            (sum>=0)?l=mid:r=mid-1;        }        printf("%d\n",lst=b[l]);    }    return 0;}