题意：

求矩形面积的并  每一个矩形里面有个小的矩形被挖空

思路：

经典的线段树扫描线  我居然坑了3个小时没写出来…真是歧视自己！

！

学过扫描线的都会有思路  这里提出一个错误想法…（就是我的…）

你要是这样给线赋权值就大错特错了  由于会发现线段树的结构使得操作变得非常麻烦

当你想更新某段区间的时候  并不知道准确的down到哪里  也不知道更新完了up要怎样合并区间

当然像我一样一開始都更新到叶子节点是必须TLE的… TAT

正确思路是这种

划分出4个矩形再求  为什么这样就对了呢？  由于不用down

考虑每一个矩形假设+1的边来了那就计数就好了  反正总有一个-1边会来到这里

假设你问第一种方法不也是能够等-1来么  答案是不能够

“能等待”这个性质须要保证如今考虑的这个小矩形内部不会有空产生  而第一种明显会有空

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define LL __int64#define N 200005#define M(x,y) ( (x+y)>>1 )#define L(x) ( x<<1 )#define R(x) ( (x<<1)|1 )int n,tot;struct line{	int x,y1,y2;	int flag;	bool operator<(const line fa) const	{		if(x!=fa.x) return x
        
         fa.flag;	}}l[N*2];struct node{	int l,r,cov,sum;}tree[N*8];LL ans;void init(int l,int r,int i){	tree[i].l=l;	tree[i].r=r;	tree[i].cov=0;	tree[i].sum=0;	if(l+1==r) return ;	int mid=M(l,r);	init(l,mid,L(i));	init(mid,r,R(i));}void up(int i){    if(tree[i].cov>0) tree[i].sum=tree[i].r-tree[i].l;    else    {        if(tree[i].l+1==tree[i].r) tree[i].sum=0;        else tree[i].sum=tree[L(i)].sum+tree[R(i)].sum;    }}void updata(int y1,int y2,int i,int flag){    if(tree[i].l==y1&&tree[i].r==y2)    {        tree[i].cov+=flag;        up(i);        return ;    }    int mid=M(tree[i].l,tree[i].r);	if(y2<=mid) updata(y1,y2,L(i),flag);    else if(y1>=mid) updata(y1,y2,R(i),flag);    else    {        updata(y1,mid,L(i),flag);        updata(mid,y2,R(i),flag);    }    up(i);}int main(){	int i;	int tx1,ty1,tx2,ty2,tx3,ty3,tx4,ty4;	while(~scanf("%d",&n))	{		if(!n) break;		tot=0;		for(i=0;i