poj 1171 Picture 线段树

     经典的线段树问题，看了好久才看懂

     解法很简单，按y坐标从小到大，依次扫描每条线段，每次利用线段树记录当前图形在x轴上的投影，然后用这次投影减去上次就是x轴上变化量，而y轴，因为按y轴枚举，只需要用y的差值乘以2再乘以当前线段数即可。

     而线段树的处理就是遇到下边是加入线段树，遇到上边删去及记录当前投影长度，及投影分段情况

     看到网上还有种括号匹配的方法，离散化后枚举，复杂度n^2

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 5005
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
struct Node
{
    int num,len,lnum,lazy; //num为此线段覆盖次数，len为覆盖长度，lnum为段数，lazy为延迟数
    bool lc,rc; //表示线段两端有无被覆盖
};
struct Line
{
    int l,r,y;
    bool up;
};
Line line[maxn<<1];
Node node[maxn<<2];
int num,x[maxn<<1];
void pushup(int rt)//向上更新
{
    node[rt].len=node[rt<<1].len+node[rt<<1|1].len;
    node[rt].lnum=node[rt<<1].lnum+node[rt<<1|1].lnum;
    node[rt].lc=node[rt<<1].lc;
    node[rt].rc=node[rt<<1|1].rc;
    node[rt].num=max(node[rt<<1].num,node[rt<<1|1].num);
    if(node[rt<<1].rc&&node[rt<<1|1].lc) node[rt].lnum--;//如果左孩子的右节点和右孩子的左节点都被标记，则线段数减1
    return;
}
void pushdown(int rt,int l,int r)//向上更新
{
    if(node[rt].lazy)
    {
        int m=l+r>>1;
        node[rt<<1].len=x[m-1]-x[l-1];
        node[rt<<1|1].len=x[r-1]-x[m-1];
        node[rt<<1].num+=node[rt].lazy;
        node[rt<<1|1].num+=node[rt].lazy;
        node[rt<<1].lazy+=node[rt].lazy;
        node[rt<<1|1].lazy+=node[rt].lazy;
        if(node[rt<<1].num>0) node[rt<<1].lnum=node[rt<<1].lc=node[rt<<1].rc=1;
        else node[rt<<1].num=node[rt<<1].len=node[rt<<1].lnum=node[rt<<1].lc=node[rt<<1].rc=0; //如果覆盖数为0，则删除
        if(node[rt<<1|1].num>0) node[rt<<1|1].lnum=node[rt<<1|1].lc=node[rt<<1|1].rc=1;
        else node[rt<<1|1].num=node[rt<<1|1].len=node[rt<<1|1].lnum=node[rt<<1|1].lc=node[rt<<1|1].rc=0;
    }
    node[rt].lazy=0;
}
void add(int L,int R,int l,int r,int rt)//增加线段
{
    if(L<=l&&R>=r)
    {
        node[rt].len=x[r-1]-x[l-1];
        node[rt].num++;
        node[rt].lc=node[rt].rc=node[rt].lnum=1;
        node[rt].lazy++;//延迟更新
        return;
    }
    pushdown(rt,l,r);
    int m=(l+r)>>1;
    if(L<m)add(L,R,lson);
    if(R>m)add(L,R,rson);
    pushup(rt);
    return;
}
void del(int L,int R,int l,int r,int rt)//删除线段
{
    if(L<=l&&R>=r)
    {
        node[rt].num--;
        if(node[rt].num<=0)
        {
            node[rt].len=0;
            node[rt].lc=node[rt].rc=node[rt].lnum=0;
            node[rt].num=0;
            node[rt].lazy--;//如果此线段被删除，延迟更新子线段
            return;
        }
        if(r-l==1)return;
    }
    pushdown(rt,l,r);
    int m=(l+r)>>1;
    if(L<m)del(L,R,lson);
    if(R>m)del(L,R,rson);
    pushup(rt);
    return;
}
bool cmp(Line a,Line b)
{
    if(a.y==b.y) return a.l<b.l;
    else return a.y<b.y;
}
inline int find(int key)//查询x坐标对应的下标，因为线段树要求从1开始，所以下标加1
{
    return lower_bound(x,x+num,key)-x+1;
}
int main()
{
    int n,i,x1,x2,y1,y2;
    while(~scanf("%d",&n))
    {
        memset(node,0,sizeof(node));
    num=0;
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x[num++]=x1;x[num++]=x2;
        line[i<<1].l=x1;line[i<<1].r=x2;line[i<<1].y=y1;line[i<<1].up=1;
        line[i<<1|1].l=x1;line[i<<1|1].r=x2;line[i<<1|1].y=y2;line[i<<1|1].up=0;
    }
    sort(x,x+num);//对x排序，离散化处理
    num=unique(x,x+num)-x;//去重
    n=n<<1;
    sort(line,line+n,cmp);
    int pre=0,ans=0;
    for(i=0;i<n-1;i++)
    {
        if(line[i].up)//如果是下边，则加边
            add(find(line[i].l),find(line[i].r),1,num,1);
        else //如果是上边，则删除
            del(find(line[i].l),find(line[i].r),1,num,1);
        ans+=node[1].lnum*(line[i+1].y-line[i].y)*2;//平行y轴
        ans+=abs(node[1].len-pre);//平行x轴
        pre=node[1].len;
    }
    del(find(line[i].l),find(line[i].r),1,num,1);
    ans+=abs(node[1].len-pre);
    printf("%d\n",ans);
    }
}