Rooks Defenders（二分）

題目 https://codeforces.com/contest/1679/problem/C

題意 
：給定一個(gè)的矩陣，有三種操作

• 往矩陣埋一顆地雷，保證對(duì)應(yīng)的點(diǎn)之前不存在地雷 。
• 往矩陣挖掉一個(gè)顆地雷 ，保證對(duì)應(yīng)的點(diǎn)之前存在地雷。

• 查詢(xún)子矩陣是否所有點(diǎn)都被地雷覆蓋。一個(gè)點(diǎn)(x,y)被地雷覆蓋，當(dāng)且僅當(dāng)至少存在一個(gè)地雷(a,b)，使得x==a或y==b。即至少存在一個(gè)地雷和它同行或同列 。

思路：維護(hù)沒(méi)有被地雷覆蓋的行和列 。對(duì)于每次查詢(xún)，如果在對(duì)應(yīng)范圍內(nèi)
，存在至少一個(gè)沒(méi)有被覆蓋的行 ，和至少一個(gè)沒(méi)有被覆蓋的列，則說(shuō)明子矩陣沒(méi)有被覆蓋 。否則，說(shuō)明矩陣被完全覆蓋。詳見(jiàn)代碼。

#include using namespace std;const int maxn = 100010;int n, q, op;int x, y, x2, y2;setrow, col;int numr[maxn], numc[maxn];void init() { 	row.clear();	col.clear();	memset(numr, 0, sizeof(numr));	memset(numc, 0, sizeof(numc));	vectorve;	for (int i = 1; i <= n; ++i) { 		ve.push_back(i);	}	row = { ve.begin(), ve.end()};	col = { ve.begin(), ve.end()};}// 查找s集合是否存在 [st,ed] 的元素 bool check(set&s, int st, int ed) { 	// >= st	// 用通用lower_bound超時(shí)了，還是內(nèi)置的香 //	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");				else					printf("Yes");				break;		}	}}int main() { 	int t;	t = 1;	while (t--) { 		solve();	}}/*8 101 2 43 6 2 7 21 3 23 6 2 7 21 4 33 2 6 4 82 4 33 2 6 4 81 4 83 2 6 4 8*/

投稿時(shí)間：2022-05-23  最后更新：2022-09-04