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

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 772 Accepted Submission(s): 184

Problem Description

　　因为马拉松初赛中吃鸡腿的题目让不少人抱憾而归，威威猫一直觉得愧对大家，这几天他悄悄搬到直角坐标系里去住了。
　　生活还要继续，太阳也照常升起，今天，威威猫在第一象限晒了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

Source

2013腾讯编程马拉松复赛第一场（3月29日）

Recommend

liuyiding

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 50020

typedef __int64 LL;

struct node
{
    LL x,y,key;
    LL sum,sum1;
}g[N],g1[N];

int n;
int cnt,cnt1;

int cmp(node t,node t1)
{
    return t.key<t1.key;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(g,0,sizeof(g));
        memset(g1,0,sizeof(g1));
        cnt=0; cnt1=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            node tmp1,tmp2,tmp3,tmp4;
            LL x,y;
            scanf("%I64d%I64d",&x,&y);
            tmp1.x=x; tmp1.y=y; tmp1.key=max(x,y); tmp1.sum=0; tmp1.sum1=0;
            scanf("%I64d%I64d",&x,&y);
            tmp2.x=x; tmp2.y=y; tmp2.key=max(x,y); tmp2.sum=0; tmp2.sum1=0;
            x=max(tmp1.x,tmp2.x);
            y=min(tmp1.y,tmp2.y);
            tmp3.x=x; tmp3.y=y; tmp3.key=max(x,y); tmp3.sum=0; tmp3.sum1=0;
            x=min(tmp1.x,tmp2.x);
            y=max(tmp1.y,tmp2.y);
            tmp4.x=x; tmp4.y=y; tmp4.key=max(x,y); tmp4.sum=0; tmp4.sum1=0;
            g1[cnt1++]=tmp3; g1[cnt1++]=tmp4;
            g[cnt++]=tmp1; g[cnt++]=tmp2;
        }
        sort(g,g+cnt,cmp);
        sort(g1,g1+cnt1,cmp);
        LL tmp=0,tmp1=0; 
        for(int i=0;i<cnt;i++)
        {
            tmp=tmp+(g[i].x+g[i].y);
            tmp1=tmp1+(g[i].x*g[i].y);
            g[i].sum=tmp; g[i].sum1=tmp1;
        }
        tmp=0; tmp1=0;
        for(int i=0;i<cnt1;i++)
        {
            tmp=tmp+g1[i].x+g1[i].y;
            tmp1=tmp1+(g1[i].x*g1[i].y);
            g1[i].sum=tmp; g1[i].sum1=tmp1;
        }
        int q;
        scanf("%d",&q);
        for(int i=0;i<q;i++)
        {
            LL ans=0;
            LL ss;
            scanf("%I64d",&ss);
            LL b=0,d=cnt-1;
            if(cnt==0||ss<=g[0].key) ans=0; 
            else
            {
                while(b<d)
                {
                    int mid=(b+d+1)/2;
                    if(ss<=g[mid].key)
                        d=mid-1;
                    else b=mid;
                }
                ans=ans+(b+1)*ss*ss-ss*(g[b].sum)+g[b].sum1;
            }
            b=0; d=cnt1-1;
            if(cnt1!=0&&ss>g1[0].key) 
            {
                while(b<d)
                {
                    int mid=(b+d+1)/2;
                    if(ss<=g1[mid].key) d=mid-1;
                    else b=mid;
                }
                ans=ans-((b+1)*ss*ss-ss*(g1[b].sum)+g1[b].sum1);
            }
            printf("%I64d\n",ans);
        }
    }
    return 0;
}

最近学了线段树+扫描线，发现这题也可以用这种方法来做。坑爹的是这题竟然卡时间卡的这么紧，我姿势各种不优美于是各种被卡。逼得我用离散化。。结果还是980ms飘过。。。坑啊

其实统一复杂度的何必卡的这么死。。。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <map>
#include <stdlib.h>
using namespace std;
#define N 20020
#define SN 1000000

struct LINE
{
    int k;
    int b,d;
    int flag;
}line[10*N];

int n;
int l[SN],r[SN];
__int64 flags[SN],flagn[SN];
__int64 sum[SN],num[SN];
int save[N*10];
__int64 ganl[N*10],ganr[N*10];
int cao[200200];

int cmp(LINE t,LINE t1)
{
    return t.k<t1.k;
}

void build(int tl,int tr,int s)
{
    l[s]=tl; r[s]=tr;
    sum[s]=0; num[s]=0; flags[s]=0; flagn[s]=0;
    if(tl==tr) return ;
    int mid=(tl+tr)/2;
    build(tl,mid,2*s);
    build(mid+1,tr,2*s+1);
}
void down(int s)
{
    if(flags[s]!=0)
    {
        flags[2*s]+=flags[s];
        sum[2*s] += flags[s]*(r[2*s]-l[2*s]);

        flags[2*s+1]+=flags[s];
        sum[2*s+1] += flags[s]*(r[2*s+1]-l[2*s+1]);
        flags[s]=0;
    }
    if(flagn[s]!=0)
    {
        flagn[2*s]+=flagn[s];
        num[2*s] += flagn[s]*(r[2*s]-l[2*s]);

        flagn[2*s+1]+=flagn[s];
        num[2*s+1] += flagn[s]*(r[2*s+1]-l[2*s+1]);
        flagn[s]=0;
    }
}

