CEOI 2022 Day 1. A

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#define int long long
#define mp make_pair
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(time(nullptr));

constexpr int N = (int)2e6 + 111;

int tr[N];
int SUM = 0;
void upd(int r,int x){
    SUM += x;
    for(int i = r; i < N; i |= i+1)
        tr[i] += x;
    return;
}
int get(int r){
    int s = 0;
    for(int i = r; i >= 0; i&=i+1,i--)
        s += tr[i];
    return s;
}
int getSuf(int r){
    return SUM - get(r-1);
}
int a[N];
int t[N],P[N];
int n = 20,q = 20;

vector<int> brute(){
    int b[n];
    vector<int> ans;
    int A[n+1][n];
    for(int i = 0; i < n; i++){
        A[0][i] = a[i];
        b[i] = a[i];
    }
    int cnt = 0;
    for(int i = 1;; i++){
        int ptr[2] = {0,n/2};
        int pos = 0;
        while(ptr[0] < n/2 && ptr[1] < n){
            if(A[i-1][ptr[0]] < A[i-1][ptr[1]]){
                A[i][pos++] = A[i-1][ptr[0]++];
            } else {
                A[i][pos++] = A[i-1][ptr[1]++];
            }
        }
        while(ptr[0] < n/2) A[i][pos++] = A[i-1][ptr[0]++];
        while(ptr[1] < n) A[i][pos++] = A[i-1][ptr[1]++];
        bool diff = false;
        for(int j = 0; j < n; j++){
            diff |= A[i-1][j] != A[i][j];
        }
        cnt++;
//        for(int j = 0; j < n; j++)
//            cout << A[i][j] << " ";
//        cout << "\n";
        if(!diff)
            break;
    }
    for(int i = 0; i < q; i++){
        t[i] = min(t[i],cnt);
        ans.pb(A[t[i]][P[i]-1]);
    }
    return ans;
}

tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> st;
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> S[N];
int parent[N];
vector<pair<int,pair<int,int>>> Q;
int ans[N];

