题意：
在一个平面上，依次放入N个颜色不同的矩形（可能会覆盖），现在求最终状态下能看到多少种不同温度颜色。注：空白部分也视为一种颜色。
N≤100000N≤100000
分析：
这是一道比较有趣的数据结构题：
利用扫描线算法，首先将所有坐标离散化，然后按照正方向枚举x坐标，每次求出当前这个横坐标能看见的矩形，于是将每个矩形视作两条线段：
矩形的左侧视为加入当前矩形，右侧+1的位置视为删去当前矩形。
用线段树+set维护。
对于每个线段树上的节点，存储两个值与一个set，分别设为maxv,minv,S
maxv表示：当前区间内能够看见的，编号最大的未被标记的颜色。
minv表示：当前区间内被覆盖的最小的颜色。（用于更新maxv）
S存储覆盖了当前区间的所有颜色。
对于每次更新，首先求出左右儿子节点的maxv，minv，令当前节点的maxv=max{
maxvin left son,maxvin right son,maxvalin S and did′t used}maxv=max{maxvinleftson,maxvinrightson,maxvalinSanddid′tused}，
minv=max{
min{
minvin left son,minvin right son},maxvalin S and did′t used}minv=max{min{minvinleftson,minvinrightson},maxvalinSanddid′tused}，理解起来很容易，里层的min就是左右区间内的被覆盖颜色的最小值，而外层的max是因为：当前区间内都被这个值覆盖，所以取max。
然后，若maxv<minvmaxv<minv，说明当前maxv这个颜色一定被其他已更新颜色覆盖掉了，因为它连当前区间内最小的值都不够。所以将maxvmaxv修正为-1，即记为当前区间不含可以被更新的颜色。
每更新一次，继续判断根节点的maxv是否为-1，若不是则继续标记，若是则停止。
实现上有些细节要考虑：首先离散化后，必须区分“离散化后相邻”和“离散化前相邻”的情况（实现时就会发现了）。
并且，由于题目给出的是端点坐标，因此我们的矩形范围要作出相应改动，比如，两个点（0,1）与（0,2）之间，如果直接将这个作为矩形的边界位置（即将左端点设为1，右端点设为2），那么矩形就会有2的单位长度，但其实这个矩形只有1单位长度。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
struct node{set<int> s;int mi,ma; node *pl,*pr;
}tree[MAXN*12],*root=tree,*ncnt=tree;
bool used[MAXN];
struct block{int l,r,id,flag,x;block() {}block(int l1,int r1,int id1,int flag1,int x1):l(l1),r(r1),id(id1),flag(flag1),x(x1) {}bool operator < (const block&a) const{if(x==a.x)return l<a.l;return x<a.x;}
}blo[MAXN*2];
void build(node *x,int l,int r){x->mi=-1,x->ma=-1;if(l==r) return ;int mid=(l+r)>>1;x->pl=++ncnt;build(x->pl,l,mid);x->pr=++ncnt;build(x->pr,mid+1,r);
}
void pushup(node *x){if(x->pl==NULL&&x->pr==NULL){if(x->s.empty()){x->ma=x->mi=-1;return; }x->ma=*x->s.rbegin();x->mi=x->ma;if(used[x->ma]==1)x->ma=-1;}else{int &mi=x->mi,&ma=x->ma;mi=min(x->pl->mi,x->pr->mi),x->ma=max(x->pl->ma,x->pr->ma);if(x->s.empty())return ;int xs=*x->s.rbegin();mi=max(mi,xs);if(ma<xs){if(used[xs]==1)ma=-1;else{if(xs<mi)ma=-1;elsema=xs;}}}
}
void add(node *x,int l,int r,int l1,int r1,int val,int idx){if(l>=l1&&r<=r1){if(val==-1)x->s.erase(idx);elsex->s.insert(idx);pushup(x);return ;}int mid=(l+r)>>1;if(mid>=l1)add(x->pl,l,mid,l1,r1,val,idx);if(mid<r1)add(x->pr,mid+1,r,l1,r1,val,idx);pushup(x);
}
void Update(node *x,int l,int r,int l1,int r1,int idx){if(l>=l1&&r<=r1){pushup(x); return ;}int mid=(l+r)>>1;if(mid>=l1)Update(x->pl,l,mid,l1,r1,idx);if(mid<r1)Update(x->pr,mid+1,r,l1,r1,idx);pushup(x);
}
int n,sumx,sumy;
int apx[MAXN*6],apy[MAXN*6];
int ls[MAXN],rs[MAXN];
void pushx(int x){apx[++sumx]=x;apx[++sumx]=x-1;apx[++sumx]=x+1;
}
void pushy(int y){apy[++sumy]=y;apy[++sumy]=y-1;apy[++sumy]=y+1;
}
int main(){SF("%d",&n); int sx,sy,ex,ey,cnt=0;for(int i=1;i<=n;i++){SF("%d%d%d%d",&sx,&sy,&ex,&ey);ex--,ey--;blo[++cnt]=block(sy,ey,i,1,sx);blo[++cnt]=block(sy,ey,i,-1,ex+1);pushx(sx);pushx(ex+1);pushy(sy);pushy(ey);}sort(apx+1,apx+1+sumx);sort(apy+1,apy+1+sumy);sumx=unique(apx+1,apx+1+sumx)-(apx+1);sumy=unique(apy+1,apy+1+sumy)-(apy+1);for(int i=1;i<=cnt;i++){blo[i].l=lower_bound(apy+1,apy+1+sumy,blo[i].l)-apy;blo[i].r=lower_bound(apy+1,apy+1+sumy,blo[i].r)-apy;blo[i].x=lower_bound(apx+1,apx+1+sumx,blo[i].x)-apx;}for(int i=1;i<=cnt;i++){ls[blo[i].id]=blo[i].l;rs[blo[i].id]=blo[i].r;}sort(blo+1,blo+1+cnt);int las=1;build(root,1,sumy);/*for(int i=1;i<=cnt;i++)PF("{%d %d %d %d %d}\n",blo[i].l,blo[i].r,blo[i].x,blo[i].id,blo[i].flag);*/for(int i=1;i<=sumx;i++){while(las<=cnt&&blo[las].x==i){//PF("{
%d %d %d %d}\n",blo[las].l,blo[las].r,blo[las].x,blo[las].id);add(root,1,sumy,blo[las].l,blo[las].r,blo[las].flag,blo[las].id);las++;}while(root->ma!=-1){int x=root->ma;used[x]=1;Update(root,1,sumy,ls[x],rs[x],x);}}int ans=1;for(int i=1;i<=n;i++)if(used[i]==1)ans++;PF("%d",ans);
}