Rooks Defenders（二分）

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

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

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

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

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

#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超時了