每个点覆盖的区域是一个斜放的正方形，用一条 x+y=b 的扫描线扫一遍，需要维护区间覆盖和单点查询。线段树就可以了。
#include<cstdio> #include<algorithm> using namespace std; #define LL long long const int maxn=100010; int rd() { int x=0; char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x; } struct str { int k,l,r,id; LL p; bool operator < (const str &s) const { if (p!=s.p) return p<s.p; return k>s.k; } }a[maxn*3]; int xx[maxn],yy[maxn],dis[maxn],ord[5*maxn],tag[15*maxn],ans[maxn], n,m,k,tot,res; void modi(int u,int L,int R,int l,int r,int x) { if (l<=L&&R<=r) { tag[u]+=x; return; } int mid=(L+R)/2; if (l<=mid) modi(u*2,L,mid,l,r,x); if (r>mid) modi(u*2+1,mid+1,R,l,r,x); } int qry(int u,int L,int R,int p) { if (L==R) return tag[u]; int mid=(L+R)/2; if (p<=mid) return qry(u*2,L,mid,p)+tag[u]; return qry(u*2+1,mid+1,R,p)+tag[u]; } int main() { /*freopen("berhatton.in","r",stdin); freopen("berhatton.out","w",stdout);*/ int x,l,r; n=rd(); k=rd(); for (int i=1;i<=n;i++) { xx[i]=rd(); yy[i]=rd(); dis[i]=rd(); ord[++m]=xx[i]-yy[i]; ord[++m]=xx[i]+dis[i]-yy[i]; ord[++m]=xx[i]-dis[i]-yy[i]; } sort(ord+1,ord+m+1); m=unique(ord+1,ord+m+1)-ord-1; for (int i=1;i<=n;i++) { x=lower_bound(ord+1,ord+m+1,xx[i]-yy[i])-ord; a[++tot]=(str){0,x,x,i,xx[i]+yy[i]}; l=lower_bound(ord+1,ord+m+1,xx[i]-yy[i]-dis[i])-ord; r=lower_bound(ord+1,ord+m+1,xx[i]-yy[i]+dis[i])-ord; a[++tot]=(str){1,l,r,0,xx[i]+yy[i]-dis[i]}; a[++tot]=(str){-1,l,r,0,(LL)xx[i]+yy[i]+dis[i]}; } sort(a+1,a+tot+1); for (int i=1;i<=tot;i++) if (a[i].k) modi(1,1,m,a[i].l,a[i].r,a[i].k); else if (qry(1,1,m,a[i].l)>k) ans[++res]=a[i].id; sort(ans+1,ans+res+1); printf("%d\n",res); for (int i=1;i<=res;i++) printf("%d%c",ans[i],i==res?'\n':' '); //fclose(stdout); }