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;	
}

Download