题目 题意：给定一个n * n的矩阵，有三种操作
- 往矩阵埋一颗地雷，保证对应的点之前不存在地雷。
- 往矩阵挖掉一个颗地雷，保证对应的点之前存在地雷。
查询子矩阵是否所有点都被地雷覆盖。一个点(x,y)被地雷覆盖，当且仅当至少存在一个地雷(a,b)，使得 x = = a x==a x==a或 y = = b y==b y==b。即至少存在一个地雷和它同行或同列。
思路：维护没有被地雷覆盖的行和列。对于每次查询，如果在对应范围内，存在至少一个没有被覆盖的行，和至少一个没有被覆盖的列，则说明子矩阵没有被覆盖。否则，说明矩阵被完全覆盖。详见代码。
#include
using namespace std;
const int maxn = 100010;
int n, q, op;
int x, y, x2, y2;
set row, col;
int numr[maxn], numc[maxn];
void init() {
row.clear();
col.clear();
memset(numr, 0, sizeof(numr));
memset(numc, 0, sizeof(numc));
vector ve;
for (int i = 1; i = st
// 用通用lower_bound超时了，还是内置的香
// set::iterator it = lower_bound(s.begin(), s.end(), st);
set::iterator it = s.lower_bound(st);
if (it == s.end()) {
return false;
}
if (*it > ed) {
return false;
}
return true;
}
void solve() {
scanf("%d%d", &n, &q);
init();
while (q--) {
scanf("%d%d%d", &op, &x, &y);
switch (op) {
case 1:
if (numr[x]++ == 0)
row.erase(row.find(x));
if (numc[y]++ == 0)
col.erase(col.find(y));
break;
case 2:
if (--numr[x] == 0)
row.insert(x);
if (--numc[y] == 0)
col.insert(y);
break;
case 3:
scanf("%d%d", &x2, &y2);
if (check(row, x, x2) && check(col, y, y2))
printf("No\n");
else
printf("Yes\n");
break;
}
}
}
int main() {
int t;
t = 1;
while (t--) {
solve();
}
}
/*
8 10
1 2 4
3 6 2 7 2
1 3 2
3 6 2 7 2
1 4 3
3 2 6 4 8
2 4 3
3 2 6 4 8
1 4 8
3 2 6 4 8
*/
