Editorial for Điểm trên cạnh hình chữ nhật - HRASTOVI

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
fo='';
maxn=300300;
maxm=200200;
oo=1000000000;
type ar1=array[1..maxn] of longint;
ar2=array[1..maxm] of longint;
var num,numy,n,m:longint;
x,y:ar1;
a,b,re:ar2;

procedure rf;
var i:longint;
begin
for i:=1 to n do read(x[i],y[i]);
for i:=1 to m do read(a[i*2],b[i*2],a[i*2+1],b[i*2+1]);
end;

procedure sort(l,r:longint);
var i,j,p,q,t:longint;
begin
i:=l; j:=r; p:=x[(i+j) shr 1]; q:=y[(i+j) shr 1];
repeat
while (x[i]<p) or ((x[i]=p) and (y[i]<q)) do i:=i+1;
while (x[j]>p) or ((x[j]=p) and (y[j]>q)) do j:=j-1;
if i<=j then
begin
t:=x[i]; x[i]:=x[j]; x[j]:=t;
t:=y[i]; y[i]:=y[j]; y[j]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure sortt(l,r:longint);
var i,j,p,q,t:longint;
begin
i:=l; j:=r; p:=y[(i+j) shr 1]; q:=x[(i+j) shr 1];
repeat
while (y[i]<p) or ((y[i]=p) and (x[i]<q)) do i:=i+1;
while (y[j]>p) or ((y[j]=p) and (x[j]>q)) do j:=j-1;
if i<=j then
begin
t:=x[i]; x[i]:=x[j]; x[j]:=t;
t:=y[i]; y[i]:=y[j]; y[j]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sortt(i,r);
if l<j then sortt(l,j);
end;

function bs(xx,yy:longint):longint;
var l,r,mid,i:longint;
begin
bs:=oo;
l:=1; r:=n;
while l<=r do
begin
mid:=(l+r) div 2;
if (x[mid]<xx) or ((x[mid]=xx) and (y[mid]<yy)) then l:=mid+1
else r:=mid-1;
end;
for i:=mid-1 to mid+1 do
if (i>0) and (i<=n) and ((x[i]>xx) or ((x[i]=xx) and (y[i]>=yy))) then exit(i);
end;

function bss(xx,yy:longint):longint;
var l,r,mid,i:longint;
begin
bss:=-oo;
l:=1; r:=n;
while l<=r do
begin
mid:=(l+r) div 2;
if (x[mid]>xx) or ((x[mid]=xx) and (y[mid]>yy)) then r:=mid-1
else l:=mid+1;
end;
for i:=mid+1 downto mid-1 do
if (i>0) and (i<=n) and ((x[i]<xx) or ((x[i]=xx) and (y[i]<=yy))) then exit(i);
end;

procedure pr;
var i,p,q:longint;
begin
for i:=1 to m do
begin
p:=bs(a[i*2],b[i*2]);
q:=bss(a[i*2],b[i*2+1]);
if q>=p then re[i]:=re[i]+q-p+1;
p:=bs(a[i*2+1],b[i*2]);
q:=bss(a[i*2+1],b[i*2+1]);
if q>=p then re[i]:=re[i]+q-p+1;
end;
end;

function bs1(xx,yy:longint):longint;
var l,r,mid,i:longint;
begin
bs1:=oo;
l:=1; r:=n;
while l<=r do
begin
mid:=(l+r) div 2;
if (y[mid]<yy) or ((y[mid]=yy) and (x[mid]<xx)) then l:=mid+1
else r:=mid-1;
end;
for i:=mid-1 to mid+1 do
if (i>0) and (i<=n) and ((y[i]>yy) or ((y[i]=yy) and (x[i]>=xx))) then exit(i);
end;

function bss1(xx,yy:longint):longint;
var l,r,mid,i:longint;
begin
bss1:=-oo;
l:=1; r:=n;
while l<=r do
begin
mid:=(l+r) div 2;
if (y[mid]>yy) or ((y[mid]=yy) and (x[mid]>xx)) then r:=mid-1
else l:=mid+1;
end;
for i:=mid+1 downto mid-1 do
if (i>0) and (i<=n) and ((y[i]<yy) or ((y[i]=yy) and (x[i]<=xx))) then exit(i);
end;

procedure prr;
var i,p,q:longint;
begin
for i:=1 to m do
begin
p:=bs1(a[i*2],b[i*2]);
q:=bss1(a[i*2+1],b[i*2]);
if q>=p then re[i]:=re[i]+q-p+1;
p:=bs1(a[i*2],b[i*2+1]);
q:=bss1(a[i*2+1],b[i*2+1]);
if q>=p then re[i]:=re[i]+q-p+1;
end;
end;

