D题线段树解法

感觉线段树好写一点，set一直错......

权值线段树存众数，然后不断更新就行了

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e4 + 7;
typedef pair<int, int> PII;
int a[N], b[3 * N];
PII tr[4 * N];
map<int, int> mp1, mp;

void build (int l, int r, int p) {
    if (l == r) {
        tr[p] = {l, mp[l]};
        return;
    }
    int mid = l + r >> 1;
    build (l, mid, p << 1);
    build (mid + 1, r, p << 1 | 1);
    if (tr[p << 1].second > tr[p << 1 | 1].second) tr[p] = tr[p << 1];
    else if (tr[p << 1].second < tr[p << 1 | 1].second) tr[p] = tr[p << 1 | 1];
    else {
        if (tr[p << 1].first > tr[p << 1 | 1].first) tr[p] = tr[p << 1];
        else tr[p] = tr[p << 1 | 1];
    }
}

void update (int l, int r, int x, int k, int p) {
    if (l == r) {
        tr[p].second += k;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(l, mid, x, k, p << 1);
    else update(mid + 1, r, x, k, p << 1 | 1);
    
    if (tr[p << 1].second > tr[p << 1 | 1].second) tr[p] = tr[p << 1];
    else if (tr[p << 1].second < tr[p << 1 | 1].second) tr[p] = tr[p << 1 | 1];
    else {
        if (tr[p << 1].first > tr[p << 1 | 1].first) tr[p] = tr[p << 1];
        else tr[p] = tr[p << 1 | 1];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
        b[i + n] = a[i] - 1;
        b[i + 2 * n] = a[i] + 1;
        mp1[a[i]]++;
    }
    
    int m = 3 * n;
    sort (b + 1, b + 1 + m);
    m = unique(b + 1, b + 1 + m) - (b + 1);
    
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b + 1, b + 1 + m, a[i]) - b;
        mp[x] = mp1[a[i]];
        a[i] = x;
    }
    //for (int i = 1; i <= m; i++) cout << b[i] << " \n"[i == m];
    sort (a + 1, a + 1 + n);
    
    set<int> st;
    build (0, N, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            update(0, N, a[i], -1, 1);
            update(0, N, a[j], -1, 1);
            update(0, N, a[i] + 1, 1, 1);
            update(0, N, a[j] - 1, 1, 1);
            //cout << a[i] << " " << a[j] << " " << tr[1].first << " " << tr[1].second << "\n";
            st.insert(b[tr[1].first]);
            update(0, N, a[i] + 1, -1, 1);
            update(0, N, a[j] - 1, -1, 1);
            update(0, N, a[i], 1, 1);
            update(0, N, a[j], 1, 1);
        }
    }
    for (auto it: st) cout << it << " ";
    return 0;
}