2023牛客暑假多校4

F

假设目前最小值为 $L$ ，最大值为 $R$ ，$Mid=\lfloor\dfrac{L+R}{2}\rfloor$ 。

每次只需比较 $[L,Mid]$ 内数的数量 $lcnt$ 与 $[Mid+1,R]$ 内数的数量 $rcnt$ 即可。

若 $lcnt\ge rcnt$ ，则将 R 的数量减少 1 ，反之则将 L 的数量减少 1 。

于是可用离散化+线段树来维护。

代码

#include<bits/stdc++.h>
#define N 1000010

using namespace std;

int n,a[N],head,tail;

struct qwid{
    int x,id;
    bool operator < (const qwid &y) const{
        return x<y.x;
    }
}q[N];
vector<qwid> tmp;
vector<int> ttmp;
void discrete() {
     sort(tmp.begin(),tmp.end());
    int t=tmp.size();
    for(int i=0;i<t;i++) {
        q[i+1].id=tmp[i].id;
        q[i+1].x=tmp[i].x;
        ttmp.push_back(tmp[i].x);
    }
    t=unique(ttmp.begin(),ttmp.end())-ttmp.begin();
}

int get_val(int x) {
    return lower_bound(ttmp.begin(),ttmp.end(),x)-ttmp.begin()+1;
}

struct SegmentTree{
    struct node{
        int sum;
    }nod[N<<2];
    #define s(x) nod[x].sum
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
    void modify(int p,int l,int r,int x,int y) {
        if(l>x||r<x) return ;
        if(l==r) {
            s(p)+=y;
            return ;
        }
        modify(ls,l,mid,x,y),modify(rs,mid+1,r,x,y);
        update(p);
    }
    int ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
    }
}SMT;

void work() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        tmp.push_back(qwid{a[i],i});
    }
    discrete();
    for(int i=1;i<=n;i++) SMT.modify(1,1,n,get_val(a[i]),1);
    int now=1,ans=1;
    head=1,tail=n;
    while(head<tail) {
        int hd=get_val(q[head].x),ta=get_val(q[tail].x),md=upper_bound(ttmp.begin(),ttmp.end(),(q[head].x+q[tail].x)/2)-ttmp.begin();
        int lcnt=SMT.ask(1,1,n,hd,md),rcnt=SMT.ask(1,1,n,md+1,ta);
        if(lcnt>=rcnt) {
            tail--;
            SMT.modify(1,1,n,ta,-1);
        }
        else{
            head++;
            SMT.modify(1,1,n,hd,-1);
        }
    }
    cout<<q[head].id<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}