function bsss(xx,yy:longint):boolean;
var l,r,mid:longint;
begin
bsss:=false;
l:=1; r:=n;
while l<=r do
begin
mid:=(l+r) div 2;
if (x[mid]=xx) and (y[mid]=yy) then exit(true);
if (x[mid]<xx) or ((x[mid]=xx) and (y[mid]<yy)) then l:=mid+1
else r:=mid-1;
end;
end;

procedure minus;
var i:longint;
begin
for i:=1 to m do
begin
if bsss(a[i*2],b[i*2]) then re[i]:=re[i]-1;
if bsss(a[i*2],b[i*2+1]) then re[i]:=re[i]-1;
if bsss(a[i*2+1],b[i*2]) then re[i]:=re[i]-1;
if bsss(a[i*2+1],b[i*2+1]) then re[i]:=re[i]-1;
end;
end;

procedure wf;
var i:longint;
begin
for i:=1 to m do writeln(re[i]);
end;

begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
sort(1,n);
minus;
pr;
sortt(1,n);
prr;
wf;
close(input); close(output);
end.


#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
//#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 700005;
using namespace std;

int n, m, p;
int x1[N], y1[N], x2[N], y2[N];

struct point {
int x, y, id;
point(int _x = 0, int _y = 0, int _id = 0) {
x = _x; y = _y; id = _id;
}
bool operator < (const point &b) const {
return (x != b.x) ? (x < b.x) : ((y != b.y) ? (y < b.y) : id < b.id);
}
} a[N];

int findLeft(point a) {
if (a.y == y1[a.id]) return -1;
return y1[a.id];
}

int s[N];
int ans[N];

void solve() {
sort(a + 1, a + 1 + p);
int j;
for(int i = 1; i <= p; i = j + 1) {
j = i;
while (a[j + 1].x == a[i].x) j++;
s[i - 1] = 0;
REP(k, i, j) {
s[k] = s[k - 1];
if (a[k].id) {
int l = i, r = k, pos;
int leftBound = findLeft(a[k]);
if (leftBound == -1) continue;
while (l <= r) {
int mid = l + r >> 1;
if (a[mid].y >= leftBound) {
pos = mid; r = mid - 1;
}
else
l = mid + 1;
}
ans[a[k].id] += s[k] - s[pos - 1];
}
else
s[k]++;
}
}
}

int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
REP(i, 1, n) cin >> a[i].x >> a[i].y;
cin >> m;
p = n;
REP(i, 1, m) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
a[++p] = point(x1[i], y1[i], i);
a[++p] = point(x1[i], y2[i], i);
a[++p] = point(x2[i], y1[i], i);
a[++p] = point(x2[i], y2[i], i);
}
solve();
REP(i, 1, p) swap(a[i].x, a[i].y);
REP(i, 1, m) {
int yy1 = y1[i], yy2 = y2[i];
y1[i] = x1[i]; y2[i] = x2[i];
x1[i] = yy2; x2[i] = yy1;
}
solve();
int j;
for(int i = 1; i <= p; i = j + 1) {
j = i;
if (a[i].id == 0) {
while (a[j + 1].x == a[i].x && a[j + 1].y == a[i].y)
ans[a[++j].id]--;
}
}
REP(i, 1, m) cout << ans[i] << '\n';
return 0;
}


Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#define MAXN 300111
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define oo 1000111000
using namespace std;

int n,m;
pair<int,int> a[MAXN],b[MAXN];

int main() {
scanf("%d",&n);
FOR(i,1,n) {
int x,y;
scanf("%d %d",&x,&y);
a[i]=MP(x,y);
b[i]=MP(y,x);
}
n++;
a[n]=MP(oo,oo);
b[n]=MP(oo,oo);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
scanf("%d",&m);
FOR(i,1,m) {
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int res=UB(a+1,a+n+1,MP(x1,y2))-LB(a+1,a+n+1,MP(x1,y1))
+UB(a+1,a+n+1,MP(x2,y2))-LB(a+1,a+n+1,MP(x2,y1))
+UB(b+1,b+n+1,MP(y1,x2-1))-LB(b+1,b+n+1,MP(y1,x1+1))
+UB(b+1,b+n+1,MP(y2,x2-1))-LB(b+1,b+n+1,MP(y2,x1+1));
printf("%d\n",res);
}
return 0;
}


Code mẫu của hieult

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
//#include <conio.h>

using namespace std;

vector<pair < int, int> > X,Y;
int n,que,x,y,x1,x2,y1,y2;

