题解 | #众数#

这有 2000？？？

考虑维护 表示 在 中出现的次数，由于 ，所以我们可以 暴力修改，你再考虑查询等价于先问你 的最大值 ，然后问你最后一个 的位置 ，你考虑把这个东西变成询问最以后一个 的位置 。

我们整理一下，需要支持单点修改，区间最大值、区间最后一个 的位置，不就是裸的线段树上二分啊。

于是线段树上二分即可。代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[1005],cnt[1000005];set<ll> st;
#define ls (u<<1)
#define rs (u<<1|1)
struct seg{
    ll l,r,mx;
}w[4000050];
void up(ll u){
    w[u].mx=max(w[ls].mx,w[rs].mx);
}
void bd(ll u,ll l,ll r){
    w[u].l=l,w[u].r=r;
    if(l==r) return w[u].mx=cnt[l],void(0);
    ll md=(l+r)>>1;
    bd(ls,l,md),bd(rs,md+1,r);
    up(u);
}
ll qry(ll u,ll l,ll r){
    if(l<=w[u].l&&w[u].r<=r) return w[u].mx;
    ll md=(w[u].l+w[u].r)>>1,res=0;
    if(l<=md) res=max(res,qry(ls,l,r));
    if(r>md) res=max(res,qry(rs,l,r));
    return res;
}
ll search(ll u,ll x){
    if(w[u].l==w[u].r){
        if(w[u].mx==x) return w[u].l;
        return -1;
    }
    if(w[rs].mx>=x) return search(rs,x);
    return search(ls,x);
}
void mdf(ll u,ll x,ll v){
    if(w[u].l==w[u].r&&w[u].l==x) return w[u].mx+=v,void(0);
    ll md=(w[u].l+w[u].r)>>1;
    if(x<=md) mdf(ls,x,v);
    else mdf(rs,x,v);
    up(u);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
    bd(1,0,1000001);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(i!=j){
                mdf(1,a[i],-1),mdf(1,a[i]+1,1);
                mdf(1,a[j],-1),mdf(1,a[j]-1,1);
                ll mx=qry(1,0,1000001),rt=search(1,mx);
                st.insert(rt);
                mdf(1,a[i]+1,-1),mdf(1,a[i],1);
                mdf(1,a[j]-1,-1),mdf(1,a[j],1);
            }
        }
    }
    for(auto p:st) cout<<p<<" ";
}