MRECT1 - Điểm trên cạnh hình chữ nhật - HRASTOVI
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair
typedef pair<int,int> PII;
typedef vector<int> VI;
struct Rect {
int x, y, u, v;
};
struct Seg {
int id;
int x;
int y1, y2;
bool operator<(Seg s)const{
return x<s.x;
}
};
int n, m;
PII a[300030];
Rect b[100010];
Seg s[200020];
int res[100010];
int ns;
int dx[300030];
int nd;
int bit[300030];
void update(int i,int dt) {
for(++i;i<300030;i+=i&(-i))bit[i]+=dt;
}
int calc(int i){
int r=0;
for(++i;i>0;i-=i&(-i))r+=bit[i];
return r;
}
int main() {
scanf("%d",&n);
Rep(i,n)scanf("%d%d",&a[i].first,&a[i].second);
scanf("%d",&m);
Rep(i,m){
scanf("%d%d%d%d",&b[i].x,&b[i].y,&b[i].u,&b[i].v);
}
for(int kk=0;kk<2;++kk) {
sort(a,a+n);
nd = 0;
Rep(i,n) dx[nd++] = a[i].second;
sort(dx, dx + nd);
nd = unique(dx,dx+nd)-dx;
memset(bit,0,sizeof(bit));
// cout << nd << endl;
ns = 0;
Rep(i,m){
s[ns].id = i;
s[ns].x=b[i].x;
s[ns].y1=b[i].y;
s[ns].y2=b[i].v;
++ns;
s[ns]=s[ns-1];
s[ns].x=b[i].u;
++ns;
}
sort(s,s+ns);
int sin = 0, sout = 0;
for(int i=0;i<ns;){
int j=i;
while(j<ns && s[j].x==s[i].x) ++j;
while(sin < n && a[sin].first <= s[i].x) {
update(lower_bound(dx,dx+nd,a[sin].second)-dx,1);
++sin;
}
while(sout<n && a[sout].first < s[i].x) {
update(lower_bound(dx,dx+nd,a[sout].second)-dx,-1);
++sout;
}
for(int k=i;k<j;++k) {
int id1 = upper_bound(dx,dx+nd,s[k].y1)-dx;
int id2 = lower_bound(dx,dx+nd,s[k].y2)-dx-1;
// cout << " here " << id1 << " " << id2 << endl;
if(id1<=id2)
res[s[k].id] += calc(id2) - calc(id1-1);
}
i=j;
}
Rep(i,n) swap(a[i].first,a[i].second);
Rep(i,m) swap(b[i].x,b[i].y), swap(b[i].u,b[i].v);
}
sort(a,a+n);
Rep(i,m){
if(binary_search(a,a+n,MP(b[i].x,b[i].y))) ++res[i];
if(binary_search(a,a+n,MP(b[i].x,b[i].v))) ++res[i];
if(binary_search(a,a+n,MP(b[i].u,b[i].y))) ++res[i];
if(binary_search(a,a+n,MP(b[i].u,b[i].v))) ++res[i];
}
for(int i=0;i<m;++i)
printf("%d\n",res[i]);
return 0;
}