hdu-4052/ LA 5694-Adding New Machine（线段树矩形面积并）

62 阅读 0 评论 41 点赞

我是靠谱客的博主文艺菠萝，最近开发中收集的这篇文章主要介绍hdu-4052/ LA 5694-Adding New Machine（线段树矩形面积并），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.split.hdu.edu.cn/showproblem.php?pid=4052

题意：

给一个w*h的矩阵，给n个小矩形覆盖掉原矩阵，最后要在空余出来的位置塞进一个1*m的新矩形，问有多少种方案数，

因为塞进去的是1*m的矩形，因此对于某一行，如果可用长度为X，则有X-m+1种方案，同理列也一样

先考虑行的：

我们同理把每一个子矩形的左边界延伸m-1格（注意不要越界），最后再塞进一个 X范围为【w-m+1+1，w】，高度为【1，h】的矩形，把原矩阵覆盖后，空出多少的面积，便是多种方案数了。

同理列的处理也一样，把x和y互换，w和h互换即可

于是问题就变成了经典的矩形面积并的问题了

这道题的坐标系比较恶心，给的矩形的坐标不是格点，而是代表一条边。这就很尴尬了。。。最后的处理办法是：

将x1,y1都减1，采用经典的坐标代表点的坐标系。这样写起来就很简单了

注意特判m=1的情况

关于扫描线：

<span style="color:#ff0000;">  long long l=lower_bound(X+1,X+1+num_x,line[i].lx)-X;
            long long r=lower_bound(X+1,X+1+num_x,line[i].rx)-X-1;   --记住扫描线时线段树节点的意义是 一段线</span>

<span style="color:#ff0000;">所以对于从点l到点r之间的 线段 是由离散化后的点l 和点r-1来表示的，并不是l,r</span>

<pre name="code" class="cpp" style="font-size: 12.381px;"><span style="color:#ff0000;">    if (add[i]) sum[i]=X[r+1]-X[l];  因为线段树代表的节点是线段，那么对于i节点代表的这些线段的实际长度就应该是X【r+1】-X【l】
</span>

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const long long mod=1e9+7;

const long long N=50000*2+55;

struct node
{
    long long flag;
    long long  lx,rx,y;
    node (){}
    node (long long a,long long b,long long c,long long d)
    {
        lx=a,rx=b,y=c,flag=d;
    }
    bool operator<(const node &b ) const
    {
        return y<b.y;
    }
};
node line [N];
long long X[N];
long long  sum[4*N];
long long add[4*N];
void pushup(long long i,long long l,long long r)
{
    if (add[i]) sum[i]=X[r+1]-X[l];
    else if (l==r) sum[i]=0;
    else sum[i]=sum[i<<1]+sum[i<<1|1];
}
void update(long long i,long long l,long long r,long long ql,long long qr,long long val)
{
    if (l>qr || ql>r)
        return ;
    if (ql<=l&&qr>=r)
    {
        add[i]+=val;
        pushup(i,l,r);
        return ;
    }
    long long mid=(l+r)>>1;
    update(i<<1,l,mid,ql,qr,val);
    update(i<<1|1,mid+1,r,ql,qr,val);
    pushup(i,l,r);
}
long long xx1[N];
long long yy1[N];
long long xx2[N];
long long yy2[N];
int  main()
{
    long long tmpw,tmph;
    long long w,h,n,m;
    while(scanf("%lld%lld%lld%lld",&w,&h,&n,&m)!=EOF)
    {
        long long ans=0;
        memset(add,0,sizeof add);
        memset(sum,0,sizeof sum);
        tmpw=w,tmph=h;
        w++,h++;
        w=max(1LL,w-m+1);
        long long num=0;
        long long x1,y1,x2,y2;
        for (long long i=1;i<=n;i++)
        {
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            xx1[i]=x1;
            xx2[i]=x2;
            yy1[i]=y1;
            yy2[i]=y2;

            x2++,y2++;
            x1=max(1LL,x1-m+1);
            x2=min(x2,w);
            line[++num]=node(x1,x2,y1,1);
            X[num]=x1;
            line[++num]=node(x1,x2,y2,-1);
            X[num]=x2;
        }
        sort(line+1,line+1+num);
        sort(X+1,X+1+num);
        long long num_x=unique(X+1,X+1+num)-X-1;
        long long ret=0;
        for (long long i=1;i<num;i++)
        {
            long long l=lower_bound(X+1,X+1+num_x,line[i].lx)-X;
            long long r=lower_bound(X+1,X+1+num_x,line[i].rx)-X-1;
            update(1,1,num_x,l,r,line[i].flag);
            ret+=sum[1]*(line[i+1].y-line[i].y);
        }
        ans=(w-1)*(h-1)-ret;


        memset(add,0,sizeof add);
        memset(sum,0,sizeof sum);
        num=0;
        w=tmph,h=tmpw;
        ++w,h++;
        w=max(1LL,w-m+1);
         for (long long i=1;i<=n;i++)
        {
            x1=yy1[i];
            x2=yy2[i];
            y1=xx1[i];
            y2=xx2[i];

            x2++,y2++;
            x1=max(1LL,x1-m+1);
            x2=min(x2,w);
            line[++num]=node(x1,x2,y1,1);
            X[num]=x1;
            line[++num]=node(x1,x2,y2,-1);
            X[num]=x2;
        }
        sort(line+1,line+1+num);
        sort(X+1,X+1+num);
          num_x=unique(X+1,X+1+num)-X-1;
          ret=0;
        for (long long i=1;i<num;i++)
        {
            long long l=lower_bound(X+1,X+1+num_x,line[i].lx)-X;
            long long r=lower_bound(X+1,X+1+num_x,line[i].rx)-X-1;
            update(1,1,num_x,l,r,line[i].flag);
            ret+=sum[1]*(line[i+1].y-line[i].y);
        }
        ans+=(w-1)*(h-1)-ret;
        if (m==1)
            ans=ans/2;

        printf("%lldn",ans);


    }



}