#include<bits/stdc++.h>
using namespace std;
typedef tree<array<int, 3>, null_type, less<array<int, 3>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int N, Q;
int cur;
vector<int> A, nxtg, subans;
vector<pair<int, int>> q;
ordered_set S;// original segment {L, R};
template<typename T>
struct fenwick_tree {
int N;
T E;
vector<T> bit;
fenwick_tree(int n, T e = 0) { // empty!?
swap(n, N);
swap(e, E);
bit.resize(N + 1, E);
}
void add(int ind, T val) {
++ind;
while(ind <= N) {
bit[ind] += val;
ind += ind & -ind;
}
}
T pref_sum(int ind) {
T total = E;
++ind;
while(ind > 0) {
total += bit[ind];
ind -= ind & -ind;
}
return total;
}
T query(int L, int R) {
return pref_sum(R) - pref_sum(L - 1);
}
};
fenwick_tree<int> bit(400200, 0);
void shuffle_go() {
if(cur == N / 2) {
return;
}
auto x = end(S); --x;
while(x != begin(S) && cur - ((*x)[2] - (*x)[1] + 1) >= N / 2) {
--R;
cur -= ((*x)[2] - (*x)[1] + 1);
for(int i = (*x)[2]; i >= (*x)[1]; --i) {
subans.push_back(A[i]);
}
x = S.erase(x); --x;
}
if(cur == N / 2) {
return;
}
array<int, 3> mv = *x;
S.erase(x);
--R;
int trsh = cur - N / 2;
--L;
bit.add(L, mv[2] - trsh - mv[1] + 1);
S.insert({mv[0], mv[1], mv[2] - trsh});
int L = mv[2] - trsh + 1;
int R = mv[2];
for(int i = L; i <= R; ++i) {
int j = min(R, nxtg[i] - 1);
--L;
bit.add(L, j - i + 1);
S.insert({A[i], i, j});
i = j;
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
cur = N;
A.resize(N); for(int& u : A) cin >> u;
q.resize(Q); for(auto& u : q) { cin >> u.first >> u.second; u.first = min(u.first, N); }
vector<int> ind(Q); iota(begin(ind), end(ind), 0);
sort(begin(ind), end(ind), [&](const int& u, const int& v) { return q[u].first < q[v].first; });
{
nxtg.resize(N, N);
vector<int> st;
for(int i = N - 1; i >= 0; --i) {
while(!st.empty() && A[st.back()] < A[i]) st.pop_back();
if(!st.empty()) nxtg[i] = st.back();
st.push_back(i);
}
}
int K = 0;
while(K < Q && q[ind[K]].first == 0) {
cout << A[q[ind[K]].second - 1] << '\n';
++K;
}
//first change manually
for(int i = 0; i < N / 2; ++i) {
int j = min(nxtg[i] - 1, N / 2 - 1);
S.insert({A[i], i, j});
i = j;
}
for(int i = N / 2; i < N; ++i) {
int j = nxtg[i] - 1;
S.insert({A[i], i, j});
i = j;
}
L = R = 400200 - 3;
++L;
for(auto& u : S) {
--L;
bit.add(L, u[2] - u[1] + 1);
}
for(int i = 1; i <= N + 2; ++i) {
while(K < Q && q[ind[K]].first == i) {
int sd = q[ind[K]].second - 1;
if(sd >= cur) {
cout << subans[sd - cur] << '\n'; // whut
} else {
int tl = L, tr = R + 1;
while(tl < tr) {
int tm = (tl + tr) / 2;
if(bit.query(L, tm) <= sd + 1) {
tl = tm + 1;
} else tr = tm;
}
--tl;
tl -= L;
auto x = S.find_by_order(tl);
cout << A[(*x)[1] + (sd + 1) - bit.query(L, tl)] << '\n'; // sus
}
++K;
}
shuffle_go();
}
return 0;
}
Compilation message
Main.cpp:3:9: error: 'tree' does not name a type; did you mean 'free'?
3 | typedef tree<array<int, 3>, null_type, less<array<int, 3>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
| ^~~~
| free
Main.cpp:9:1: error: 'ordered_set' does not name a type
9 | ordered_set S;// original segment {L, R};
| ^~~~~~~~~~~
Main.cpp: In function 'void shuffle_go()':
Main.cpp:47:15: error: 'S' was not declared in this scope
47 | auto x = end(S); --x;
| ^
Main.cpp:49:5: error: 'R' was not declared in this scope
49 | --R;
| ^
Main.cpp:61:4: error: 'R' was not declared in this scope
61 | --R;
| ^
Main.cpp:63:4: error: 'L' was not declared in this scope
63 | --L;
| ^
Main.cpp: In function 'int32_t main()':
Main.cpp:103:3: error: 'S' was not declared in this scope
103 | S.insert({A[i], i, j});
| ^
Main.cpp:108:3: error: 'S' was not declared in this scope
108 | S.insert({A[i], i, j});
| ^
Main.cpp:111:2: error: 'L' was not declared in this scope
111 | L = R = 400200 - 3;
| ^
Main.cpp:111:6: error: 'R' was not declared in this scope
111 | L = R = 400200 - 3;
| ^
Main.cpp:113:16: error: 'S' was not declared in this scope
113 | for(auto& u : S) {
| ^
Main.cpp:132:14: error: 'S' was not declared in this scope
132 | auto x = S.find_by_order(tl);
| ^
