题解
离线读入, 我们发现一个矩形能被保护, 矩形内部所有列上必定有一辆车, 或者所有行上必定有一辆车
分两次进行处理
第一次按照横坐标把车加进去, 然后查询最大横坐标在这个位置的矩形, 纵坐标区间里的车出现位置的最小值有没有超过最小横坐标
第二次按照纵坐标把车加进去, 然后查询最大纵坐标所在位置的矩形, 横坐标区间里的车出现位置的最小值有没有超过最小纵坐标
用线段树维护区间即可
代码
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- #include <vector>
- #include <set>
- #include <cmath>
- #include <bitset>
- #include <queue>
- #define enter putchar('\n')
- #define space putchar(' ')
- //#define ivorysi
- #define pb push_back
- #define mo 974711
- #define pii pair<int,int>
- #define mp make_pair
- #define fi first
- #define se second
- #define MAXN 200005
- #define eps 1e-12
- using namespace std;
- typedef long long int64;
- typedef double db;
- template<class T>
- void read(T &res) {
- res = 0;char c = getchar();T f = 1;
- while(c <'0' || c> '9') {
- if(c == '-') f = -1;
- c = getchar();
- }
- while(c>= '0' && c <= '9') {
- res = res * 10 - '0' + c;
- c = getchar();
- }
- res = res * f;
- }
- template<class T>
- void out(T x) {
- if(x <0) {x = -x;putchar('-');}
- if(x>= 10) out(x / 10);
- putchar('0' + x % 10);
- }
- int N,M,K,Q;
- bool ans[MAXN];
- struct Matrix {
- int x1,x2,y1,y2;
- }mat[MAXN];
- pii C[MAXN];
- struct Ins_node {
- int pos,w;
- friend bool operator <(const Ins_node &a,const Ins_node &b) {
- return a.pos < b.pos;
- }
- }Ins[MAXN];
- struct Qry_node {
- int l,r,s,t,id;
- friend bool operator < (const Qry_node &a,const Qry_node &b) {
- return a.t < b.t;
- }
- }Qry[MAXN];
- struct tr_node {
- int l,r;
- int minv;
- }tr[MAXN * 4];
- void build(int u,int l,int r) {
- tr[u].l = l;tr[u].r = r;
- tr[u].minv = 0;
- if(l == r) return;
- int mid = (l + r)>> 1;
- build(u <<1,l,mid);
- build(u << 1 | 1,mid + 1,r);
- }
- void update(int u) {
- tr[u].minv = min(tr[u << 1].minv,tr[u << 1 | 1].minv);
- }
- void Change(int u,int pos,int v) {
- if(tr[u].l == tr[u].r) {tr[u].minv = v;return;}
- int mid = (tr[u].l + tr[u].r)>> 1;
- if(pos <= mid) Change(u <<1,pos,v);
- else Change(u << 1 | 1,pos,v);
- update(u);
- }
- int Query(int u,int l,int r) {
- if(tr[u].l == l && tr[u].r == r) return tr[u].minv;
- int mid = (tr[u].l + tr[u].r)>> 1;
- if(r <= mid) return Query(u <<1,l,r);
- else if(l> mid) return Query(u <<1 | 1,l,r);
- else return min(Query(u << 1,l,mid),Query(u << 1 | 1,mid + 1,r));
- }
- void Process(int L) {
- sort(Ins + 1,Ins + K + 1);
- sort(Qry + 1,Qry + Q + 1);
- build(1,1,max(N,M));
- int p = 1,h = 1;
- for(int i = 1 ; i <= L ; ++i) {
- while(p <= K && Ins[p].pos <= i) {
- Change(1,Ins[p].w,Ins[p].pos);
- ++p;
- }
- while(h <= Q && Qry[h].t <= i) {
- if(!ans[Qry[h].id]) {
- if(Query(1,Qry[h].l,Qry[h].r)>= Qry[h].s) ans[Qry[h].id] = 1;
- }
- ++h;
- }
- }
- }
- void Solve() {
- read(N);read(M);read(K);read(Q);
- int x,y;
- for(int i = 1 ; i <= K ; ++i) {
- read(x);read(y);
- C[i] = mp(x,y);
- }
- for(int i = 1 ; i <= Q ; ++i) {
- read(mat[i].x1);read(mat[i].y1);read(mat[i].x2);read(mat[i].y2);
- }
- for(int i = 1 ; i <= K ; ++i) {
- Ins[i].pos = C[i].fi;Ins[i].w = C[i].se;
- }
- for(int i = 1 ; i <= Q ; ++i) {
- Qry[i] = (Qry_node){mat[i].y1,mat[i].y2,mat[i].x1,mat[i].x2,i};
- }
- Process(N);
- for(int i = 1 ; i <= K ; ++i) {
- Ins[i].pos = C[i].se;Ins[i].w = C[i].fi;
- }
- for(int i = 1 ; i <= Q ; ++i) {
- Qry[i] = (Qry_node){mat[i].x1,mat[i].x2,mat[i].y1,mat[i].y2,i};
- }
- Process(M);
- for(int i = 1 ; i <= Q ; ++i) {
- if(ans[i]) puts("YES");
- else puts("NO");
- }
- }
- int main() {
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- Solve();
- }
来源: http://www.bubuko.com/infodetail-2651792.html