void up(int s)
{
    sum[s]=sum[2*s]+sum[2*s+1];
    num[s]=num[2*s]+num[2*s+1];
}


void update(int tl,int tr,int x,int sign,int s)
{
    if(tl==l[s]&&tr==r[s])
    {
        //从tl到tr这段线段，同时加
        flags[s] += -sign*x;
        sum[s] += -sign*x*(ganr[tr]-ganl[tl]);
        //然后就是记录长度
        flagn[s] += sign;
        num[s] += sign*(ganr[tr]-ganl[tl]);
        return ;
    }
    //down(s);//肯定要下推
    if(flags[s]!=0)
    {
        flags[2*s]+=flags[s];
        sum[2*s] += flags[s]*(ganr[r[2*s]]-ganl[l[2*s]]);

        flags[2*s+1]+=flags[s];
        sum[2*s+1] += flags[s]*(ganr[r[2*s+1]]-ganl[l[2*s+1]]);
        flags[s]=0;
    }
    if(flagn[s]!=0)
    {
        flagn[2*s]+=flagn[s];
        num[2*s] += flagn[s]*(ganr[r[2*s]]-ganl[l[2*s]]);

        flagn[2*s+1]+=flagn[s];
        num[2*s+1] += flagn[s]*(ganr[r[2*s+1]]-ganl[l[2*s+1]]);
        flagn[s]=0;
    }

    int mid=(l[s]+r[s])/2;
    if(tr<=mid) update(tl,tr,x,sign,2*s);
    else if(tl>mid) update(tl,tr,x,sign,2*s+1);
    else
    {
        update(tl,mid,x,sign,2*s);
        update(mid+1,tr,x,sign,2*s+1);
    }
    //up(s);
    sum[s]=sum[2*s]+sum[2*s+1];
    num[s]=num[2*s]+num[2*s+1];
}

__int64 query(int tl,int tr,int x,int s)
{
    if(tl==l[s]&&tr==r[s])
    {
        return sum[s]+x*num[s];
    }
    if(flags[s]!=0)
    {
        flags[2*s]+=flags[s];
        sum[2*s] += flags[s]*(ganr[r[2*s]]-ganl[l[2*s]]);

        flags[2*s+1]+=flags[s];
        sum[2*s+1] += flags[s]*(ganr[r[2*s+1]]-ganl[l[2*s+1]]);
        flags[s]=0;
    }
    if(flagn[s]!=0)
    {
        flagn[2*s]+=flagn[s];
        num[2*s] += flagn[s]*(ganr[r[2*s]]-ganl[l[2*s]]);

        flagn[2*s+1]+=flagn[s];
        num[2*s+1] += flagn[s]*(ganr[r[2*s+1]]-ganl[l[2*s+1]]);
        flagn[s]=0;
    }

    int mid=(l[s]+r[s])/2;
    if(tr<=mid) return query(tl,tr,x,2*s);
    else if(tl>mid) return query(tl,tr,x,2*s+1);
    else
    {
        return query(tl,mid,x,2*s)+query(mid+1,tr,x,2*s+1);
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int cnt=0;
        int tcnt=0;
        for(int i=0;i<n;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            line[cnt].k=x1;

            line[cnt].b=y1;
            line[cnt].d=y2;
            line[cnt].flag=1;
            //
            save[tcnt++]=y1;
            save[tcnt++]=y2;
            cnt++;

            line[cnt].k=x2;
            line[cnt].b=y1;
            line[cnt].d=y2;
            line[cnt].flag=-1;
            cnt++;
        }
        int m;
        scanf("%d",&m);
        save[tcnt++]=0;
        for(int i=0;i<m;i++)
        {
            int x;
            scanf("%d",&x);
            line[cnt].k=x;
            line[cnt].b=0;
            line[cnt].d=x;
            save[tcnt++]=x;
            line[cnt].flag=0;
            cnt++;
        }

        sort(save,save+tcnt);

        int pre=0;
        int id=0;
        save[0]=0;
        cao[0]=0;
        id=1;
        for(int i=1;i<tcnt;i++)
        {
            if(save[i]!=pre)
            {
                ganl[id-1]=pre;
                ganr[id-1]=save[i];

                save[id]=save[i];
                cao[save[i]]=id;
                id++;
                pre=save[i];
            }
        }

        for(int i=0;i<cnt;i++)
        {
            line[i].b=cao[line[i].b];
            line[i].d=cao[line[i].d]-1;
        }

        sort(line,line+cnt,cmp);
        //好像直接用区间求和就行了
        build(0,id-1,1);
        //没有关系
        for(int i=0;i<cnt;i++)
        {
            if(line[i].flag!=0)//添加线段
            {
                update(line[i].b,line[i].d,line[i].k,line[i].flag,1);
            }
            else
            {
                //query
                __int64 ans=query(line[i].b,line[i].d,line[i].k,1);
                printf("%I64d\n",ans);
            }
        }
    }
    return 0;
}