题目描述 传送门：http://codeforces.com/contest/983/problem/D
题解 倒过来然后裸上树套树的话似乎会mle。 考虑离线，颜色的编号等于时间戳。 然后对于x轴扫描线，用线段树维护y坐标的情况。 对于一个矩形，如果它在x坐标扫到某个位置并且操作完的时候，某一段能够显示出来，那么这个矩形就可见。 所以我们按照x坐标扫描线，每次先把矩形删除加上，然后取出所有可视矩形计算答案。
接下来我们考虑下线段树要怎么维护。 对于线段树上的每个点维护一个set表示覆盖这个区间的所有矩形的颜色序号。 线段树上每个节点再维护两个值maxn,minn，分别表示该区间可视的颜色虽大编号和最小编号。 对于转移，一个区间上如果最大的那个颜色已经被记录答案那么maxn=0，否则maxn为子树和set里的最大值。 最小直接转移就好了。 每一个x坐标处理完之后我们取线段树根节点的manx并记录答案并进行修改，然后依次这么做下去直到maxn[root]=0。
这样的话时间复杂度是O(nlog2n)。
代码
#include<bits/stdc++.h> #define N 200005 using namespace std; int n,A[N],B[N],C[N],D[N],ans,flag[N]; int n1[N],n2[N],t1,t2,T1,T2; struct info{int maxn,minn;}t[N*4]; vector<int>s[N]; set<int>q[N*4]; class seg_tree { void update(int x,int l,int r) { int lc=x<<1,rc=lc+1; if(l==r)t[x].minn=t[x].maxn=0; else { t[x].minn=min(t[lc].minn,t[rc].minn); t[x].maxn=max(t[lc].maxn,t[rc].maxn); } if(q[x].size()) { if(flag[*q[x].rbegin()]) t[x].minn=max(t[x].minn,*q[x].rbegin()); else t[x].maxn=max(t[x].maxn,*q[x].rbegin()); } if(t[x].maxn<t[x].minn)t[x].maxn=0; } public: void modify(int x,int l,int r,int ql,int qr,int col) { if(ql<=l&&r<=qr) { if(col>0)q[x].insert(col); else q[x].erase(-col); update(x,l,r);return; } int mid=l+r>>1,lc=x<<1,rc=lc+1; if(ql<=mid)modify(lc,l,mid,ql,qr,col); if(qr>mid)modify(rc,mid+1,r,ql,qr,col); update(x,l,r); } }T; int main() { int x,y; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]); n1[++t1]=A[i];n1[++t1]=C[i]; n2[++t2]=B[i];n2[++t2]=D[i]; } sort(n1+1,n1+t1+1);sort(n2+1,n2+t2+1); T1=unique(n1+1,n1+t1+1)-n1-1; T2=unique(n2+1,n2+t2+1)-n2-1; for(int i=1;i<=n;i++) { A[i]=lower_bound(n1+1,n1+T1+1,A[i])-n1; B[i]=lower_bound(n2+1,n2+T2+1,B[i])-n2; C[i]=lower_bound(n1+1,n1+T1+1,C[i])-n1; D[i]=lower_bound(n2+1,n2+T2+1,D[i])-n2-1; s[A[i]].push_back(i); s[C[i]].push_back(-i); } for(int i=1;i<=T1;i++) { for(int j=0;j<s[i].size();j++) { y=s[i][j];x=abs(y); T.modify(1,1,T2,B[x],D[x],y); } while(t[1].maxn) { x=t[1].maxn;flag[x]=1;ans++; T.modify(1,1,T2,B[x],D[x],0); } } printf("%d\n",ans+1); return 0; }