首页 > ACM题库 > HDU-杭电 > HDU 4533-威威猫系列故事――晒被子-线段树-[解题报告]HOJ
2015
07-17

HDU 4533-威威猫系列故事――晒被子-线段树-[解题报告]HOJ

威威猫系列故事――晒被子

问题描述 :

  因为马拉松初赛中吃鸡腿的题目让不少人抱憾而归,威威猫一直觉得愧对大家,这几天他悄悄搬到直角坐标系里去住了。
  生活还要继续,太阳也照常升起,今天,威威猫在第一象限晒了N条矩形的被子,被子的每条边都和坐标轴平行,不同被子的某些部分可能会叠在一起。这时候,在原点处突然发了场洪水,时间t的时候,洪水会蔓延到( t, t ),即左下角为( 0, 0 ) ,右上角为( t, t )的矩形内都有水。
  悲剧的威威猫想知道,在时间t1, t2, t3 … tx 的时候,他有多少面积的被子是湿的?

输入:

输入数据首先包含一个正整数T,表示有T组测试数据;
每组数据的第一行首先是一个整数N,表示有N条被子;
接下来N行,每行包含四个整数x1, y1, x2, y2,代表一条被子的左下角和右上角的坐标;
然后接下来一行输入一个整数x,表示有x次询问;
再接下来x行,输入x个严格单调递增的整数,每行一个,表示威威猫想知道的时间ti。

[Technical Specification]
T <= 5
0 < N <= 20000
1 <= x1 < x2 <= 200000
1 <= y1 < y2 <= 200000
1 <= x <= 20000
1 <= ti <= 200000 (1 <= i <= x )

输出:

输入数据首先包含一个正整数T,表示有T组测试数据;
每组数据的第一行首先是一个整数N,表示有N条被子;
接下来N行,每行包含四个整数x1, y1, x2, y2,代表一条被子的左下角和右上角的坐标;
然后接下来一行输入一个整数x,表示有x次询问;
再接下来x行,输入x个严格单调递增的整数,每行一个,表示威威猫想知道的时间ti。

[Technical Specification]
T <= 5
0 < N <= 20000
1 <= x1 < x2 <= 200000
1 <= y1 < y2 <= 200000
1 <= x <= 20000
1 <= ti <= 200000 (1 <= i <= x )

样例输入:

1
2
1 1 3 3 
2 2 4 4
5
1
2
3
4
5

样例输出:

0
1
5
8
8

方法一:

把(0,0),(t,t)看成是一个大矩形的话,那么这个大矩形的右上坐标x是等于y的,有了这个就好办了,

我们可以维持一颗关于t的线段树,比如现在对一个X矩形(x1,y1),(x2,y2)来说如果t>=Max(x2,y2),那么这个面积直接加上;

在关于t的这颗线段树上操作也就是相当于更新(Max(x2,y2)~Max(t))这个区间,而对于(0~MAx(x1,y1))这个区间是无影响的;

现在在于怎么处理MAx(x1,y1)~Min(x2,y2)和Max(MAx(x1,y2),Min(x2,y2))~Max(x2,y2)这两个区间

如果Max(x1,y2)<Min(x2,y2),那么这端区间和X矩形的相交的面积就是(t-x1)*(t-y1);而这里t是变动的,

所以我把式子变一下得t*t-(x1+y1)*t+x1*y1,这样我们可以开三个数组保存这个方程的系数(1,-(x1+y1),x1*y1),

因为这三个系数是常数并且可以进行加减运算,然后一样可以利用线段树的lazy思想,系数到最后再计算是一样的。

用类似的方法去处理Max(MAx(x1,y2),Min(x2,y2))~Max(x2,y2)这个区间,画个图就明白了;

对于Max(MAx(x1,y2),Min(x2,y2))~Max(x2,y2)这个区间处理有两种情况(如下图,手画的,只能看个大概):

这是第一种情况(y2>x2):

威威猫系列故事――晒被子

威威猫系列故事――晒被子

重叠面积为(t-x1)*(t-y1)-(t-x2)*(t-y1)展开为:(-x1-y1+y1+x2)*t+y1*(x1-x2);和前面一样在线段树区间上更新这个方程的系数

第二种情况(x2>y2):

威威猫系列故事――晒被子

重叠面积为(t-x1)*(t-y1)-(t-x1)*(t-y2)展开为:(-x1-y1+x1+y2)*t+x1*(y1-y2);和前面一样在线段树区间上更新这个方程的系数

上面的介绍体现在POP函数里面,主要的思想是利用保存系数达到目的;

今天比赛太挫了,A题弄了我好久wa了好几次,D题也没在比赛的时候过,太悲剧了威威猫系列故事――晒被子

#include<stdio.h>

#include<string.h>

#define _LL __int64

int n=200000;
_LL A[800000],B[800000],C[800000];

