扫描线是线段树标记永久化的一种应用

最开始我学习的都是计算矩形面积并的程序
每次在加入一条边的时候，只用在logn个节点上打上标记即可，不用下传标记
这样在对应删除的时候，就可以再次找到这些标记，删除即可

但是这道题的大矩形中出现了小的矩形空隙

first.

一开始我简单的认为，只要把矩形空隙的前一条边ff设为-1
后一条边设为1，就可以直接做了

但是这样得出的答案只会是大矩形的面积并
并没有把小矩形空隙的面积并减掉

因为小矩形的边是无法直接对应到标记上的
所以在一次修改，单链向上update的过程中，t[1]是无法维护的
（一旦在从叶子到根update的过程中
有一个节点的s>0，那就无法影响再往上的区间了）

second

于是我就想用大矩形的面积并-删除的小矩形的面积并
但是出现了这种反例（这种反例还是很普遍的）
这里写图片描述

third

唯一的解决办法就是把一个矩形扣掉一小部分这种图形分成四个小矩形计算
这里写图片描述

tip

一定要注意我们对矩形的定义是左下角和右上角

我的程序在hdu上一直RE。。。

y1在c++中是关键字

这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010;
int n,tot,tt;
struct node{
    int l,r,ml,mr,s,len;
};
node t[N*40];
struct nd{
    int x,ya,yb,ff;
};
nd li[N*8];
int yi[N*8];

int cmp(const nd &a,const nd &b)
{
    return a.x<b.x;
}

void build(int bh,int l,int r)
{
    t[bh].l=l;t[bh].r=r;
    t[bh].ml=yi[l]; t[bh].mr=yi[r];
    t[bh].s=t[bh].len=0;
    if (r-l==1) return;
    int mid=(l+r)>>1;
    build(bh<<1,l,mid);
    build(bh<<1|1,mid,r);
}

void update(int bh)
{
    if (t[bh].s>0) t[bh].len=t[bh].mr-t[bh].ml;
    else if (t[bh].r-t[bh].l==1) t[bh].len=0;  //
    else t[bh].len=t[bh<<1].len+t[bh<<1|1].len;
}

void add(int bh,nd b)
{
    if (t[bh].ml==b.ya&&t[bh].mr==b.yb)
    {
        t[bh].s+=b.ff;
        update(bh);
        return;
    }
    if (b.yb<=t[bh<<1].mr) add(bh<<1,b);   
    else if (b.ya>=t[bh<<1|1].ml) add(bh<<1|1,b);
    else
    {
        nd tmp=b;
        tmp.yb=t[bh<<1].mr;
        add(bh<<1,tmp);
        tmp=b;
        tmp.ya=t[bh<<1|1].ml;
        add(bh<<1|1,tmp);
    }
    update(bh);
}

int main()
{
    scanf("%d",&n);
    while (n)
    {
        tot=0; tt=0;
        int x,y,xx,yy,x3,x4,y3,y4;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d%d%d",&x,&y,&xx,&yy,&x3,&y3,&x4,&y4);
            tot++; yi[tot]=y;
            li[tot].x=x; li[tot].ya=y; li[tot].yb=yy; li[tot].ff=1;
            tot++; yi[tot]=yy;
            li[tot].x=x3; li[tot].ya=y; li[tot].yb=yy; li[tot].ff=-1;

            tot++; yi[tot]=y;
            li[tot].x=x4; li[tot].ya=y; li[tot].yb=yy; li[tot].ff=1;
            tot++; yi[tot]=yy;
            li[tot].x=xx; li[tot].ya=y; li[tot].yb=yy; li[tot].ff=-1;

            tot++; yi[tot]=y4;
            li[tot].x=x3; li[tot].ya=y4; li[tot].yb=yy; li[tot].ff=1;
            tot++; yi[tot]=yy;
            li[tot].x=x4; li[tot].ya=y4; li[tot].yb=yy; li[tot].ff=-1;

            tot++; yi[tot]=y;
            li[tot].x=x3; li[tot].ya=y; li[tot].yb=y3; li[tot].ff=1;
            tot++; yi[tot]=y3;
            li[tot].x=x4; li[tot].ya=y; li[tot].yb=y3; li[tot].ff=-1;
        } 
        sort(yi+1,yi+1+tot);
        sort(li+1,li+1+tot,cmp);
        build(1,1,tot);
        add(1,li[1]);
        int sum=0;
        for (int i=2;i<=tot;i++)
        {
            sum+=(t[1].len*(li[i].x-li[i-1].x));
            add(1,li[i]);
        }
        printf("%dn",sum);
        scanf("%d",&n);
    }
    return 0;
}