[ABC234]D - Prefix K-th Max（set）

题目传送门：D - Prefix K-th Max (atcoder.jp)

题目大意

给定一个大小为N的排列，从第K个数字开始，每次求从开始到该数字为止的序列中的第K大的数字。

思路

如果是一个月前，我将会不知所措。但是最近atcoder出了好几个multiset和set的题目，于是不难想到用set这个神奇的数据结构。

因为set的插入和查询复杂度均为O(logN)，所以可以很轻松地完成这道题。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	int N, K;cin >> N >> K;
	set<int> s;
	for(int i = 1, x;i <= N; ++ i)
	{
		cin >> x;s.insert(x);
		if(s.size() > K)s.erase(s.begin());
		if(s.size() == K)printf("%lld\n",*s.begin());
	}
	return 0;
}