void update(int i,int l,int r,int a,int b,_LL *v)
{
    int mid;
    if(a>b) return;
    if(a==l&&r==b)
    {
        A[i]+=v[0];B[i]+=v[1];C[i]+=v[2];
        return ;
    }
    mid=(l+r)/2;
    if(b<=mid) update(i<<1,l,mid,a,b,v);
    else if(a>mid) update(i<<1|1,mid+1,r,a,b,v);
    else {
        update(i<<1,l,mid,a,mid,v);
        update(i<<1|1,mid+1,r,mid+1,b,v);
    }
}

_LL query(int i,int l,int r,_LL p)
{
    int mid;
    if(l==r) return p*p*A[i]+p*B[i]+C[i];
    mid=(l+r)/2;
    A[i<<1]+=A[i];B[i<<1]+=B[i];C[i<<1]+=C[i];
    A[i<<1|1]+=A[i];B[i<<1|1]+=B[i];C[i<<1|1]+=C[i];
    A[i]=B[i]=C[i]=0;
    if(p<=mid) return query(i<<1,l,mid,p);
    else return query(i<<1|1,mid+1,r,p);
}

void POP(_LL a,_LL b,_LL x,_LL y)
{
    int m=a<b?b:a,t=x>y?x:y,t2=x>y?y:x;
    _LL v[3]={0,0,0};
    v[2]=(x-a)*(y-b);
    update(1,1,n,t+1,n,v);
    v[0]=1;v[1]=-(a+b);v[2]=a*b;
    if(t2>=m) update(1,1,n,m+1,t2,v);
    if(y>x){
        v[0]-=1;
        v[1]+=x+b;v[2]-=x*b;
    }
    else if(x>y)
    {
        v[0]-=1;
        v[1]+=a+y;v[2]-=a*y;
    }
    if(m>t2) t2=m;
    update(1,1,n,t2+1,t,v);
}

int main()
{
    int cas,m,i;
    _LL x1,x2,y1,y2;
    scanf("%d",&cas);
    while(cas–)
    {
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
            POP(x1,y1,x2,y2);
        }
        scanf("%d",&m);
        while(m–)
        {
            scanf("%I64d",&x1);
            printf("%I64d\n",query(1,1,n,x1));
        }
    }
    return 0;

}

题目大意:

在第一象限中给出若干矩形(点范围1e5,矩形个数20000),现在给出一些询问(次数20000),每次询问给出一个整数t,问在(0,0)到(t,t)范围的矩形面积和。

解题思路:

考虑每次询问t,对于单一矩形的面积的计算方法~
威威猫系列故事――晒被子
威威猫系列故事――晒被子
对于询问t。计算如图矩形所被包含的面积可以用矩形面积S[TCFI]-S[TJGI],而S[TCFI]=(t-Fx)*(t-Fy);S[TJGI]=(t-Gx)*(t-Gy)
换句话说就是用[T和矩形左下角的点形成的面积]减去[T和矩形右下角形成的矩形面积]就是这个矩形被包含的面积!
下面来看一个类似的情况:
威威猫系列故事――晒被子
威威猫系列故事――晒被子
对于这次询问t。当前矩形被包涵的面积是S[TLFI]-S[TLEK]。即[T和矩形左下角点形成的面积]减去[T和矩形左上角点形成的矩形的面积]
那么对于矩形被包含进(t,t)范围是什么情况呢?
威威猫系列故事――晒被子
威威猫系列故事――晒被子
这时候的面积是EHGF的面积,但我们还想计算这个面积时和T有关。仿照前面的讨论,发现S[EHGF]不就是S[TLFI]-S[TLEN]-S[TMGI]+S[TMHN]么?
换句话描述,就是[T和矩形左下角点形成的矩形面积]减去[T和矩形左上角点形成的矩形面积]减去[T和矩形右下角点形成的矩形面积]加上[T和矩形右上角点形成的矩形面积]
那么我们得到了如下算法:
输入询问t
sum=0
遍历所有矩形的四个顶点
   如果该顶点在(0,0)-(t,t)的范围内
      如果当前顶点是它所在矩形的左上角或右下角的点那么sum+=[(t,t)和该点形成的矩形的面积]
      否则sum-=[(t,t)和该点形成的矩形的面积]
返回sum
对于这题目的数据来说时间复杂度肯定是不够的,我们要想办法优化它。。。
观察我们计算[T和当前点形成的矩形面积]时的方法:
假设当前点坐标是(x,y)
那么S=(t-x)*(t-y)
我们可以将上式展开:S=t*t-t(x+y)+xy
我们可不可以将上式分成的三部分分别求和呢?答案是可以的!

