P7312 [COCI2018-2019#2] Sunčanje
题解
分类讨论的思想有点像P4169?
要你对于每一个矩形，求是否存在编号比它大，与它有交的矩形。
直接做需要用一个比较神仙的线段树用法，所以我们可以容斥：我们求出编号比它大，与它无交的矩形数量，最后与所有可能覆盖它的矩形共 \(n-i\) 个作比较。
更具体的，求出在它上下左右的矩形数量减去四个角的矩形数量即可。上下左右的矩形数量是经典二维偏序，四个角的矩形数量是经典三维偏序，直接套板子就好。
一个小技巧：只考虑一边和一个角的贡献，打包成一个函数（即下文的 solve() 函数），每次直接转坐标轴就可以快速求解。
时间复杂度 \(O(n\log^2n)\) ，可以尝试归并，但是我懒。
代码很好写：
#include<bits/stdc++.h>
using namespace std;
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
const int ML=200005;
int n,ans[100005];
struct QWQ {int id,xl,xr,yl,yr;} a[100005],b[100005];
bool cmp1(QWQ a1,QWQ a2) {return a1.id>a2.id;}
bool cmp2(QWQ a1,QWQ a2) {return a1.xr<a2.xr;}
bool cmp3(QWQ a1,QWQ a2) {return a1.xl<a2.xl;}
int bx[200005],by[200005],cntx,cnty,qx,qy;
struct Binary_Indexed_Tree {
int t[ML+5];
inline int lb(int x) {return x&-x;}
inline int sum(int x) {int s=0;for(int i=x;i;i-=lb(i)) s+=t[i];return s;}
inline void add(int x,int k) {for(int i=x;i<=ML;i+=lb(i)) t[i]+=k;}
} t;
void cdq(int l,int r) {
if(l>=r) return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
sort(b+l,b+mid+1,cmp2);
sort(b+mid+1,b+r+1,cmp3);
int i=l;
for(int j=mid+1;j<=r;j++) {
while(i<=mid&&b[i].xr<=b[j].xl) t.add(b[i].yr,1),i++;
ans[b[j].id]+=t.sum(b[j].yl);
}
for(int j=l;j<i;j++) t.add(b[j].yr,-1);
}
void solve() {
for(int i=1;i<=n;i++)
ans[b[i].id=a[i].id]-=t.sum(b[i].yl),t.add(b[i].yr,1);
for(int i=1;i<=n;i++) t.add(b[i].yr,-1);
cdq(1,n);
}
signed main() {
cin>>n;
for(int i=1;i<=n;i++) {
int xi=rd()+1,yi=rd()+1,ai=rd(),bi=rd();
a[i].id=i,ans[i]=n-i;
bx[++cntx]=a[i].xl=xi,bx[++cntx]=a[i].xr=xi+ai,
by[++cnty]=a[i].yl=yi,by[++cnty]=a[i].yr=yi+bi;
}
sort(bx+1,bx+cntx+1);qx=unique(bx+1,bx+cntx+1)-bx-1;
sort(by+1,by+cnty+1);qy=unique(by+1,by+cnty+1)-by-1;
for(int i=1;i<=n;i++)
a[i].xl=lower_bound(bx+1,bx+qx+1,a[i].xl)-bx,
a[i].xr=lower_bound(bx+1,bx+qx+1,a[i].xr)-bx,
a[i].yl=lower_bound(by+1,by+qy+1,a[i].yl)-by,
a[i].yr=lower_bound(by+1,by+qy+1,a[i].yr)-by;
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
b[i].xl=a[i].xl,b[i].xr=a[i].xr,b[i].yl=a[i].yl,b[i].yr=a[i].yr;
solve();
for(int i=1;i<=n;i++)
b[i].xl=a[i].yl,b[i].xr=a[i].yr,b[i].yl=ML-a[i].xr,b[i].yr=ML-a[i].xl;
solve();
for(int i=1;i<=n;i++)
b[i].xl=ML-a[i].xr,b[i].xr=ML-a[i].xl,b[i].yl=ML-a[i].yr,b[i].yr=ML-a[i].yl;
solve();
for(int i=1;i<=n;i++)
b[i].xl=ML-a[i].yr,b[i].xr=ML-a[i].yl,b[i].yl=a[i].xl,b[i].yr=a[i].xr;
solve();
for(int i=1;i<=n;i++)
if(!ans[i]) puts("DA");
else puts("NE");
return 0;
}