P3755 离线+树状数组

· · 题解

P3755题解 离线+树状数组

兄弟题目P2163

看到这一道题目，我回想起了以前学习的二维前缀和，里面就用到了容斥原理。那么，这道题目我们为什么不可以用容斥原理呢？我在这里给大家讲解一下。

求面积

我们先规定下，S_{x,y} 表示左下角和右上角为 (0,0) 和 (x,y) 的矩阵内的功率总和。用左上角和右上角来表示一个矩形。用 f((x1,y1),(x2,y2)) 表示图形面积的表示方法。

我们可以观察下面的一幅图片。

这一幅图片我们可以用容斥原理来解决。我们看下一幅图。

在这一幅图形里我标出了许多的颜色。我们可以用绿色+紫色-蓝色-黄色这样的方法来表示橙色矩形的面积，也可以说成是它内部的和。

于是可以得出公式：

f((x1,y1),(x2,y2))=s_{x2,y2}+s_{x1,y1}-s_{x1,y2}-s_{x2,y1}

但是这里仅仅是面积，至于这里是连长都要计算的我们应该另外考虑。

我们发现，橙色的边缘是要用到的，所以我们不用的边缘应该需要再原来的基础上 -1 。

对于重复的部分，我们发现，黄色部分是重复的，所以我们的重复部分也是需要 -1 的。由此，公式可以变为：

f((x1,y1),(x2,y2))=s_{x2,y2}+s_{x1-1,y1-1}-s_{x1-1,y2}-s_{x2,y1-1}

但是再打这道题目的时候我是没有想到的，只是后来自己调试的时候才改的，所以调试也是很重要的。

离散化

我们注意到，x,y 都是 int 范围的，所以我们数组肯定开不下，所以就需要用到离散化了。

至于用什么去离散。我认为，需要离散的东西如下：

如何去重复的数字，都是紫题了，大家自己思考吧。

树状数组优化快速求解

接下来就是求解的问题了。

本题有两个限制条件，那我们是不是可以通过枚举的顺序把一种条件抵消，并且通过数据结构把另一种抵消呢？在这一道题目里，我们可以离线，并不一定出来一个马上有答案，先存着。而求答案的顺序，就是排序之后以 x 轴升序扫描一遍，有点像扫描线的样子。

扫到自己之后，由于此时 x 都是比自己小的，所以用树状数组统计 y 比自己小的功率之和就可以了。

统计点的时候，我们可以这样开结构体，并且把基站和区间的四个角。

struct data{
    int x,y,id,mul,xx;
   //id：序号，方便后面统计答案，并且作为排序依据，如果是基站，那么id为0
   //mul：乘，就是统计乘1还是-1，后面统计答案方便
   //xx：当前点的功率
}point[2500005];

但是排序部分我认为 cmp 这个函数需要说明一下。

inline bool cmp(data x,data y){
    if(x.x==y.x){
        return x.id<y.id;//如果x一样的话，就用id来辅助，由于我把基地的id设为0，所以小的在前，大的在后，确保统计
    }
    return x.x<y.x;//以x为主体
}

编写代码

然后我们就可以写出我们的代码了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int N=2500005,INF=1e9;
int n,m,tem_y[2500005],x,y,z,tot,x_1,y_1,c[2500005],ans[2500005],pose;//tem_y离散化工具
struct data{
    int x,y,id,mul,xx;
}point[2500005];
inline void read(int &res){//读优加速
    res=0;int f=1;char ch=getchar();
    while('0'>ch||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9'){
        res=(res<<1)+(res<<3)+(ch^48);
        ch=getchar();
    }
    res*=f;
}
inline bool cmp(data x,data y){
    if(x.x==y.x){
        return x.id<y.id;
    }
    return x.x<y.x;
}
//树状数组
inline int lowbit(int x){return x&-x;}
inline void add(int x,int k){
    while(x<=tem_y[0]){
        c[x]+=k;
        x+=lowbit(x);
    }
}
inline int get(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

inline int find(int x){//我用二分去寻找离散之后的值
    int mid,l=1,r=tem_y[0];
    while(l<=r){
        mid=l+r>>1;
        if(tem_y[mid]==x) return mid;
        if(tem_y[mid]>x) r=mid-1;
        else l=mid+1;
    }
}
signed main(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(x),read(y);read(z);
        tem_y[++tem_y[0]]=y;
        point[++tot]=(data){x,y,0,0,z};
    }
    for(int i=1;i<=m;i++){
        read(x),read(y),read(x_1),read(y_1);
      //x_1,y_1是右上角，x,y是左上角
        tem_y[++tem_y[0]]=y-1;
        tem_y[++tem_y[0]]=y_1;
      //把四个角落都弄一边，记得-1
        point[++tot]=(data){x-1,y-1,i,1,0};
        point[++tot]=(data){x_1,y_1,i,1,0};
        point[++tot]=(data){x_1,y-1,i,-1,0};
        point[++tot]=(data){x-1,y_1,i,-1,0};
    }

   //去重
    sort(tem_y+1,tem_y+tem_y[0]+1);
    for(int i=1;i<tem_y[0];i++) if(tem_y[i]==tem_y[i+1]) tem_y[i]=INF;
    sort(tem_y+1,tem_y+tem_y[0]+1);
    while(tem_y[tem_y[0]]==INF) --tem_y[0];
    sort(point+1,point+tot+1,cmp);

    for(int i=1;i<=tot;i++){
        pose=find(point[i].y);
      //分类讨论，如果是矩形的四边形就计算，反之就加入这个点
        if(point[i].id) ans[point[i].id]+=point[i].mul*get(pose);
        else add(pose,point[i].xx);
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}

谢谢大家。