那么我们可以将所有矩形左下角和右上角的点分到一组a(因为它们和T形成的矩形面积都是做“加”运算),把左上角和右下角的点分到一组b(因为它们和T形成的矩形面积都是做“减”运算)
那么结果可以写成sigma[a中在(t,t)范围内的点和T形成的矩形面积]-sigma[b在(t,t)范围内的点和T形成的矩形面积]
很容易想到,我们将a,b中的点分别按max(x,y)排序。然后正确的算法已经呼之欲出了!
对于每次询问t,我们二分找到它在a,b中的位置n,m(即max(x,y)恰好不超过t的最大的下标,a,b都是从1开始编号)
答案不就是
Sum(Sa)-Sum(Sb)
=sigma[t*t-t*(x+y)+xy](a中点)-sigma[t*t-t*(x+y)+xy](b中点)
=[sigma(t*t)-sigma(x+y)+sigma(xy)](a中点)-[sigma(t*t)-sigma(x+y)+sigma(xy)](b中点)
计算sigma(t*t)只要t*t乘个数(对于a是n,对于b是m)即可!
计算sigma(x+y)和sigma(xy)只要预处理一下即可!
现在算法如下:
检查所有矩形的四个顶点
        如果是左下角或是右上角的点那么放到a的末尾
        否则放到b的末尾
将a,b中的所有点按max(x,y)排序
定义suma,sumb表示a、b的点中下标1到下标i的所有点的x+y和
定义suma_mul,sumb_mul表示a、b的点中下标1到下标i的所有点的x*y和
循环 i=1 到 2*N 
        suma[i]=suma[i-1]+a[i].x+a[i].y
        sumb[i]=sumb[i-1]+b[i].x+b[i].y
        suma_mul[i]=suma_mul[i-1]+a[i].x*a[i].y
        sumb_mul[i]=sumb_mul[i-1]+b[i].y*b[i].y
对于每次询问t
        二分找到在a,b中max(x,y)恰好不超过t的下标n,m
        输出答案(t*t*n-t*suma[n]+suma_mum[n])-(t*t*m-t*sumb[m]+sumb_mul[m])
另外:由于本题的询问范围是固定且是递增的,所以可以考虑在这里再次优化时间复杂度

    #include<cstdio>  
    #include<algorithm>  
    #include<cstring>  
    #include<iostream>  
    using namespace std;  
    struct point{  
        long long x,y;  
        friend bool operator < (const point &a,const point &b){  
            return max(a.x,a.y)<max(b.x,b.y);  
        }  
    };  
    point a[50001];  
    long long suma[50001],sumb[50001],suma_mul[50001],sumb_mul[50001];  
    point b[50001];  
    int find_a(int l,int r,long long t){  
        while(r>=l){  
            int m=(l+r)/2;  
            if(t==max(a[m].x,a[m].y))return m;  
            if(t<max(a[m].x,a[m].y))r=m-1;  
            else l=m+1;  
        }  
        return l;  
    }  
    int find_b(int l,int r,long long t){  
        while(r>=l){  
            int m=(l+r)/2;  
            if(t==max(b[m].x,b[m].y))return m;  
            if(t<max(b[m].x,b[m].y))r=m-1;  
            else l=m+1;  
        }  
        return l;  
    }  
    int main(){  
        int T;  
        scanf("%d",&T);  
        while(T--){  
            memset(suma,0,sizeof(suma));  
            memset(sumb,0,sizeof(sumb));  
            memset(suma_mul,0,sizeof(suma_mul));  
            memset(sumb_mul,0,sizeof(sumb_mul));  
            memset(a,0,sizeof(a));  
            memset(b,0,sizeof(b));  
            int n;  
            scanf("%d",&n);  
            for(int i=1;i<=n;i++){  
                long long x1,y1,x2,y2;  
                scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);  
                //cin>>x1>>y1>>x2>>y2;  
                a[2*i-1]=(point){x1,y1};  
                a[2*i]=(point){x2,y2};  
                b[2*i-1]=(point){x1,y2};  
                b[2*i]=(point){x2,y1};  
            }  
            sort(a,a+2*n+1);  
            sort(b,b+2*n+1);  
            for(int i=1;i<=2*n;i++){  
                suma[i]=suma[i-1]+a[i].x+a[i].y;  
                sumb[i]=sumb[i-1]+b[i].x+b[i].y;  
                suma_mul[i]=suma_mul[i-1]+a[i].x*a[i].y;  
                sumb_mul[i]=sumb_mul[i-1]+b[i].x*b[i].y;  
            }  
            suma[2*n+1]=suma[2*n];  
            sumb[2*n+1]=sumb[2*n];  
            suma_mul[2*n+1]=suma_mul[2*n];  
            sumb_mul[2*n+1]=sumb_mul[2*n];  
            int q;  
            scanf("%d",&q);  
            while(q--){  
                long long x;  
                scanf("%I64d",&x);  
                long long sum=0;  
                int m=find_a(1,2*n,x);  
                if(m>2*n)m=2*n;  
                if(x<max(a[m].x,a[m].y))m--;  
                sum=m*x*x-x*suma[m]+suma_mul[m];  
                m=find_b(1,2*n,x);  
                if(m>2*n)m=2*n;  
                if(x<max(b[m].x,b[m].y))m--;  
                sum=sum-(m*x*x-x*sumb[m]+sumb_mul[m]);  
                printf("%I64d\n",sum);  
                //cout<<sum<<endl;  
            }  
        }  
    }  

参考:http://blog.csdn.net/sprintfwater/article/details/8738684