void solve(){
    n = (int)2e5, q = (int)1e6;
    for(int i = 0; i <= n; i++) tr[i] = 0;
    for(int i = 0; i <= n; i++) S[i].clear();
    st.clear();
    SUM = 0;
//    cin >> n >> q;
//    cout << n << " " << q << "\n";
    vector<int> V(n);
    iota(V.begin(),V.end(),1);
    V[0] = 1;
    for(int i = 1;i<=n/2;i+=1){
        V[i] = n/2-i+2;
    }
    for(int i = n/2+1;i<n;i+=1){
        V[i] = i+1;
    }
//    shuffle(V.begin(),V.end(),rnd);
    for(int i = 0; i < n; i++){
        a[i] = V[i];
//        cout << a[i] << " ";
//        cin >> a[i];
    }
//    cout << "\n";
    for(int i = 0; i < q; i++){
//        int t,pos;
        t[i] = rnd()%n;
        P[i] = rnd()%n+1;
//        cin >> t[i] >> P[i];
        t[i] = min(t[i],n/2);
        Q.pb(mp(t[i],mp(P[i],i)));
    }
    sort(Q.begin(),Q.end());
    vector<pair<int,int>> v;
    bool used[n+1];
    for(int i = 0; i <= n; i++){
        used[i] = false;
    }
    for(int i = 0; i < n; i++){
        v.pb(mp(a[i],i));
    }
    sort(v.rbegin(),v.rend());
    for(auto&[x,pos] : v){
        if(used[pos])
            continue;
        if(pos < n/2){
            int cnt = 0;
            for(int i = pos; i < n/2; i++){
                if(used[i])
                    break;
                S[x].insert(mp(i,a[i]));
                used[i] = 1;
                parent[a[i]] = x;
                cnt++;
            }
            st.insert(x);
            upd(x,cnt);
        } else {
            int cnt = 0;
            for(int i = pos; i < n; i++){
                if(used[i])
                    break;
                S[x].insert(mp(i,a[i]));
                used[i] = 1;
                parent[a[i]] = x;
                cnt++;
            }
            st.insert(x);
            upd(x,cnt);
        }
    }
//    cerr << "st: ";
//    for(auto& x : st)
//        cerr << x << " ";
//    cerr << "\n";
    int cur_t = 1;
    bool all = false;
//    return;
    for(auto& query : Q){
        int& t = query.first;
        int& pos = query.second.first;
        int& id = query.second.second;
        if(t == 0){
            ans[id] = a[pos-1];
            continue;
        }
        while(!all && cur_t < t){
            int l = 0, r = st.size();
            while(r - l > 1){
                int m = (l+r)>>1;
                int x = *st.find_by_order(m);
                int tl = getSuf(x);
                if(tl > n/2)
                    l = m;
                else
                    r = m;
            }
            int x = *st.find_by_order(l);
            int y = *st.find_by_order(l+1);
//            cerr << "x = " << x << ", y = " << y << "\n";
            int tr = getSuf(y);
//            cerr << "tr = " << tr << "\n";
            if(tr+1 > n/2){
                all = true;
//                cerr << "broke\n";
                break;
            }
            int delta = n/2 - tr;
            vector<int> cur;
//            cerr << "delete: ";
            assert(S[x].size() >= delta);
            for(int i = 0; i < delta; i++){
                auto p = *(--S[x].end());
                cur.pb(p.second);
//                cerr << p.second << " ";
                S[x].erase(--S[x].end());
            }
//            cerr << "\n";

            upd(x,-delta);
            reverse(cur.begin(),cur.end());
            v.clear();
            for(int i = 0; i < cur.size(); i++) used[i] = false;
            for(int i = 0; i < cur.size(); i++){
                v.pb(mp(cur[i],i));
            }
            sort(v.rbegin(),v.rend());
            for(int i = 0; i < v.size(); i++){
                int xx = v[i].first;
                int pos = v[i].second;
                if(used[pos])
                    continue;
                int cnt = 0;
                for(int j = pos; j < cur.size(); j++){
                    if(used[j])
                        break;
                    S[xx].insert(mp(j,cur[j]));
                    used[j] = 1;
                    parent[cur[j]] = xx;
                    cnt++;
                }
                upd(xx,cnt);
                st.insert(xx);
            }
            cur_t++;
        }
//        cerr << "cur_t = " << cur_t << "\n";
        int l = 0, r = st.size();
        while(r - l > 1){
            int m = (l+r)>>1;
            int x = *st.find_by_order(m);
            if(getSuf(x) >= n - pos + 1)
                l = m;
            else
                r = m;
        }
//        cerr << "l,r = " << l << " " << r << "\n";
        int x = *st.find_by_order(l);
//        cerr << "x = " << x << "\n";
        int sz = S[x].size();
        int suffSum = 0;
        if(l + 1 != st.size()){
            int y = *st.find_by_order(l+1);
            suffSum = getSuf(y);
        }
//        cerr << "suffSum = " << suffSum << "\n";
        int cur_pos = (n - pos + 1) - suffSum;
        cur_pos = S[x].size() - cur_pos;
//        cerr << "cur_pos = " << cur_pos << "\n";
        ans[id] = (S[x].find_by_order(cur_pos))->second;
    }
//    cout << "cur_t = " << cur_t << "\n";

//    vector<int> bruteAns = brute();

    for(int i = 0; i < q; i++){
//        if(ans[i] != bruteAns[i]){
//            for(int j = 0; j < n; j++){
//                cout << a[j] << " ";
//            }
//            cout << "\n";
//            cout << "WA\n";
//            cout << t[i] << " " << P[i] << "\n";
//            cout << "expected " << bruteAns[i] << ", found = " << ans[i] << "\n";
////            cout << ans[i] << "\n";
//            exit(0);
//        }
        cout << ans[i] << "\n";
    }
//    cout << "AC\n";
    return;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }
    return 0;
}
/**
41 6 22 18 20 33 44 15 5 32 49 16 38 19 46 36 37 8 25 43 39 12 47 23 10 13 2 9 31 30 35 50 14 48 17 11 7 45 34 3 27 24 40 42 29 21 26 1 4 28
41 6 22 18 20 33 44 15 5 32 49 16 38 19 46 36 37 8 25 43 39 12 47 23 10 13 2 9 31 30 35 50 14 48 17 11 7 45 34 3 27 24 40 42 29 21 26 1 4 28
WA
4 9
expected 6, found = 12
50 1
18 9 38 21 45 49 26 48 23 27 25 15 10 36 5 1 29 14 50 8 2 19 13 20 6 3 33 12 17 37 39 47 22 16 40 46 32 4 42 30 35 34 41 7 11 44 43 28 31 24
9 5
WA
expected 30, found = 28

**/