區域安全的check方法就是， 每行都有哨兵或者每列都有哨兵，然后我們用y建線段樹， 維護在每個y上的哨兵的x的最值就好啦。

#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long longusing namespace std;const int N = 2e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1);int n, m, k, q; bool ans[N];PII p[N]; struct Qus {PII a, b;bool operator < (const Qus& rhs) const {return b < rhs.b;}int id; } qus[N];int a[N << 2]; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 void update(int p, int val, int l, int r, int rt) {if(l == r) {a[rt] = max(a[rt], val);return;}int mid = l + r >> 1;if(p <= mid) update(p, val, lson);else update(p, val, rson);a[rt] = min(a[rt << 1], a[rt << 1 | 1]); } int query(int L, int R, int l, int r, int rt) {if(l >= L && r <= R) return a[rt];int mid = l + r >> 1;if(R <= mid) return query(L, R, lson);else if(L > mid) return query(L, R, rson);else return min(query(L, R, lson), query(L, R, rson)); }void solve() {sort(p + 1, p + 1 + k);sort(qus + 1, qus + 1 + q);memset(a, 0, sizeof(a));for(int i = 1, j = 1; i <= q; i++) {while(j <= k && p[j] <= qus[i].b) update(p[j].se, p[j].fi, 1, m, 1), j++;int mn = query(qus[i].a.se, qus[i].b.se, 1, m, 1);if(mn >= qus[i].a.fi) ans[qus[i].id] = true;} }int main() {scanf("%d%d%d%d", &n, &m, &k, &q);for(int i = 1; i <= k; i++) scanf("%d%d", &p[i].fi, &p[i].se);for(int i = 1; i <= q; i++) {scanf("%d%d", &qus[i].a.fi, &qus[i].a.se);scanf("%d%d", &qus[i].b.fi, &qus[i].b.se);qus[i].id = i;}solve();swap(n, m);for(int i = 1; i <= k; i++) swap(p[i].fi, p[i].se);for(int i = 1; i <= q; i++) {swap(qus[i].a.fi, qus[i].a.se);swap(qus[i].b.fi, qus[i].b.se);}solve();for(int i = 1; i <= q; i++) printf("%s\n", ans[i] ? "YES" : "NO");return 0; }/* */

?

轉載于:https://www.cnblogs.com/CJLHY/p/10437045.html

總結

以上是生活随笔為你收集整理的Codeforces 524E Rooks and Rectangles 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。