inline int Q_fow(vector<pair<int,int> > &P, int x,int y1,int y2){
return upper_bound(P.begin(),P.end(),make_pair(x,y2))- upper_bound(P.begin(),P.end(),make_pair(x,y1));
}

inline int Q_rev(vector<pair<int,int> > &P,int x, int y1,int y2){
return lower_bound(P.begin(),P.end(),make_pair(x,y2))-lower_bound(P.begin(),P.end(),make_pair(x,y1));
}

int main()
{
scanf("%d",&n);
for(int i = 0;i<n;i++)
{
scanf("%d %d",&x,&y);
X.push_back(make_pair(x,y));
Y.push_back(make_pair(y,x));
}
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
scanf("%d",&que);
for(int i = 1;i<=que;i++)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
printf("%d\n",Q_fow(X,x1,y1,y2)+Q_fow(Y,y2,x1,x2)+Q_rev(X,x2,y1,y2)+Q_rev(Y,y1,x1,x2));
}
// getch();
}


Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
typedef long long ll;
using namespace std;

vector< pair<int,int> > X,Y;
int n,p;

int segX(pair<int,int> u,pair<int,int> v)
{
return upper_bound(X.begin(),X.end(),v) - lower_bound(X.begin(),X.end(),u);
};

int segY(pair<int,int> u,pair<int,int> v)
{
return upper_bound(Y.begin(),Y.end(),v) - lower_bound(Y.begin(),Y.end(),u);
};

int main()
{
//    freopen("hras.in","r",stdin);
//    freopen("hras.ou","w",stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x,y;
scanf("%d %d", &x, &y);
X.push_back(make_pair(x,y));
Y.push_back(make_pair(y,x));
};
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
scanf("%d", &p);
for (int i = 0; i < p; i++)
{
int x1,y1,x2,y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int ret = 0;
ret += segX(make_pair(x1,y1),make_pair(x1,y2));
ret += segX(make_pair(x2,y1),make_pair(x2,y2));
ret += segY(make_pair(y1,x1 + 1),make_pair(y1,x2 - 1));
ret += segY(make_pair(y2,x1 + 1),make_pair(y2,x2 - 1));
printf("%d\n", ret);
};
};


Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAXP   300300
#define MAXR   100100
#define x   first
#define y   second
using namespace std;
typedef pair<int,int> point;
point ax[MAXP];
point ay[MAXP];
int n,p;
bool cmpx(const point &a,const point &b) {
if (a.x<b.x) return (true);
if (a.x>b.x) return (false);
return (a.y<b.y);
}
bool cmpy(const point &a,const point &b) {
if (a.y<b.y) return (true);
if (a.y>b.y) return (false);
return (a.x<b.x);
}
void init(void) {
int i,px,py;
scanf("%d",&n);
for (i=1;i<=n;i=i+1) {
scanf("%d",&px);
scanf("%d",&py);
ax[i]=point(px,py);
ay[i]=point(px,py);
}
sort(&ax[1],&ax[n+1],cmpx);
sort(&ay[1],&ay[n+1],cmpy);
}
int county(const int &y,const int &x1,const int &x2) {
if (x1>x2) return (0);
if (cmpy(ay[n],point(x1,y))) return (0);
if (cmpy(point(x2,y),ay[1])) return (0);
int f,l;
f=lower_bound(&ay[1],&ay[n+1],point(x1,y),cmpy)-&ay[0];
if (cmpy(point(x2,y),ay[n])) l=upper_bound(&ay[1],&ay[n+1],point(x2,y),cmpy)-&ay[0];
else l=n+1;
return (l-f);
}
int countx(const int &x,const int &y1,const int &y2) {
if (y1>y2) return (0);
if (cmpx(ax[n],point(x,y1))) return (0);
if (cmpx(point(x,y2),ax[1])) return (0);
int f,l;
f=lower_bound(&ax[1],&ax[n+1],point(x,y1),cmpx)-&ax[0];
if (cmpx(point(x,y2),ax[n])) l=upper_bound(&ax[1],&ax[n+1],point(x,y2),cmpx)-&ax[0];
else l=n+1;
return (l-f);
}
void process(void) {
int i,r,x1,y1,x2,y2;
scanf("%d",&p);
for (i=1;i<=p;i=i+1) {
r=0;
scanf("%d",&x1);
scanf("%d",&y1);
scanf("%d",&x2);
scanf("%d",&y2);
r+=county(y1,x1,x2);
r+=county(y2,x1,x2);
r+=countx(x1,y1+1,y2-1);
r+=countx(x2,y1+1,y2-1);
printf("%d\n",r);
}
}
int main(void) {
init();
process();
return 0;
}


Code mẫu của khuc_tuan

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