【题解】#102. 矩形的面积交

· · 个人记录

数据结构题被水了过去了，似乎常数还比较小额。

题意

给 n 个互不相交的矩形，左下角坐标为 (x_{1_i},y_{1_i}) 右上角坐标为 (x_{2_i},y_{2_i})。

现有 m 次询问，每次给定一个矩形，对于每次询问输出该矩形与平面上的矩形的公共部分的面积大小。

solution

根据以前所做的题目【园丁的烦恼】，我们可以合理推测一下该题的解法：

将一个大小为 x\cdot y 矩形看作是 x\cdot y 棵树，那两道题就是一样的了，双倍经验。

来观察一下数据范围，m\le 5\cdot 10^5，似乎有点小大额，那我们应该怎么办呢?

不妨先考虑一下只有一个矩形和一次查询的情况：

给定矩形为 (1,1)，(4,4)，查询矩形为 (3,3)，(5,5)。

显然面积为绿色部分，对于查询我们可以将矩形 (3,3)，(5,5) 拆成四个前缀和的形式：

S(3,3)-S(5,3)-S(3,5)+S(5,5)

既然查询可以拆开，那么修改是否也能拆开呢？

显然是能的。

对于矩形 (1,1)，(4,4) 我们可以看作：

这样就可以把每一个矩形用四个二元组 (x,y) 表示。

对于一个查询操作 (x,y)，任意一个修改操作 (x_0,y_0) 对它的贡献为 min(x,x_0)\cdot min(y,y_0)。

例如上图中的查询操作 (5,3) 与修改操作 (4,4) 的交集为 (4,3)，那么贡献显然为 4\cdot 3=12。

同理，上图的答案为：

ans=S(3,3)-S(5,3)-S(3,5)+S(5,5)\\=(1-3-3+9)-(1-3-4+12)-(1-4-3+12)+(1-4-4+16)\\=4-6-6+9\\=1

又显然该题支持离线算法，那么我们就可以用CDQ进行优化。

将所有修改与查询拆成四个二元组 (x,y)，对于修改操作，记 val_i 表示这个矩形是加 (+1) 还是减 (-1)。

以 x 为第一关键字，y 为第二关键字按不下降排序，再按 y 上升归并排序。

归并排序

对于当前操作区间 (l,r)。

令 mid=(l+r)>>1。

首先递归处理操作区间 (l,mid) 和 (mid+1,r)。

处理之后现在考虑怎么合并两个操作区间？

显然前面区间的 x 均小于后面区间的 x，且两个区间内 y 分别呈不下降序，此时我们以 y 为关键字进行归并排序。

显然此时需要分类讨论：（建议先思考一下以下四类情况再看参考做法

对于 lasa 和 lasb 提前预处理即可，在每次进行修改操作和更新 suma,sumb,lasa,lasb 即可。

时间复杂度O（跑的飞快）

注意在拆二元组的时候坐标不要减去1，因为求的是面积（感性理解，我太蒻了，不会证明，考试的时候卡了半个多小时也没改出来。

Code

//压行课次
#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN=5e5+10;
int n,m,tim;
LL ans[MAXN];
struct node{int op,x,y,opt,id;}q[MAXN<<3],p[MAXN<<3];//op 操作类型0为修改1为查询,x,y 坐标 opt 增或减 1为增-1为减 或者操作id 
LL read(){LL sss=0,fff=1;char ccc;ccc=getchar();while(ccc<'0'||ccc>'9'){if(ccc=='-')fff=-1;ccc=getchar();}while(ccc>='0'&&ccc<='9')sss=(sss<<1)+(sss<<3)+(ccc^'0'),ccc=getchar();return sss*fff;}
bool cmp(node x,node y){if(x.x==y.x){if(x.y==y.y)return x.op<y.op;return x.y<y.y;}return x.x<y.x;}
void F(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    F(l,mid);F(mid+1,r);
    int L=l,R=mid+1,k=l;
    LL suma=0,sumb=0,lasa=0,lasb=0;
    for(int i=l;i<=mid;i++) if(q[i].op==0) lasa+=1ll*q[i].opt*q[i].x;//预处理 lasa
    for(int i=mid+1;i<=r;i++) if(q[i].op==0) lasb+=1ll*q[i].opt;//预处理 lasb
    while(L<=mid&&R<=r)
        if(q[L].y<q[R].y)//在前面 
        {
            if(q[L].op==0) sumb+=1ll*q[L].opt*q[L].x*q[L].y,lasa-=q[L].opt*q[L].x,p[k++]=q[L++];//修改操作 
            else ans[q[L].id]+=(1ll*lasb*q[L].x*q[L].y + 1ll*suma*q[L].x)*q[L].opt,p[k++]=q[L++];//查询操作 
        }
        else
        {
            if(q[R].op==0)suma+=1ll*q[R].opt*q[R].y,lasb-=q[R].opt,p[k++]=q[R++];//修改操作 
            else ans[q[R].id]+=(sumb+lasa*q[R].y)*q[R].opt,p[k++]=q[R++];//查询操作 
        }
    while(L<=mid)
        if(q[L].op==0) p[k++]=q[L++];//修改操作 
        else ans[q[L].id]+=(1ll*lasb*q[L].x*q[L].y + 1ll*suma*q[L].x)*q[L].opt,p[k++]=q[L++];//查询操作 
    while(R<=r)
        if(q[R].op==0) p[k++]=q[R++];//修改操作 
        else ans[q[R].id]+=(sumb+lasa*q[R].y)*q[R].opt,p[k++]=q[R++];//查询操作 
    for(int i=l;i<=r;i++) q[i]=p[i];
}
int main()
{
//  freopen("123.in","r",stdin);
//  freopen("123.out","w",stdout);
    n=read();m=read();
    read();read();
    for(int i=1;i<=n;i++)
    {
        int a=read()+1,b=read()+1,c=read()+1,d=read()+1;
        tim++;q[tim]=(node){0,a,b,1,0};
        tim++;q[tim]=(node){0,a,d,-1,0};
        tim++;q[tim]=(node){0,c,b,-1,0};
        tim++;q[tim]=(node){0,c,d,1,0};
    }
    for(int i=1;i<=m;i++)
    {
        int a=read()+1,b=read()+1,c=read()+1,d=read()+1;
        tim++;q[tim]=(node){1,a,b,1,i};
        tim++;q[tim]=(node){1,a,d,-1,i};
        tim++;q[tim]=(node){1,c,b,-1,i};
        tim++;q[tim]=(node){1,c,d,1,i};
    }
    sort(q+1,q+1+tim,cmp);
    F(1,tim);
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}

其他

本来不准备压行的，但是不压行又显得代码冗杂，思想混乱，不便于阅读，故在复制代码时特意将多余的括号与换行去掉

还有，这个不是整体二分,涨知识了