[ABC241D] Sequence Query 题解

[ABC241D] Sequence Query

Description

有一个空序列 \(a\)。给定 \(q\) 次操作，每次询问是以下三种之一：

• 1 x：向 \(a\) 中插入元素 \(x\)。
• 2 x k：输出 \(a\) 中所有 \(\le x\) 的元素中的第 \(k\) 大值。如果不存在输出 -1。
• 3 x k：输出 \(a\) 中所有 \(\ge x\) 的元素中的第 \(k\) 小值。如果不存在输出 -1。

---

Solution

考虑使用 set 维护。

操作 \(1\) 直接 s.push(x) 即可。

剩下两个操作我们可以分开考虑，先找到 \(a\) 中所有 \(\le x\) 的元素中最大的，然后从大往小跳 \(k\) 次即可。

相对地，对于操作 \(3\) 我们可以考虑先用 lower_bound 找到 \(a\) 中所有 \(\ge x\) 的数中最小的，然后往大跳 \(k-1\) 次即可。

注意：lower_bound 找的是 \(a\) 中所有 \(\ge x\) 的数中最大的，所以只需要跳 \(k-1\) 次

#include<bits/stdc++.h>
#define int long long
using namespace std;
multiset<long long>s;
long long T;
inline void solve(){cin>>T;while(T--){int opt,x,k;cin>>opt>>x;if(opt==1){s.insert(x);}else if(opt==2){cin>>k;auto it=s.upper_bound(x);int ok=1;while(k){if(it==begin(s)){ok=0;break;}k--;advance(it,-1);}if(ok){cout<<*it<<endl;}else{cout<<-1<<endl;}}else{cin>>k;k--;auto it=s.lower_bound(x);int ok=1;while(k){if(it==end(s)){ok=0;break;}k--;advance(it,1);}if(it==end(s)){ok=0;}if(ok==1){cout<<*it<<endl;}else{cout<<-1<<endl;}}}
}
signed main(){solve();return 0;
}