HDU 2461 线段树扫描线

给出N个矩形，M次询问

每次询问给出R个。问这R个矩形围成的面积

经典扫面线求面积并，对每次询问的R个点离散化一下

#include "stdio.h"

#include "string.h"

#include "algorithm"

#include "map"

using namespace std;

map<int,int>mp;

struct P

{

    int x1,y1,x2,y2;

}p[21];

struct Mark

{

    int l,r,x,dir;

}mark[41];

struct node

{

    int l,r,y,s;

}data[410];

int h[50];

bool cmp(Mark a,Mark b)

{

    return a.x<b.x;

}

void callen(int k)

{

    if (data[k].s>0) data[k].y=h[data[k].r]-h[data[k].l];

    else

        data[k].y=data[k*2].y+data[k*2+1].y;

}

void build(int l,int r,int k)

{

    int mid;

    data[k].l=l;

    data[k].r=r;

    data[k].y=0;

    data[k].s=0;

    if (l+1==r) return;

    mid=(l+r)/2;

    build(l,mid,k*2);

    build(mid,r,k*2+1);

}

void updata(int l,int r,int k,int op)

{

    int mid;

    if (data[k].l==l && data[k].r==r)

    {

        data[k].s+=op;

        callen(k);

        return ;

    }

    mid=(data[k].l+data[k].r)/2;

    if (r<=mid) updata(l,r,k*2,op);

    else

        if (l>=mid) updata(l,r,k*2+1,op);

    else

    {

        updata(l,mid,k*2,op);

        updata(mid,r,k*2+1,op);

    }

    callen(k);

}

int main()

{

    int Case,cnt,i,ii,r,n,m,ans,k;

    Case=0;

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        if (n==0 && m==0) break;

        for (i=1;i<=n;i++)

            scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);

        printf("Case %d:\n",++Case);

        for (ii=1;ii<=m;ii++)

        {

            scanf("%d",&r);

            for (i=0;i<r;i++)

            {

                scanf("%d",&k);

                mark[i*2].x=p[k].x1;

                mark[i*2].l=p[k].y1;

                mark[i*2].r=p[k].y2;

                mark[i*2].dir=1;

                mark[i*2+1].x=p[k].x2;

                mark[i*2+1].l=p[k].y1;

                mark[i*2+1].r=p[k].y2;

                mark[i*2+1].dir=-1;

                h[i*2]=p[k].y1;

                h[i*2+1]=p[k].y2;

            }

            sort(h,h+r*2);

            cnt=unique(h,h+r*2)-h;

            for (i=0;i<cnt;i++)

                mp[h[i]]=i;

            sort(mark,mark+r*2,cmp);

            for (i=0;i<r*2;i++)

            {

                mark[i].l=mp[mark[i].l];

                mark[i].r=mp[mark[i].r];

            }

            ans=0;

            build(0,cnt,1);

            updata(mark[0].l,mark[0].r,1,mark[0].dir);

            for (i=1;i<r*2;i++)

            {

                ans+=(mark[i].x-mark[i-1].x)*data[1].y;

                updata(mark[i].l,mark[i].r,1,mark[i].dir);

            }

            printf("Query %d: %d\n",ii,ans);

        }

        printf("\n");

    }

    return 0;

}