D - Sequence Query（二分查找，set）

题目链接：D - Sequence Query (atcoder.jp)

题目大意

一开始有一个空序列A，可以进行三种操作，共进行Q种操作。

• 操作1 x：将 x 插入到序列A中。
• 操作2 x k ：求序列A中比 x 小且第 k 大的数。
• 操作3 x k ：求序列A中比 x 大且第 k 小的数。

数据范围详见原题。

思路

最典型的思路是维护一个有序序列，然后二分查找进行操作2 3，二分的复杂度为O(logN)，但是此时插入的复杂度会比较大，达到O(N)，即使用双向的数组优化也要O(N / 2) = O(N)。所以我们需要一种可以有较低复杂度来进行插入且维护序列单调性的数据结构。

可以想到用multiset，插入复杂度是O(logN)，底层原理是红黑树，所以在二分查找后得到的iterator不能直接 + k - 1，也不能用 > 或 < 判断是否越界，而应该用个循环来移动iterator，这应该也是 k <= 5 的好处。

使用multiset需要引入头文件<set>，具体方法请见代码。

这里主要是iterator处理麻烦一些，其他的都还好。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*-------全局变量------*/
multiset<int> s;

/*-----自定义函数------*/
inline int goleft(multiset<int>::iterator it, int k)
{
	if(it == s.begin() && k)return -1;//将会越界。
	while(k --)if(-- it == s.begin() && k)return -1;//将会越界。 
	return *it;
}

inline int goright(multiset<int>::iterator it, int k)
{
	if(it == s.end())return -1;//已经越界了。 
	while(k --)if(++ it == s.end())return -1;//已经越界了。 
	return *it;
}

signed main()
{
	//freopen("in.txt","r",stdin);
	int Q = re();
	while(Q --)
	{
		int op = re();
		if(op == 1)s.insert(re());//将读入的值直接插入 s
		else if(op == 2)
		{
			int x = re(), k = re();
			//得到第一个大于 x 的数的迭代器，那么他的前一个就是第一个小于等于 x 的 
			multiset<int>::iterator it = s.upper_bound(x);
			//往左走 k 次
			pr("%lld\n",goleft(it, k));
		}
		else if(op == 3)
		{
			int x = re(), k = re();
			//得到第一个大于等于 x 的数的迭代器
			multiset<int>::iterator it = s.lower_bound(x);
			//往右走 k - 1次
			pr("%lld\n",goright(it, k - 1));
		}
	}
	return 0;
}