学步园

题意：有n（1<=n<=60000）个矩形散落在大矩形中，保证任意两个矩形没有一个交点，问每块被围出来的小面积的大小是多少。

题解：矩形并=线段树，对于这个题，由于任意两个矩形没有一个交点，着眼于lazy的性质，如果一个矩形能被另一个矩形包围起来，那么当前矩形的lazy一定

         比另一个lazy小，遇到矩形的右边的时候再把lazy还原成father，这样搞出来一棵树，然后dfs即可。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
using namespace std;
const int inf = 1 << 29;
const int maxn = 60010;
struct line
{
    int x,down,up,id;
    bool operator < (const line &other) const
    {
        return x < other.x;
    }
}vertical_line[maxn << 1];
struct node
{
    int l,r;
    int lazy;
}seg[maxn << 3];
struct nnode
{
    int v;
    int next;
}edge[maxn << 1];
int yy[maxn << 1],head[maxn],father[maxn];
__int64 area[maxn];
int w,h,n,tot,top,idx;

void swap(int &a,int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
    return;
}

void addedge(int u,int v)
{
    edge[idx].v = v;
    edge[idx].next = head[u];
    head[u] = idx++;
    return;
}

void addmatrix(int x1,int x2,int y1,int y2,int ii)
{
    vertical_line[tot].x = x1;
    vertical_line[tot].down = y1;
    vertical_line[tot].up = y2;
    vertical_line[tot].id = ii;
    tot++;

    vertical_line[tot].x = x2;
    vertical_line[tot].down = y1;
    vertical_line[tot].up = y2;
    vertical_line[tot].id = -ii;
    tot++;

    yy[top++] = y1;
    yy[top++] = y2;
    area[ii] = 1LL * (x2 - x1) * (y2 - y1);
    return;
}

void init()
{
    memset(father,-1,sizeof(father));
    memset(head,-1,sizeof(head));
    tot = top = idx = 0;
    father[1] = inf;
    return;
}

void read()
{
    scanf("%d %d",&w,&h);
    addmatrix(0,w,0,h,1);
    int x1,x2,y1,y2;
    for(int i=2;i<=n+1;i++)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        if(x1 > x2) swap(x1 , x2);
        if(y1 > y2) swap(y1 , y2);
        addmatrix(x1 , x2 , y1 , y2 , i);
    }
    sort(vertical_line , vertical_line + tot);
    sort(yy , yy + top);
    top = unique(yy , yy + top) - yy;
    return;
}

void biuld(int l,int r,int num)
{
    seg[num].l = l;
    seg[num].r = r;
    seg[num].lazy = inf;
    if(l + 1 == r) return;
    int mid = (l + r) >> 1;
    biuld(l , mid , num << 1);
    biuld(mid , r , num << 1 | 1);
    return;
}

void DOWN(int num)
{
    if(seg[num].lazy != inf)
    {
        seg[num << 1].lazy = seg[num << 1 | 1].lazy = seg[num].lazy;
        seg[num].lazy = inf;
    }
    return;
}

void UP(int num)
{
    if(seg[num << 1].lazy == seg[num << 1 | 1].lazy)
    {
        seg[num].lazy = seg[num << 1].lazy;
        seg[num << 1].lazy = seg[num << 1 | 1].lazy = inf;
    }
    return;
}

void update(int l,int r,int num,int id)
{
    if(seg[num].l == l && seg[num].r == r)
    {
        if(id < 0) seg[num].lazy = father[ABS(id)];
        else
        {
            father[id] = seg[num].lazy;
            seg[num].lazy = id;
        }
        return;
    }
    DOWN(num);
    int mid = (seg[num].l + seg[num].r) >> 1;
    if(mid >= r) update(l , r , num << 1 , id);
    else if(l >= mid) update(l , r , num << 1 | 1 , id);
    else
    {
        update(l , mid , num << 1 , id);
        update(mid , r , num << 1 | 1 , id);
    }
    UP(num);
    return;
}

void addline(int i)
{
    int bjd = lower_bound(yy , yy + top , vertical_line[i].down) - yy;
    int bju = lower_bound(yy , yy + top , vertical_line[i].up) - yy;
    update(bjd , bju , 1 , vertical_line[i].id);
    return;
}

void dfs(int st)
{
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        area[st] -= area[edge[i].v];
        dfs(edge[i].v);
    }
    return;
}

void solve()
{
    biuld(0 , top - 1 , 1);
    for(int i=0;i<tot;i++) addline(i);
    for(int i=2;i<=n+1;i++) addedge(father[i] , i);
    dfs(1);
    sort(area + 1 , area + n + 2);
    for(int i=1;i<=n+1;i++)
    {
        if(i > 1) printf(" ");
        printf("%I64d",area[i]);
    }
    puts("");
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        read();
        solve();
    }
    return 0;
}