map

map 映射

同时存储一对 key 和 value
可以根据 key 找到 value

支持操作：
加入任意值
删除任意值
询问 lower_bound 和 upper_bound
询问最大值最小值

不支持：
询问第k大值
询问一个值是第几大

Java

C++ map = Java TreeMap (sorted map)
C++ unordered_map = Java HashMap

参考题目

abc253_c Max - Min Query

https://atcoder.jp/contests/abc253/tasks/abc253_c
维护 multiset
支持加入一个值
删去一个值x至多c次
输出最大值减去最小值的差

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int q, o, x, c;
int main()
{
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		scanf("%d", &o);
		if (o == 1)
		{
			scanf("%d", &x);
			g[x]++;
		}
		else if (o == 2)
		{
			scanf("%d%d", &x, &c);
			g[x] -= c;
			if (g[x] <= 0)
			{
				g.erase(x);
			}
		}
		else
		{
			printf("%d\n", g.rbegin()->first - g.begin()->first);
		}
	}
	return 0;
}

题解