UVA-11983-Weird Advertisement(线段树+扫描线)[求矩形覆盖K次以上的面积]

题意:

求矩形覆盖K次以上的面积

分析:

k很小，可以开K颗线段树,用sum[rt][i]来保存覆盖i次的区间和,K次以上全算K次

// File Name: 11983.cpp

// Author: Zlbing

// Created Time: 2013/7/21 16:06:54

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int MAXN=6e4+;

struct seg{

    int x1,x2,y;

    int flag;

    bool operator <(const seg& rsh)const{

        return y<rsh.y;

    }

}G[MAXN];

int hash[MAXN];

int col[MAXN<<];

int sum[MAXN<<][];

int n,m;

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

{

    col[rt]=;

    sum[rt][]=hash[r+]-hash[l];

    for(int i=;i<=m;i++)sum[rt][i]=;

    if(l==r)return;

    int m=(l+r)>>;

    build(lson);

    build(rson);

}

void pushup(int rt,int l,int r)

{

    if(col[rt]>=m)

    {

        memset(sum[rt],,sizeof(sum[rt]));

        sum[rt][m]=hash[r+]-hash[l];

    }

    else if(l==r)

    {

        memset(sum[rt],,sizeof(sum[rt]));

        sum[rt][col[rt]]=hash[r+]-hash[l];

    }

    else{

        for(int i=;i<col[rt];i++)sum[rt][i]=;

        for(int i=col[rt];i<m;i++)

        {

            sum[rt][i]=sum[rt<<][i-col[rt]]+sum[rt<<|][i-col[rt]];

        }

        sum[rt][m]=;

        for(int i=m-col[rt];i<=m;i++)

        {

            sum[rt][m]+=sum[rt<<][i]+sum[rt<<|][i];

        }

    }

}

void update(int L,int R,int flag,int l,int r,int rt)

{

    if(L<=l&&R>=r)

    {

        col[rt]+=flag;

        pushup(rt,l,r);

        return;

    }

    int m=(l+r)>>;

    if(L<=m)update(L,R,flag,lson);

    if(R>m)update(L,R,flag,rson);

    pushup(rt,l,r);

}

int main()

{

    int T;

    scanf("%d",&T);

    int cas=;

    while(T--)

    {

        scanf("%d%d",&n,&m);

        int a,b,c,d;

        int xlen=;

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

        {

            scanf("%d%d%d%d",&a,&b,&c,&d);

            c++,d++;

            G[xlen]=(seg){a,c,b,};

            //G[xlen].x1=a,G[xlen].x2=c,G[xlen].y=b,G[xlen].flag=1;

            hash[xlen]=a;

            xlen++;

            G[xlen]=(seg){a,c,d,-};

            //G[xlen].x1=a,G[xlen].x2=c,G[xlen].y=d,G[xlen].flag=-1;

            hash[xlen]=c;

            xlen++;

        }

        sort(G,G+xlen);

        sort(hash,hash+xlen);

        int len=unique(hash,hash+xlen)-hash;

        LL ans=;

        build(,xlen-,);

        for(int i=;i<xlen-;i++)

        {

            int x1=lower_bound(hash,hash+len,G[i].x1)-hash;

            int x2=lower_bound(hash,hash+len,G[i].x2)-hash-;

            update(x1,x2,G[i].flag,,xlen-,);

            //printf("sum[1][m]=%I64d h=%d\n",sum[1][m],G[i+1].y-G[i].y);

            ans+=(LL)sum[][m]*(LL)(G[i+].y-G[i].y);

        }

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

    }

    return ;

}