#include<bits/stdc++.h>
using namespace std;
mt19937 rng(0);//rng(time(nullptr));
using T = int;
struct node {
T val, ma;
int size;
size_t prior;
node *left, *right;
node *par=nullptr; bool isleft=0; //se serve get_pos
bool rot = false;
node(T v) : val(v), ma(v), size(1),
prior(rng()), left(0), right(0) {}
node* fix() {
ma = val, size = 1;
if (left) {
ma = max(ma, left->ma);
size += left->size;
}
if (right) {
ma = max(ma, right->ma);
size += right->size;
}
return this;
}
};
node* merge(node* a, node* b) {
if (!a) return b; a->fix();
if (!b) return a; b->fix();
if (a->prior > b->prior) {
auto tmp = merge(a->right, b);
a->right = tmp;
if(tmp)tmp->par = a, tmp->isleft = 0; //se serve get_pos
return a->fix();
} else {
auto tmp = merge(a, b->left);
b->left = tmp;
if(tmp)tmp->par = b, tmp->isleft = 1; //se serve get_pos
return b->fix();
}
}
//taglio subito dopo k elementi (1-based)
//es. k=1, divido il primo elemento dagli altri
pair<node*, node*> split(node* p, int k) {
if (!p) return {nullptr, nullptr};
p->fix();
int sl = p->left ? p->left->size : 0;
if (k <= sl) {
auto [a, b] = split(p->left, k);
if(a) a->par = nullptr, a->isleft=0; //se serve get_pos
p->left = b;
if(b) b->par = p, b->isleft = 1; //se serve get_pos
return {a, p->fix()};
} else {
auto [a, b] = split(p->right, k-sl-1);
if(b) b->par = nullptr, b->isleft=0; //se serve get_pos
p->right = a;
if(a) a->par = p, a->isleft = 0; //se serve get_pos
return {p->fix(), b};
}//invariante: sui due nodi di ritorno
} //è sempre stata chiamata ->fix()
int find_kth(node* p,int pos){
int sl = p->left ? p->left->size : 0;
if (p->left && pos < sl) {
return find_kth(p->left,pos);
} else if (p->right && pos > sl) {
return find_kth(p->right,pos - sl - 1);
} else {
return p->val;
}
}
int find_first(node *p,int val){
int sl = p->left ? p->left->size : 0;
if (p->left && p->left->ma > val) {
return find_first(p->left,val);
} else if (p->val > val){
return sl;
} else if (p->right && p->right->ma > val) {
return sl + 1 + find_first(p->right,val);
} else {
return p->size;
}
}
const int MAXN = 200005, MAXQ = 1000006;
node* vv[MAXN];
node* build(vector<T>& A, int l, int r) {
if (l + 1 == r) return vv[A[l]]=new node(A[l]);
int m = (l + r) / 2;
node* a = build(A, l, m);
node* b = build(A, m, r);
return merge(a, b);
}
// dato un node* p, ritorna la sua posizione (0-based)
int get_pos(node* p){
if(!p)return -1;
bool flag = (p->par && p->par->rot);
if(p->isleft ^ flag){
int rightsize=0;
if(p->right)rightsize=p->right->size;
return get_pos(p->par)-rightsize-1;
}else{
int leftsize=0;
if(p->left)leftsize=p->left->size;
return get_pos(p->par)+leftsize+1;
}
}
int n,q,ans[MAXQ],tmp[MAXN],cont;
vector<T> v;
vector<pair<int,int> > opz[MAXN];
node* root;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
v.resize(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
for(int i=0;i<q;i++){
int t,x;
cin>>t>>x;
opz[min(t,n)].emplace_back(x-1,i);
}
root = build(v,0,n);
for(int i=0;i<=n;i++){
for(auto [a,b] : opz[i]){
ans[b]=find_kth(root,a);
assert(get_pos(v[ans[b]])==a);
}
auto [a,b] = split(root,n/2);
while(b!=nullptr){
int val = find_kth(b,0);
if(val > a->ma){
a = merge(a,b);
break;
}
int pos1 = find_first(a,val);
int pos2 = find_first(b,val);
auto [c,d] = split(b,pos2);
auto [e,f] = split(a,pos1);
a = merge(merge(e,c),f);
b = d;
cont++;
}
root = a;
}
for(int i=0;i<q;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'node* merge(node*, node*)':
Main.cpp:32:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
32 | if (!a) return b; a->fix();
| ^~
Main.cpp:32:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
32 | if (!a) return b; a->fix();
| ^
Main.cpp:33:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
33 | if (!b) return a; b->fix();
| ^~
Main.cpp:33:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
33 | if (!b) return a; b->fix();
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:145:36: error: invalid conversion from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'node*' [-fpermissive]
145 | assert(get_pos(v[ans[b]])==a);
| ^
| |
| __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}
Main.cpp:102:19: note: initializing argument 1 of 'int get_pos(node*)'
102 | int get_pos(node* p){
| ~~~~~~^
