扫描线补充

1.两条扫描线之间，不一定是一个矩形，可能是多个不相交的，高相同的矩形

2.扫描线的板子没有pushdown

void upd(int u,int l,int r){
	if(cnt[u]){
		len[u]=b[r+1]-b[l];
		sum[u]=2;
		lh[u]=rh[u]=1;
	}else{
		len[u]=len[lch]+len[rch];
		sum[u]=sum[lch]+sum[rch];
		lh[u]=lh[lch],rh[u]=rh[rch];
		if(rh[lch]&&lh[rch])	sum[u]-=2;
	}
}
void add(int u,int l,int r,int L,int R,int typ){
	if(l>R||r<L)	return;
	if(l>=L&&r<=R){
        if(typ) cnt[u]++;//在这里能够停止了，u的儿子不会被改变，会感觉有问题
        else    cnt[u]--;
		upd(u,l,r);
		return;
	}
	int mid=l+r>>1;
	add(lch,l,mid,L,R,typ),add(rch,mid+1,r,L,R,typ);
	upd(u,l,r);
}

实际上是因为查找的只有tree[1].len。如果查询的是若干区间，就需要用懒惰标记，并且进行pushdown.

3.特别注意在计算周长时，要考虑边重合（相切）的问题。把边重合转化成相交，而不是相离。

对边排序时预处理可以避免这类问题。

bool cmp(line p,line q){
	return (p.y!=q.y)?p.y<q.y:p.op>q.op;
}