学步园

线段树扫描线。

题意： 在一个n*m平面内，有一些不重叠的矩形(可能退化成点或线)，现在让你把一根给定长度的线竖直或水平地放进平面，要求不与任何原来存在的矩形重合，问有多少种放法。

解法： 在一根长度为a的线段上放置一根长度为b的线段共有a-b+1种放法。那么将给定的矩形拆成两根线段，用扫描线横着扫一次，竖着扫一次，就可以得到答案。有区间合并的过程。范围较大需要离散化。

本人在拆矩形时因为拆的是闭区间，一个矩形8条线，再因为线段树的4倍空间需求和维护变量的4倍空间需求，总共有5W个矩形，在ZOJ上内存堪堪卡过去。

注意一下计算时的讨论，还有长度为1的情况，见代码，不赘述。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))
typedef long long lld;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ls (rt<<1)
#define rs (rt<<1|1)

const int MAXN = 400010;
int w,h,n,len;
int san[MAXN],st;
struct point {
    int x[2],y[2];
}sp[MAXN];
struct Seg {
    int l,r,h,s;
    Seg(){}
    Seg(int l, int r, int h, int s) : 
        l(l), r(r), h(h), s(s) {}
    bool operator < (const Seg &tt) const {
        if(h == tt.h) return s > tt.s;
        return h < tt.h;
    }
}ss[MAXN<<2];
int tot;
lld ans;
int lpa[MAXN<<2],rpa[MAXN<<2],sum[MAXN<<2],cnt[MAXN<<2];

int Count(int x) {
    return x < len ? 0 : x-len+1;
}

void up(int l, int r, int rt) {
    int m = l+r>>1;
    sum[rt] = sum[ls] + sum[rs];
    lpa[rt] = lpa[ls];
    if(lpa[rt] == m-l+1) lpa[rt] += lpa[rs];
    rpa[rt] = rpa[rs];
    if(rpa[rt] == r-m) rpa[rt] += rpa[ls];

    sum[rt] -= Count(san[m]-san[m-rpa[ls]+1]+1);
    sum[rt] -= Count(san[m+lpa[rs]]-san[m+1]+1);
    sum[rt] += Count(san[m+lpa[rs]]-san[m-rpa[ls]+1]+1);
}

void build(int l, int r, int rt) {
    sum[rt] = Count(san[r]-san[l]+1);
    lpa[rt] = rpa[rt] = r-l+1;
    cnt[rt] = 0;
    if(l == r) return ;
    int m = l+r>>1;
    build(lson);
    build(rson);
}

void update(int L, int R, int x, int l, int r, int rt) {
    if(L<=l && r<=R) {
        cnt[rt] += x;
        if(cnt[rt] == 0) {
            lpa[rt] = rpa[rt] = r - l + 1;
            sum[rt] = Count(san[r]-san[l]+1);
        }
        else {
            rpa[rt] = lpa[rt] = 0;
            sum[rt] = 0;
        }
        return ;
    }
    else {
        int m = l+r>>1;
        if(L<=m) update(L,R,x,lson);
        if(m< R) update(L,R,x,rson);
        up(l,r,rt);
    }
}

void gaox() {
    if(n == 0) {
        ans += (lld)Count(w) * h;
        return ;
    }
    if(w < len) return ;
    tot = 0;
    REP(i,0,n) {
        ss[tot++] = Seg(sp[i].x[0],sp[i].x[1],sp[i].y[0],1);
        ss[tot++] = Seg(sp[i].x[0],sp[i].x[1],sp[i].y[1],-1);
    }
    sort(ss,ss+tot);
    int l = lower_bound(san,san+st,1) - san;
    int r = lower_bound(san,san+st,w) - san;
    build(l,r,1);
    REP(i,0,tot-1) {
        int L = lower_bound(san,san+st,ss[i].l) - san;
        int R = lower_bound(san,san+st,ss[i].r) - san;
        if(ss[i].s < 0 && (ss[i-1].h != ss[i].h || ss[i-1].s != ss[i].s))
            ans += sum[1];
        update(L,R,ss[i].s,l,r,1);
        if(ss[i].s < 0 && ss[i+1].h != ss[i].h) ans += (lld)sum[1] * (ss[i+1].h - ss[i].h - 1);
        else if(ss[i].s > 0) ans += (lld)sum[1] * (ss[i+1].h - ss[i].h);
    }

    if(ss[tot-1].s != ss[tot-2].s || ss[tot-1].h != ss[tot-2].h) ans += sum[1];
    ans += (lld)Count(w) * (ss[0].h-1 + h-ss[tot-1].h);
}

void gaoy() {
    if(n == 0) {
        ans += (lld)Count(h) * w;
        return ;
    }
    if(h < len) return ;
    tot = 0;
    REP(i,0,n) {
        ss[tot++] = Seg(sp[i].y[0],sp[i].y[1],sp[i].x[0],1);
        ss[tot++] = Seg(sp[i].y[0],sp[i].y[1],sp[i].x[1],-1);
    }
    sort(ss,ss+tot);
    int l = lower_bound(san,san+st,1) - san;
    int r = lower_bound(san,san+st,h) - san;
    build(l,r,1);
    REP(i,0,tot-1) {
        int L = lower_bound(san,san+st,ss[i].l) - san;
        int R = lower_bound(san,san+st,ss[i].r) - san;
        int temp;
        if(ss[i].s < 0 && (ss[i-1].h != ss[i].h || ss[i-1].s != ss[i].s)) ans += sum[1];
        update(L,R,ss[i].s,l,r,1);
        if(ss[i].s < 0 && ss[i+1].h != ss[i].h) ans += (lld)sum[1] * (ss[i+1].h - ss[i].h - 1);
        else if(ss[i].s > 0) ans += (lld)sum[1] * (ss[i+1].h - ss[i].h);
    }
    if(ss[tot-1].s != ss[tot-2].s || ss[tot-1].h != ss[tot-2].h) ans += sum[1];
    ans += (lld)Count(h) * (ss[0].h-1 + w-ss[tot-1].h);
}

int main() {
    while(~scanf("%d%d%d%d", &w, &h, &n, &len)) {
        st = 0;
        ans = 0;
        san[st++] = 1;
        san[st++] = w;
        san[st++] = h;
        REP(i,0,n) {
            REP(j,0,2) {
                scanf("%d%d", &sp[i].x[j],&sp[i].y[j]);
                san[st++] = sp[i].x[j];
                san[st++] = sp[i].y[j];
            }
            san[st++] = sp[i].x[0]-1;
            san[st++] = sp[i].x[1]+1;
            san[st++] = sp[i].y[0]-1;
            san[st++] = sp[i].y[1]+1;
        }
        sort(san,san+st);
        st = unique(san,san+st) - san;
        gaox();
        if(len != 1) gaoy();
        printf("%lld\n", ans);
    }
    return 0;
}

/*

4 4 3 2
3 2 3 2
2 3 2 3
3 3 4 4

ans = 10

*/