ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

D - Sequence Query(二分查找,set)

2022年2月27日 759点热度 0人点赞 0条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ iterator multiset STL 数据结构
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号