UVA 11983 Weird Advertisement

题意：求矩形覆盖k次以上的区域总面积。

因为k≤10，可以在线段树上维护覆盖次数为0,...,k, ≥k的长度数量。

然后就是一个离散化以后扫描线的问题了。

离散化用的是半开半闭区间，以方便表示没有被覆盖的区间。

/*********************************************************
*      --------------Alfheim--------------               *
*   author AbyssalFish                                   *
**********************************************************/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 3e4+5;
const int maxnc = maxn*2;
const int maxk = 10;
int x[maxnc], y[maxnc];
int xs[maxnc], mpx[maxnc];
int rx[maxnc], ry[maxnc];


int n, nxs, lim_k;

#define para int o = 1, int l = 1, int r = nxs
#define lo (o<<1)
#define ro (o<<1|1)
#define Tvar int md = (l+r)>>1;
#define lsn lo,l,md
#define rsn ro,md,r
#define insd ql<=l&&r<=qr

const int ST_SIZE = 1<<17;

int sum[ST_SIZE][maxk+1];
int cnt[ST_SIZE];
#define int_byte 4

void build(para)
{
    cnt[o] = 0;
    memset(sum[o]+1,0,int_byte*lim_k);
    sum[o][0] = mpx[r]-mpx[l];
    if(r-l>1){
        Tvar
        build(lsn);
        build(rsn);
    }
}

inline void maintain(para)
{
    if(cnt[o] >= lim_k) {
        memset(sum[o],0,int_byte*lim_k);
        sum[o][lim_k] = mpx[r]-mpx[l];
    }
    else if(r - l == 1) {
        int k = cnt[o];
        sum[o][k] = mpx[r]-mpx[l];
        if(k > 0) sum[o][k-1] = 0;
        if(k < lim_k) sum[o][k+1] = 0;
    }
    else {
        int lc = lo, rc = ro, c = cnt[o], k;
        for(k = 0; k < c; k++) sum[o][k] = 0;
        for(k = c; k <= lim_k; k++){
            sum[o][k] = sum[lc][k-c] + sum[rc][k-c];
        }
        for(k = lim_k - c+1; k <= lim_k; k++){
            sum[o][lim_k] += sum[lc][k] + sum[rc][k];
        }
    }

}

#define upara ql,  qr,  d
void update(int ql, int qr, int d, para)
{
    if(insd){
        cnt[o] += d;
    }
    else {
        Tvar
        if(ql < md) update(upara,lsn);
        if(qr > md) update(upara,rsn);
    }
    maintain(o,l,r);
}


int *c_cmp;
bool cmp_id(int i,int j){ return c_cmp[i] < c_cmp[j]; }
bool cmp_y(int i,int j){ return y[i] < y[j] || (y[i] == y[j] && (i&1)>(j&1) ); } //出点下标i, i % 2 = 1

int compress(int n, int *a, int *r, int *b, int *mp)
{
    for(int i = 0; i < n; i++){
        r[i] = i;
    }
    c_cmp = a;
    sort(r,r+n,cmp_id);
    int k = 1;
    mp[b[r[0]] = 1] = a[r[0]];
    for(int i = 1; i < n; i++){
        int j = r[i];
        if(a[j] != a[r[i-1]]){
            mp[ b[j] = ++k ] = a[j];
        }
        else {
            b[j] = k;
        }
    }
    return k;
}

ll solve()
{
    scanf("%d%d",&n,&lim_k);
    int nn = n*2;
    for(int i = 0; i < nn; i++){
        scanf("%d%d",x+i,y+i);
        ry[i] = i;
    }
    for(int i = 1; i < nn; i += 2){ //[)
        x[i]++; y[i]++;
    }
    nxs = compress(2*n,x,rx,xs,mpx);
    build();
    sort(ry,ry+nn,cmp_y);
    ll res = 0;
    for(int i = 0; i < nn; i++){
        int p = ry[i], q = p^1;
        if(i) res += (ll)sum[1][lim_k]*(y[p]-y[ry[i-1]]);
        if(y[p] < y[q]){
            //assert((q&1) == 1);
            update(xs[p],xs[q],1);
        }
        else {
            update(xs[q],xs[p],-1);
        }

    }
    return res;
}

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    //cout<<log2(maxnc);
    int T, ks = 0; scanf("%d",&T);
    while(++ks <= T){
        printf("Case %d: %lld
",ks,solve());
    }
    return 0;
}