这可能是道COCI题
题目大意：
在二维平面坐标系，依次给出N个矩形。第i个矩形是“差的”，当且仅当：存在一个$j$，满足$i < j le n$，且矩形i和矩形j有重叠面积。
$1 le N le100000$,坐标范围$[0,10^9]$
（时限$5s$，空限$512MB$）
其实一开始就想到是扫描线的，然后不知道如何维护一些奇奇怪怪的东西。直到考完后经人提醒才想起可以用个set来维护，STL是个好东西。
进入正题：
- 前置知识：扫描线 (不会的可出门左转度娘
由题意，我们自然联想到维护每个线段树每个节点所代表的区间中，可以完全覆盖这个区间的矩形里，矩形编号的最大值与不是坏矩形的编号（好像就是最小值。
显然，我们要支持撤销操作，由此我们想不到可以用set来维护上述东西。
至于维护答案，我们可以在对线段树进行操作时，同步进行。只要把当前节点我们记录的“不是坏矩形的编号”与当前操作所属的矩形的编号作比较就行了。
这样就可以了吗？
显然不是。
容易发现，上述维护方式是错的。至于反例，可以简单得出，这里就不讲了。
事实上，我们还要多维护一个东西，就是非完全覆盖这个区间的矩形的编号。我们有三类更新答案的操作：
A.这个矩形把当前节点所表示区间全覆盖了，会对完全覆盖这个区间和非完全覆盖这个区间的矩形都会造成影响。
（对于完全覆盖这个区间的，我们只需用上前面维护那俩东西,对于非完全覆盖的，我们可以扫描一下set）
B.这个矩形把没有当前节点所表示区间完全覆盖，至少会对完全覆盖这个区间的矩形造成影响。
至此，完结撒花~
附代码：
#include<bits/stdc++.h> using namespace std; int x,y,h,w,n,p,tree[4000000],trees[4000000]; bool bad[1000002]; int yy[2000002],n_y,ny[2000002],nny; set<int> treen[4000000]; set<int> treem[4000000]; struct data { int x,yy1,yy2,num,pp; }line[2000002]; void lisanhua() { sort(yy+1,yy+1+n_y); for (int i=1;i<=n_y;i++) if (yy[i]!=yy[i-1]) ny[++nny]=yy[i]; } bool cmp(data x,data y) { return (x.x<y.x)||(x.x==y.x&&x.pp<y.pp); } void maketree(int x,int l,int r) { if (l==r) { tree[x]=0;trees[x]=0; return ; } int mid=(l+r)/2; maketree(x*2,l,mid);maketree(x*2+1,mid+1,r); tree[x]=0;trees[x]=0; } void add(int x,int l,int r,int ql,int qr,int k,int num) { if (trees[x]) { if (num>trees[x]) {bad[trees[x]]=1,trees[x]=0;} else if (num<trees[x]) {bad[num]=1;} } if (l>=ql&&r<=qr) { if (k==1) treen[x].insert(num); if (k==-1) { if (trees[x]==num) trees[x]=0; treen[x].erase(num); } set<int>::iterator it; it=treem[x].begin(); if (treem[x].begin()!=treem[x].end()) while (1) { if (num>*it) {bad[*it]=1;} else if (num<*it) {bad[num]=1;} if (it==(--treem[x].end())) break; it++; } if (!(treen[x].empty())) tree[x]=*(--treen[x].end()); if (!bad[num]&&k==1) trees[x]=num; return ; } else { if (k==1) treem[x].insert(num); if (k==-1) {treem[x].erase(num);} set<int>::iterator it; it=treen[x].begin(); if (treen[x].begin()!=treen[x].end()) while (1) { if (num>*it) {bad[*it]=1;} else if (num<*it) {bad[num]=1;} if (it==(--treen[x].end())) break; it++; } } int mid=(l+r)/2; if (ql>mid) add(x*2+1,mid+1,r,ql,qr,k,num); else if (qr<=mid) add(x*2,l,mid,ql,qr,k,num); else { add(x*2,l,mid,ql,mid,k,num); add(x*2+1,mid+1,r,mid+1,qr,k,num); } } int main() { freopen("2737.in","r",stdin); freopen("2737.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) { cin>>x>>y>>w>>h; int xx1=x+w,yy1=y+h; line[++p].x=x;line[p].yy1=y;line[p].yy2=yy1;line[p].num=i;line[p].pp=1; line[++p].x=xx1;line[p].yy1=y;line[p].yy2=yy1;line[p].num=i;line[p].pp=-1; yy[++n_y]=y;yy[++n_y]=yy1; } yy[0]=-1; lisanhua(); sort(line+1,line+1+p,cmp); maketree(1,1,nny); for (int i=1;i<=p;i++) { int np1=lower_bound(ny+1,ny+nny+1,line[i].yy1)-ny,np2=lower_bound(ny+1,ny+nny+1,line[i].yy2)-ny; add(1,1,nny,np1,np2-1,line[i].pp,line[i].num); } for (int i=1;i<=n;i++) { if (bad[i]) cout<<"NE ";else cout<<"DA "; } return 0; }