[数据结构与算法]瓜瓜选妃（set)

set的二维数组下标法，set的lower_bound和upper_bound，返回定位器，删除区间可以用他们的返回区间，eraser，注意区间删除是后一个要后一位，思维很强

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

今天是瓜瓜大王选妃的日子，所有 MM 排成了 n×mn \times mn×m 的方阵。

每次瓜瓜可以任意选择一个矩形区域，但是瓜瓜又希望能够雨露均沾，每个 MM 都能被选到。

瓜瓜会做 kkk 次选择，你需要告诉他一个最早的一个选择 tit_iti?，自此 tit_iti? 以后（包括 tit_iti?）所有人都被选到过了。如果不存在，输出 ?1-1?1。

输入描述:

第一行有三个正整数 n,m,kn, m, kn,m,k，其中 1?n,m?5001 \leqslant n, m \leqslant 5001?n,m?500，1?k?1051 \leqslant k \leqslant 10^51?k?105。

接下来 kkk 行，其中每行有四个数字 x1,y1,x2,y2x_1, y_1, x_2, y_2x1?,y1?,x2?,y2?，表示瓜瓜选择矩形的左上角 (x1,y1)(x_1, y_1)(x1?,y1?) 和右下角 (x2,y2)(x_2, y_2)(x2?,y2?)，其中 1?x1?x2?n1 \leqslant x_1 \leqslant x_2 \leqslant n1?x1??x2??n， 1?y1?y2?m1 \leqslant y_1 \leqslant y_2 \leqslant m1?y1??y2??m。

输出描述:

在一行输出最早的选择位置。

示例1

输入

复制3 3 3 1 1 2 2 1 2 3 3 2 1 3 3

3 3 3
1 1 2 2
1 2 3 3
2 1 3 3

输出

复制3

3

说明

做完全部三次选择后，整个方阵才是全部被选过的。

示例2

输入

复制3 3 1 1 1 1 1

3 3 1
1 1 1 1

输出

复制-1

-1

说明

显然存在 MM 没有被选过。

#include <bits/stdc++.h>

using namespace std;
const int N = 5e2 + 10;
int n, m, k;
bool vis[N];
set<int> s[N];
int cnt = 0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	//用set构造二维数组,而且这个构造是符合删除区间的 
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			s[i].insert(j);
	} 
	
	int lx, ly, rx, ry; 
	for (int i = 1; i <= k; ++i)
	{
		cin >> lx >> ly >> rx >> ry;
		for (int j = lx; j <= rx; ++j)
		{
			auto l = s[j].lower_bound(ly);
			auto r = s[j].upper_bound(ry);
			s[j].erase(l, r);
			if (s[j].empty() && !vis[j])
			{
				vis[j] = true;
				cnt++;
			}
		}
		
		if (cnt == n)
		{
			cout << i << endl;
			return 0; 
		}
	}
	cout << "-1" << endl;	 
	return 0;
}