Rooks Defenders(二分)
Rooks Defenders(二分)
題目 https://codeforces.com/contest/1679/problem/C
題意 :給定一個(gè)的矩陣 ,有三種操作
- 往矩陣埋一顆地雷,保證對應(yīng)的點(diǎn)之前不存在地雷。
- 往矩陣挖掉一個(gè)顆地雷,保證對應(yīng)的點(diǎn)之前存在地雷。
- 查詢子矩陣是否所有點(diǎn)都被地雷覆蓋。一個(gè)點(diǎn)(x,y)被地雷覆蓋 ,當(dāng)且僅當(dāng)至少存在一個(gè)地雷(a,b) ,使得x==a或y==b 。即至少存在一個(gè)地雷和它同行或同列。
思路:維護(hù)沒有被地雷覆蓋的行和列。對于每次查詢 ,如果在對應(yīng)范圍內(nèi),存在至少一個(gè)沒有被覆蓋的行 ,和至少一個(gè)沒有被覆蓋的列,則說明子矩陣沒有被覆蓋