题面
题解
挺神奇的一道题。
正解是对 \(y\) 坐标分治。
每次考虑 \(y\) 坐标在 \([l,mid]\) 范围内的红点和 \(y\) 坐标在 \([mid+1,r]\) 范围内的蓝点匹配成点对的贡献。
考场上尝试过这种做法，但发现时间复杂度不对劲就弃掉了。
但有一种极妙的剪枝方法，它结合了题目特殊的询问条件，得出并依靠了下面的这条结论：
只有选择的红点为 \(y\) 坐标在 \([l,mid]\) 范围内权值最大的那个红点、或者选择的蓝点为 \(y\) 坐标在 \([mid+1,r]\) 范围内权值最大的那个蓝点，这样的点对才有贡献。
证明：
考虑反证法：
假设询问 \(i\) 不满足上述的结论，不妨设询问 \(i\) 为 \(L_i,R_i\)。
假设询问 \(i\) 找到的最大点权和的点对是在 \(y\) 坐标在 \([l,mid]\) 范围内的红点 \(R\) 和 \(y\) 坐标在 \([mid+1,r]\) 范围的蓝点 \(B\)，且 \(R\) 不是 \(y\) 坐标在 \([l,mid]\) 范围内权值最大的红点，\(B\) 也不是 \(y\) 坐标在 \([mid+1,r]\) 范围内权值最大的蓝点。
那么我们找到 \(y\) 坐标在 \([l,mid]\) 范围内权值最大的红点，记为 \(R_{max}\)；找到 \(y\) 坐标在 \([mid+1,r]\) 范围内权值最大的蓝点，记为 \(B_{max}\)。
注意到询问的第二个条件是要求两个点均在区间 \([L_i,R_i]\) 内或两个点均在区间 \([L_i,R_i]\) 外。（注意题目保证了所有的 \(x_i,L_i,R_i\) 各不相同）
不妨设 \(B,R\) 均在区间内（均在区间外的情况同理）：
- 显然如果选 \(B,R_{max}\) 符合询问的第二个条件的话，就会选择 \(B,R_{max}\)，因为这么选更优。但既然没有选择，说明 \(R_{max}\) 在区间外。
- 显然如果选 \(B_{max},R\) 符合询问的第二个条件的话，就会选择 \(B_{max},R\)，因为这么选更优。但既然没有选择，说明 \(B_{max}\) 在区间外。
所以我们得出结论：\(B_{max}\) 和 \(R_{max}\) 均在区间外。
那么选 \(B_{max}\) 和 \(R_{max}\) 显然是更优的，与假设矛盾。
所以结论正确。
所以我们可以按最开始说的对 \(y\) 分治，而合并两个子区间时有贡献的点对个数是 \(O(\text{当前区间长度})\) 级别的，所以总的有贡献的点对是 \(O(n\log n)\) 级别的。
然后可以把询问离线排序，变成简单的二维数点问题，可以用树状数组解决。
时间复杂度 \(O(n\log ^2n+q\log n)\)。
代码如下：
#include<bits/stdc++.h>
#define N 100010
#define M 500010
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Point
{
int x,y,val;
bool opt;
}p[N<<1];
inline bool operator < (Point a,Point b)
{
return a.y<b.y;
}
struct Query
{
int l,r,id;
}q[M];
inline bool operator < (Query a,Query b)
{
return a.l<b.l;
}
int n,nn,Q,b1[N],b2[N],val1[N],val2[N];
int lowbit[N],c1[N],c2[N];
int Ans[M];
vector<int>v[N];
void solve(int k,int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1,lc=k<<1,rc=k<<1|1;
solve(lc,l,mid),solve(rc,mid+1,r);
int max1=0,max2=0;
for(int i=l;i<=mid;i++)
if(!p[i].opt&&(!max1||p[i].val>p[max1].val)) max1=i;
for(int i=mid+1;i<=r;i++)
if(p[i].opt&&(!max2||p[i].val>p[max2].val)) max2=i;
if(!max1||!max2) return;
for(int i=l;i<=mid;i++)
if(!p[i].opt) v[p[i].x].push_back(p[max2].x);
for(int i=mid+1;i<=r;i++)
if(i!=max2&&p[i].opt) v[p[max1].x].push_back(p[i].x);
}
inline void update1(int x,int y)
{
for(;x;x-=lowbit[x]) c1[x]=max(c1[x],y);
}
inline int query1(int x)
{
int ans=-1;
for(;x<=n;x+=lowbit[x]) ans=max(ans,c1[x]);
return ans;
}
inline void update2(int x,int y)
{
for(;x<=n;x+=lowbit[x]) c2[x]=max(c2[x],y);
}
inline int query2(int x)
{
int ans=-1;
for(;x;x-=lowbit[x]) ans=max(ans,c2[x]);
return ans;
}
int main()
{
memset(c1,-1,sizeof(c1));
memset(c2,-1,sizeof(c2));
memset(Ans,-1,sizeof(Ans));
n=read(),nn=n<<1;
for(int i=1;i<=n;i++) lowbit[i]=i&-i;
for(int i=1;i<=n;i++)
b1[i]=p[i].x=read(),p[i].y=read(),p[i].val=read(),p[i].opt=0;
for(int i=1;i<=n;i++)
b2[i]=p[n+i].x=read(),p[n+i].y=read(),p[n+i].val=read(),p[n+i].opt=1;
sort(b1+1,b1+n+1),sort(b2+1,b2+n+1);
for(int i=1;i<=n;i++)
{
p[i].x=lower_bound(b1+1,b1+n+1,p[i].x)-b1;
val1[p[i].x]=p[i].val;
p[n+i].x=lower_bound(b2+1,b2+n+1,p[n+i].x)-b2;
val2[p[n+i].x]=p[n+i].val;
}
sort(p+1,p+nn+1);
solve(1,1,nn);
Q=read();
for(int i=1;i<=Q;i++)
{
q[i].l=read(),q[i].r=read(),q[i].id=i;
q[i].l=lower_bound(b1+1,b1+n+1,q[i].l)-b1;
q[i].r=lower_bound(b2+1,b2+n+1,q[i].r)-b2;
}
sort(q+1,q+Q+1);
int tmp=1;
for(int i=1;i<=n;i++)
{
while(tmp<=Q&&q[tmp].l==i)
{
Ans[q[tmp].id]=query1(q[tmp].r);
tmp++;
}
for(int j=0,size=v[i].size();j<size;j++)
update1(v[i][j],val1[i]+val2[v[i][j]]);
}
while(tmp<=Q)
{
Ans[q[tmp].id]=query1(q[tmp].r);
tmp++;
}
tmp=Q;
while(q[tmp].l>n) tmp--;
for(int i=n;i>=1;i--)
{
for(int j=0,size=v[i].size();j<size;j++)
update2(v[i][j],val1[i]+val2[v[i][j]]);
while(tmp&&q[tmp].l==i)
{
Ans[q[tmp].id]=max(Ans[q[tmp].id],query2(q[tmp].r-1));
tmp--;
}
}
for(int i=1;i<=Q;i++)
printf("%d\n",Ans[i]);
return 0;
}
/*
2
-3 1 1
-6 3 10
3 4 100
5 2 1000
5
-5 4
-2 6
-4 1
-10 10
-1 2
*/