学步园

题意：给一堆“回"字形，问最后覆盖住的面积是多少。

题解：开始想了巧妙的加边方法，缩小了数据量，搞了模板之后一直wa，和队友苦逼了半天发现问题后改好后tle，又苦逼了半天，看网上的代码没有lazy下放

         的过程，因为加边的时候会保证lazy是成对出现的，这样就不用lazy下放了。  如果线段树的区间修改是成对出现的话就不用将lazy下方了嘻嘻。

Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 210002;
struct line
{
    int x,down,up;
    int left;
    bool operator < (const line &other) const
    {
        return x < other.x;
    }
}vertical_line[maxn << 1];
struct node
{
    int l,r;
    int len,lazy;
}seg[maxn];
int yy[maxn << 1];
bool valid[4];
int n,top,tot;

void addmatrix(int xl,int xr,int yd,int yu,int bj1,int bj2)
{
    if(xl == xr || yd == yu) return;
    valid[bj1] = valid[bj2] = true;
    vertical_line[tot].x = xl;
    vertical_line[tot].down = yd;
    vertical_line[tot].up = yu;
    vertical_line[tot].left = 1;
    tot++;

    vertical_line[tot].x = xr;
    vertical_line[tot].down = yd;
    vertical_line[tot].up = yu;
    vertical_line[tot].left = -1;
    tot++;
    return;
}

void read()
{
    top = tot = 0;
    int x1,x2,x3,x4,y1,y2,y3,y4;
    for(int i=0;i<n;i++)
    {
        valid[0] = valid[1] = valid[2] = valid[3] = false;
        scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        addmatrix(x1,x3,y1,y2,0,1);
        addmatrix(x3,x4,y1,y3,0,2);
        addmatrix(x3,x4,y4,y2,3,1);
        addmatrix(x4,x2,y1,y2,0,1);
        if(valid[0]) yy[top++] = y1;
        if(valid[1]) yy[top++] = y2;
        if(valid[2]) yy[top++] = y3;
        if(valid[3]) yy[top++] = y4;
    }
    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].len = seg[num].lazy = 0;
    if(l + 1 == r) return;
    int mid = (l + r) >> 1;
    biuld(l , mid , num << 1);
    biuld(mid , r , num << 1 | 1);
    return;
}

void UP(int num)
{
    if(seg[num].lazy > 0)
    {
        seg[num].len = yy[seg[num].r] - yy[seg[num].l];
    }
    else if(seg[num].l + 1 == seg[num].r)
    {
        seg[num].len = 0;
    }
    else
    {
        seg[num].len = seg[num << 1].len + seg[num << 1 | 1].len;
    }
    return;
}

void update(int l,int r,int num,int val)
{
    if(l == seg[num].l && r == seg[num].r)
    {
        seg[num].lazy += val;
        UP(num);
        return;
    }
    int mid = (seg[num].l + seg[num].r) >> 1;
    if(mid >= r) update(l , r , num << 1 , val);
    else if(l >= mid) update(l , r , num << 1 | 1 , val);
    else
    {
        update(l , mid , num << 1 , val);
        update(mid , r , num << 1 | 1 , val);
    }
    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;
    if(bjd != bju) update(bjd , bju , 1 , vertical_line[i].left);
    return;
}

void solve()
{
    __int64 sum = 0LL;
    if(tot > 0) addline(0);
    for(int i=1;i<tot;i++)
    {
        sum += 1LL * seg[1].len * (vertical_line[i].x - vertical_line[i-1].x);
        addline(i);
    }
    printf("%I64d\n",sum);
    return;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        read();
        if(tot == 0)
        {
            puts("0");
            continue;
        }
        biuld(0,top-1,1);
        solve();
    }
    return 0;
}