Title Link

• Given \ (n \) red points and \ (n \) blue points on the two-dimensional plane, each point has a point weight.
• \(q \) queries, each given \ (L,R \). It is required to find a red dot \ ((rx,ry) \) (weight value \ (rv \)) and a blue dot \ ((bx,by) \) (weight value \ (bv \)), which meet the following requirements: \ (ry < by \)\ (Rx < L, BX > R \) or \ (Rx > L, BX < R \). Find the maximum value of \ (rv+bv \).
• \(1\le n\le10^5 \), \ (1\le q\le5\times10^5 \), all \ (x,L,R \) are different, and all \ (y \) are different

Divide and conquer pretreatment

Considering the limitation of \ (ry < by \), we first sort all points according to \ (y \), and then divide and conquer. Each time, we consider the contribution of red dots in the left interval and blue dots in the right interval.

Found that \ (Rx < L, BX > R \) or \ (Rx > L, BX < R \) is equivalent to \ ([RX < l] = [BX > R] \). For the red dot, note its type as \ ([RX < l] \); For the blue dot, note its type as \ ([BX > R] \).

Therefore, it can be proved by counter evidence that at least one of the selected red dot and blue dot has the largest weight in the interval: if neither of the selected two dots has the largest weight, the type of the selected red dot must be different from that of the blue dot with the largest weight - otherwise, the selected blue dot can be replaced with the blue dot with the largest weight, Similarly, the selected blue dot type must be the same as the red dot type with the largest weight. However, in this way, since the selected red dot and blue dot are of the same type, the red dot and blue dot with the largest weight are the same. It is better to choose them, resulting in contradiction.

Therefore, as long as the maximum red dot in the left section and all blue dots in the right section are regarded as a set of possible matching relationships, and the maximum blue dot in the right section and all red dots in the left section are regarded as a set of possible matching relationships.

Two dimensional point solution

A set of matching relationships can be expressed as \ ((rx,bx,v) \).

Query is to query the maximum value of \ (v \) for all matching relationships satisfying \ (Rx < L, BX > R \) and \ (Rx > L, BX < R \), that is, two-dimensional number point problems.

Code: \ (O(n\log^2 n+q\log n) \)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 100000
#define M 500000
#define SZ N*40
using namespace std;
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int ff,OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0,ff=1;W(!isdigit(oc=tc())) ff=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=ff;}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
	I void NA() {pc('-'),pc('1'),pc('\n');}
}using namespace FastIO;
int n;struct P {int x,y,w;I bool operator < (Cn P& o) Cn {return y<o.y;}}p[2*N+5];
int ct,dc,dv[SZ+5],Qt,ans[M+5];struct S {int x,y,w;I bool operator < (Cn S& o) Cn {return x<o.x;}}q[M+5],s[SZ+5];
struct TreeArray1
{
	int a[N+5];I void U(RI x,CI v) {W(x&&a[x]<v) a[x]=v,x-=x&-x;}I int Q(RI x) {RI t=0;W(x<=dc) t=max(t,a[x]),x+=x&-x;return t;}
}T1;
struct TreeArray2
{
	int a[N+5];I void U(RI x,CI v) {W(x<=dc&&a[x]<v) a[x]=v,x+=x&-x;}I int Q(RI x) {RI t=0;W(x) t=max(t,a[x]),x-=x&-x;return t;}
}T2;
I void Solve(CI l,CI r)//Divide and conquer pretreatment
{
	#define Add(i,j) (s[++ct]=(S){p[i].x,p[j].x,p[i].w+p[j].w})
	if(l==r) return;RI i,x,mid=l+r>>1;
	for(x=-1,i=l;i<=mid;++i) p[i].x<0&&(!~x||p[x].w<p[i].w)&&(x=i);if(~x) for(i=mid+1;i<=r;++i) p[i].x>0&&(Add(x,i),0);//The maximum red dot in the left section and all blue dots in the right section
	for(x=-1,i=mid+1;i<=r;++i) p[i].x>0&&(!~x||p[x].w<p[i].w)&&(x=i);if(~x) for(i=l;i<=mid;++i) p[i].x<0&&(Add(i,x),0);//The maximum blue dot in the right section and all red dots in the left section
	Solve(l,mid),Solve(mid+1,r);
}
int main()
{
	RI i;for(read(n),i=1;i<=n;++i) read(p[i].x,p[i].y,p[i].w);for(i=1;i<=n;++i) read(p[n+i].x,p[n+i].y,p[n+i].w);
	#define GV(x) (lower_bound(dv+1,dv+dc+1,x)-dv)
	for(sort(p+1,p+2*n+1),Solve(1,n<<1),sort(s+1,s+ct+1),i=1;i<=ct;++i) dv[i]=s[i].y;//Sort by y and divide and conquer; Sort relationships by first dimension
	for(sort(dv+1,dv+ct+1),dc=unique(dv+1,dv+ct+1)-dv-1,i=1;i<=ct;++i) s[i].y=GV(s[i].y);//Discretization
	for(read(Qt),i=1;i<=Qt;++i) read(q[i].x,q[i].y),q[i].w=i;sort(q+1,q+Qt+1);//Sort by query by first dimension
	RI j;for(i=j=1;i<=Qt;ans[q[i].w]=T1.Q(GV(q[i].y+1)),++i) W(j<=ct&&s[j].x<q[i].x) T1.U(s[j].y,s[j].w),++j;//The first two-dimensional counting point
	for(i=Qt,j=ct;i;ans[q[i].w]=max(ans[q[i].w],T2.Q(GV(q[i].y)-1)),--i) W(j&&s[j].x>q[i].x) T2.U(s[j].y,s[j].w),--j;//The second two-dimensional number point
	for(i=1;i<=Qt;++i) ans[i]?writeln(ans[i]):NA();return clear(),0;
}