P5873 题解

天命之路 · 2021-10-16 14:44:43 · 题解

写在前面

一道一眼的 cdq 分治题

当然了啊，假如你想写树套树或者 KD-Tree，那当我没说

正题

首先把总对数对化为“加入一个图形时新贡献的对数”，最后把答案求前缀和即可

然后看到这种题目，考虑一下，发现加入一个矩形十分难以处理，决定化动为静

化动态为静态，当然 cdq，品牌首选，匠心传承

考虑 cdq(l,r) 的过程

首先往左右两边递归，不需多言

然后区间分为 [l,mid] 和 [mid+1,r] ，开始计算

我们要计算两个东西：

左半边点对右半边矩形的贡献
左半边矩形对右半边点的贡献

先掏个树状数组出来

考虑把一个矩形(x1,y1,x2,y2) 拆成 (x1-1,y1,y2) 和 (x2,y1,y2) ，他们分别表示 x\le x1-1,y \in[y1,y2] 的点的数量和 x\le x2,y \in[y1,y2] 的点的数量，最后将两相减即可

然后把他们和点扔在一起，按 x 坐标从小到大排序

尤其注意！！！坐标相同时，修改排在询问前面，这是 cdq 分治的铁则

然后遍历，遇点加点，遇询问查询区间和即可

再看第二部分

因为矩形变成了修改，所以我们要借鉴一下扫描线的套路

把矩形 (x1,y1,x2,y2) 拆成两条带"权"的线段 (x1,y1,y2,1) 和 (x2+1,y1,y2,-1) 表示当直线扫到 x = x1

时，y \in [y1,y2] 的点都会多被贡献一个，当扫到 x = x2+1 时，y\in[y1,y2] 的点都会被少贡献一个

依照之前的方法排序

遇修改则区间加，遇询问则单点查，树状数组区间加可以用差分，不会的请左转 “树状数组2” 了解详情

然后就做完了，记得离散化 y 坐标

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
struct event{
    int tp;
    int x,y;
    int a1,b1,a2,b2;
    event(){}
    event(const int _x,const int _y):
    x(_x),y(_y){ tp = 1;}
    event(const int _a1,const int _b1,const int _a2,const int _b2):
    a1(_a1),b1(_b1),a2(_a2),b2(_b2){tp = 2;}
};
event Q[N];
ll ans[N];
int n;
int valy[N*3],leny=0;
#define idx(x) (lower_bound(valy+1,valy+leny+1,(x))-valy)
struct line{
    int x,l,r,tp,id;
    line(){}
    line(const int _x,const int _l,const int _r,const int _tp,const int _id):
    x(_x),l(_l),r(_r),tp(_tp),id(_id){}
};
int tr[N*3];
#define lowbit(x) (x&(-x))
inline void upd(int x,int v) { ++x;for(int i=x;i<=leny+1;i+=lowbit(i)) tr[i] += v;}
inline int Sum(int x) {++x;int res = 0;for(int i=x;i;i^=lowbit(i)) res += tr[i];return res;}
inline int Qry(int l,int r) { return Sum(r)-Sum(l-1);}
inline void inc(int l,int r,int v) { upd(l,v);upd(r+1,-v);}
inline bool cmp1(const line &a,const line &b)
{
    if(a.x != b.x) return a.x < b.x;
    if(a.tp != 0 && b.tp == 0) return true;   //修改排在询问前面，这里通过判断tp是否为0来区分修改和询问
    if(a.tp == 0 && b.tp != 0) return false;
    return a.tp <b.tp; 
}
inline bool cmp2(const line &a,const line &b)
{
    if(a.x != b.x) return a.x < b.x;
    if(a.tp != 0 && b.tp == 0) return false;  //到了第二部分,tp的赋值规则有所改变，cmp要跟着改变
    if(a.tp == 0 && b.tp != 0) return true;
    return a.tp <b.tp;  //你这里写true 或false 是不行的，因为sort 的 CMP 函数必须满足严格偏序关系，即具有非自反，反对称，传递性的关系，否则就会出现奇怪的 RE 和 TLE 等问题
}
line a[N*3];
inline void cdq(int l,int r)
{
    if(l == r) return;
    int mid = l + r >> 1;
    cdq(l,mid);cdq(mid+1,r);
    //左半边矩形对右半边点的贡献

    int tot = 0;
    for(int i=l;i<=mid;i++)
        if(Q[i].tp == 2) 
        a[++tot] = line(Q[i].a1,Q[i].b1,Q[i].b2,1,0),
        a[++tot] = line(Q[i].a2+1,Q[i].b1,Q[i].b2,-1,0);
    for(int i=mid+1;i<=r;i++)
        if(Q[i].tp == 1)
            a[++tot] = line(Q[i].x,Q[i].y,Q[i].y,0,i);
    sort(a+1,a+tot+1,cmp1);
    for(int i=1;i<=tot;i++)
    {
        if(a[i].tp != 0)
        inc(a[i].l,a[i].r,a[i].tp);
        else ans[a[i].id] += Sum(a[i].l);
    }
    for(int i=1;i<=tot;i++) if(a[i].tp != 0) inc(a[i].l,a[i].r,-a[i].tp);
    tot = 0;
    //左半边点对右半边矩形的贡献
    for(int i=l;i<=mid;i++)
        if(Q[i].tp == 1)
            a[++tot] = line(Q[i].x,Q[i].y,Q[i].y,0,0);
    for(int i=mid+1;i<=r;i++)
        if(Q[i].tp == 2)
            a[++tot] = line(Q[i].a1-1,Q[i].b1,Q[i].b2,-1,i),
            a[++tot] = line(Q[i].a2,Q[i].b1,Q[i].b2,1,i);
    sort(a+1,a+tot+1,cmp2);
    for(int i=1;i<=tot;i++)
    {
        if(a[i].tp == 0) upd(a[i].l,1);
        else
            ans[a[i].id] += a[i].tp * Qry(a[i].l,a[i].r);
    }
    for(int i=1;i<=tot;i++) if(a[i].tp == 0) upd(a[i].l,-1);  //清空，不要Memset,cdq(l,r) 的算贡献的复杂度必须控制在 r-l 量级，才能保证总复杂度正确
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int tp;
        scanf("%d",&tp);
        if(tp == 1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            Q[i] = event(x,y);
            valy[++leny] = y;
        }
        else
        {
            int a1,b1,a2,b2;
            scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
            Q[i] = event(a1,b1,a2,b2);
            valy[++leny] = b1;valy[++leny] = b2;
        }
    }
    sort(valy+1,valy+leny+1);
    leny = unique(valy+1,valy+leny+1) - valy - 1;
    for(int i=1;i<=n;i++)
        if(Q[i].tp == 1) Q[i].y = idx(Q[i].y);
        else Q[i].b1 = idx(Q[i].b1),Q[i].b2 = idx(Q[i].b2);
    cdq(1,n);
    for(int i=1;i<=n;i++) ans[i] += ans[i-1];
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}

完结撒花！！！