HDU 4533 威威猫系列故事――晒被子(线段树区间更新+分情况推公式)

「爱情、让人受尽委屈。」 2022-06-10 01:39 154阅读 0赞

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

Input

输入数据首先包含一个正整数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 ）

Output

对于每次询问，请计算并输出ti时有多少面积的被子是湿的，每个输出占一行。

Sample Input

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

Sample Output

0
    1
    5
    8
    8

题解：

一开始完全不会做啊，看博客的题解也没看懂。。。后来看了一整天，自己在图上花了几下，终于理解了别人的博客，这题就是画图推公式

图请看这个神犇的博客：[http://blog.csdn.net/wh2124335/article/details/8739097][http_blog.csdn.net_wh2124335_article_details_8739097]

代码我几乎是照搬神犇的：[http://blog.csdn.net/kirito\_acmer/article/details/47281679][http_blog.csdn.net_kirito_acmer_article_details_47281679]理解了之后自己修改了一些，加上了注释应该更容易理解了qwq

题目意思就是给被子的左下角和右下角坐标，让你求各个时间点湿的被子面积，当时间为t时，水会蔓延到\[t,t\]（从\[0,0\]开始的大方块），注意这里的面积不能重叠，每个之间是互不影响的，想要解决这题一定要结合图形！！假设一个矩形的左下坐标\[x1,y1\]右上\[x2,y2\]，和时间t，那么根据矩形的位置和形状不同，我们可以将矩形被覆盖情况分成3种，第一种是\[t,t\]在这个被子矩形的中间，即都没有超过矩形的上边界和右边界，这时推出面积为(t-x1)(t-y1)，可以发现矩形的面积可以用一个一元二次方程表示，只不过不同时间的系数不同而已，那么我们就根据这个可以建一个线段树，线段表示时间，节点上保存的是该时间t对应的系数情况，因为一元二次方程有3个系数，所以要储存3个数据，然后t时间的被子浸湿面积就是A\*x\*x+B\*x+C，这样就有了完整的思路了，然后回到刚刚的话题，分析第二种情况，就是已经到达了右边界或者已经到达了上边界，这样的t再变化下去就相当于一个一次方程了，这里的A就是0，然后根据是达到了右边界还是上边界再分一次情况就好了，然后第三种情况就是\[t,t\]已经完全覆盖掉了整个矩形，这是A=0，B=0，C就是被子的面积，是不是这题能解出来了呢！！不过还有一个难点就是找出这3种情况的具体条件，这个感觉只能意会不能言传，第一种就是max(x1,y1)<min(x2,y2)时，第二种对应的就分别是x2<y2和y2<x2这两种，分别代表先到达右边界和上边界，然后第三种就很简单了，直接就在区间从max(x2,y2)开始往上到整个大区间更新就好了，至于这三种情况的公式只要画个图就能很简单推出，然后系数就确定了因为被子面积互不影响，所以我们系数直接相加就好了，这题难在这种严密的思路和条件转化，我还是太弱了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    struct node
    {
        int l,r;
        ll cent1,cent2,cent3;//表示区间3个系数累加的结果
    }t[200005*4];
    ll A,B,C;//三个系数要用long long，声明成全局变量
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].cent1=t[k].cent2=t[k].cent3=0;
        if(l==r)
            return;
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushdown(int k)//向下更新
    {
        if(t[k].cent1)
        {
            t[lson].cent1+=t[k].cent1;
            t[rson].cent1+=t[k].cent1;
            t[k].cent1=0;
        }
        if(t[k].cent2)
        {
            t[lson].cent2+=t[k].cent2;
            t[rson].cent2+=t[k].cent2;
            t[k].cent2=0;
        }
        if(t[k].cent3)
        {
            t[lson].cent3+=t[k].cent3;
            t[rson].cent3+=t[k].cent3;
            t[k].cent3=0;
        }
    }
    void update(int l,int r,int k)
    {
        if(t[k].l==l&&t[k].r==r)//找到了就累加
        {
            t[k].cent1+=A;
            t[k].cent2+=B;
            t[k].cent3+=C;
            return;
        }//一开始可以不用更新，因为还没那么快询问
        int mid=M;
        if(r<=mid)
            update(l,r,lson);
        else if(l>mid)
            update(l,r,rson);
        else
        {
            update(l,mid,lson);
            update(mid+1,r,rson);
        }
    }
    ll query(int x,int k)
    {
        if(t[k].l==x&&t[k].r==x)
        {
            return t[k].cent1*x*x+t[k].cent2*x+t[k].cent3;//直接返回二元方程的结果
        }
        pushdown(k);//要向下更新
        int mid=M;
        if(x<=mid)
            return query(x,lson);
        else
            return query(x,rson);
    }
    int main()
    {
        int i,j,k,n,m,test;
        ll x1,x2,y1,y2,x;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            Build(1,200000,1);
            for(i=0;i<n;i++)
            {
                scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);//不用long long输入会错，迷
                if(max(x1,y1)<min(x2,y2))//第一次情况的条件
                {
                    A=1;
                    B=-(x1+y1);
                    C=x1*y1;
                    update(max(x1,y1),min(x2,y2)-1,1);//-1是因为每个节点代表这个点[x,x+1]这一段，所以其实后面的端点那段是不应该算上的
                }
                if(x2<y2)//第二种情况里的第一种到达右边界的情况
                {
                    A=0;
                    B=-x1+x2;
                    C=y1*(x1-x2);
                    update(max(x2,y1),y2-1,1);
                }
                if(y2<x2)//到达上边界的情况
                {
                    A=0;
                    B=-y1+y2;
                    C=x1*(y1-y2);
                    update(max(y2,x1),x2-1,1);
                }
                A=0;//覆盖掉整个被子的情况
                B=0;
                C=(x2-x1)*(y2-y1);
                update(max(x2,y2),200000,1);
            }
            scanf("%d",&m);
            while(m--)
            {
                scanf("%lld",&x);
                printf("%lld\n",query(x,1));//long long输入输出
            }
        }
    
        return 0;
    }

[http_blog.csdn.net_wh2124335_article_details_8739097]: http://blog.csdn.net/wh2124335/article/details/8739097
[http_blog.csdn.net_kirito_acmer_article_details_47281679]: http://blog.csdn.net/kirito_acmer/article/details/47281679