求助，思路如下： 将矩阵边延长，cdq1是求矩阵上下左右不相交的个数，cdq2是减去九宫格四个角算重复的部分

瞪了半个下午仍然卡在WA 38pts

结构体a[i]里的变量命名比较奇怪，a[i].x、a[i].y、a[i].xx、a[i].yy分别表示矩形左、右界横坐标，下、上界纵坐标

#include <bits/stdc++.h>
#define ll long long
#define lb(x) x&(-x)
using namespace std;
const ll N=8e5;
struct node{
	ll x,y,xx,yy,f;
}a[N+5];
ll n;
ll ans[N+5];
ll tr[N+5];
ll num[N+5],numm;
bool cmpf(node l1,node l2){
	return l1.f<l2.f;
}
bool cmpx(node l1,node l2){
	return l1.x<l2.x;
}
bool cmpy(node l1,node l2){
	return l1.y<l2.y;
}
bool cmpxx(node l1,node l2){
	return l1.xx<l2.xx;
}
bool cmpyy(node l1,node l2){
	return l1.yy<l2.yy;
}
void change(ll x,ll y){
	for(ll i=x;i<=numm;i+=lb(i)) tr[i]+=y;
	return;
}
ll searchh(ll x){
	ll s=0;
	for(ll i=x;i;i-=lb(i)) s+=tr[i];
	return s;
}
ll psearch(ll x,ll y){
	if(x>y || y>numm) return 0;
	return searchh(y)-searchh(x-1);
}
ll get(ll x){
	return lower_bound(num+1,num+numm+1,x)-num;
}
void cdq1(ll l,ll r){
	if(l==r) return;
	ll mid=(l+r)>>1;
	cdq1(l,mid),cdq1(mid+1,r);
	//
	sort(a+l,a+mid+1,cmpyy);
	sort(a+mid+1,a+r+1,cmpxx);
	ll p=r+1,s=0;
	for(ll i=mid;i>=l;i--){
		while(p-1>=mid+1 && a[p-1].xx>a[i].yy){
			p--;
			s++;
		}
		ans[a[i].f]+=s;
	}
	//
	sort(a+l,a+mid+1,cmpx);
	sort(a+mid+1,a+r+1,cmpy);
	p=mid,s=0;
	for(ll i=l;i<=mid;i++){
		while(p+1<=r && a[p+1].y<a[i].x){
			p++;
			s++;
		}
		ans[a[i].f]+=s;
	}
	//
	sort(a+l,a+mid+1,cmpxx);
	sort(a+mid+1,a+r+1,cmpyy);
//	cout<<l<<"oooooo"<<r<<endl;
//	for(ll i=l;i<=mid;i++) cout<<a[i].f<<" ";
//	cout<<endl;
//	for(ll i=mid+1;i<=r;i++) cout<<a[i].f<<" ";
//	cout<<endl;
	p=mid,s=0;
	for(ll i=l;i<=mid;i++){
		while(p+1<=r && a[p+1].yy<a[i].xx){
			p++;
			s++;
		}
		ans[a[i].f]+=s;
	}
	//
	sort(a+l,a+mid+1,cmpy);
	sort(a+mid+1,a+r+1,cmpx);
	p=r+1,s=0;
	for(ll i=mid;i>=l;i--){
		while(p-1>=mid+1 && a[p-1].x>a[i].y){
			p--;
			s++;
		}
		ans[a[i].f]+=s;
	}
	return;
}
void cdq2(ll l,ll r){
	if(l==r) return;
	ll mid=(l+r)>>1;
	cdq2(l,mid),cdq2(mid+1,r);
	//
	sort(a+l,a+mid+1,cmpx);
	sort(a+mid+1,a+r+1,cmpy);
	ll p=mid;
	for(ll i=l;i<=mid;i++){
		while(p+1<=r && a[p+1].y<=a[i].x){
			p++;
			change(get(a[p].xx),1);
		}
		ans[a[i].f]-=psearch(get(a[i].yy)+1,numm);
	}
	for(ll i=mid+1;i<=p;i++) change(get(a[i].xx),-1);
	//
	sort(a+l,a+mid+1,cmpx);
	sort(a+mid+1,a+r+1,cmpy);
	p=mid;
	for(ll i=l;i<=mid;i++){
		while(p+1<=r && a[p+1].y<=a[i].x){
			p++;
			change(get(a[p].yy),1);
		}
		ans[a[i].f]-=psearch(1,get(a[i].xx)-1);
	}
	for(ll i=mid+1;i<=p;i++) change(get(a[i].yy),-1);
	//
	sort(a+l,a+mid+1,cmpy);
	sort(a+mid+1,a+r+1,cmpx);
	p=r+1;
	for(ll i=mid;i>=l;i--){
		while(p-1>=mid+1 && a[p-1].x>a[i].y){
			p--;
			change(get(a[p].xx),1);
		}
		ans[a[i].f]-=psearch(get(a[i].yy)+1,numm);
	}
	for(ll i=r;i>=p;i--) change(get(a[i].xx),-1);
	//
	sort(a+l,a+mid+1,cmpy);
	sort(a+mid+1,a+r+1,cmpx);
	p=r+1;
	for(ll i=mid;i>=l;i--){
		while(p-1>=mid+1 && a[p-1].x>a[i].y){
			p--;
			change(get(a[p].yy),1);
		}
		ans[a[i].f]-=psearch(1,get(a[i].xx)-1);
	}
	for(ll i=r;i>=p;i--) change(get(a[i].yy),-1);
	//
	return;
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		ll x,y,aa,b;
		scanf("%lld%lld%lld%lld",&x,&y,&aa,&b);
		a[i]=(node){x+1,x+aa,y+1,y+b,i};
		num[++numm]=x+1;
		num[++numm]=x+aa;
		num[++numm]=y+1;
		num[++numm]=y+b;
	}
	sort(num+1,num+numm+1);
	numm=unique(num+1,num+numm+1)-num-1;
	cdq1(1,n);
	sort(a+1,a+n+1,cmpf);
	cdq2(1,n);
	for(ll i=1;i<=n;i++){
		printf(n-i==ans[i]?"DA\n":"NE\n");
	}
	return 0;
}