神奇思路

Jerry_heng @ 2024-01-31 21:59:05

by 23HKR @ 2024-06-07 23:32:48

类似于这样吗？

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned int;
using pii = pair<int, int>;
const int N = 1e6 + 10;
const ll base = 133731;
int t, n, m, k, l, r, op, x, y;
struct nd {
    ll v, p;
    bool operator<(const nd&nd1)const {
        if(v==nd1.v)return p<nd1.p;
        return v < nd1.v;
    }
} f[N], g[N];
ll ans[N], cnt;
set<ll> st;
unordered_map<ll, int> cast;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> f[i].v;
        f[i].p = i;
        g[i] = f[i];
    }
    if(n%2==0)n-=1;
    sort(f + 1, f + 1 + n);
    for (int i = 1; i <= n; i++) {
        st.insert(i);
        cast[f[i].v * base + f[i].p] = i;
    }    
    auto p = st.begin(), p1 = st.begin(), p2 = st.begin();
    for (int i = 2; i <= (n + 1) / 2; i++)p++;
    ans[++cnt] = *p;
    for (int i = n; i >= 3; i -= 2) {
        p1 = st.find( cast[g[i].v * base + g[i].p]);
        p2 = st.find( cast[g[i - 1].v * base + g[i - 1].p]);
        if (*p1 <= *p && *p2 <= *p) {
            p++;
        } else if (*p1 >= *p && *p2 >= *p) {
            p--;
        }
        st.erase(p1);
        st.erase(p2);
        ans[++cnt] = *p;
    }
    for (int i = cnt; i >= 1; i--) {
        cout << f[ans[i]].v << "\n";
    }
    return 0;
}