CF762E

发现还没有 CDQ 分治的题解，来写一个。 一个最浅显的思路，就是找 $$ x_i<x_j$$ $$x_i+r_i\ge x_j$$ $$x_i\ge x_j-r_j$$ $$\left|f_i-f_j\right|\le k$$ 满足以上四个条件的点对数量。这四个偏序关系让我们很容易想到 CDQ 分治。 ~~所以就直接上四维 CDQ 吧~~。 这样会超时，所以，我们考虑简化条件。具体来说，就是把几个不等式合并，然后就可以尝试 CDQ 了。 很容易发现一二三式可以整合成 $$\left|x_i-x_j\right|\le \min(r_i,r_j)$$ 但是我们既然要使用 CDQ ，我们一定要保证不等式两边不会有相互的关系。以上这个式子不满足这个条件。所以我们需要拆掉绝对值，或者 $\min$。但显然，假如我们拆掉绝对值，那式子就拆回去了，所以我们考虑拆右边。那么条件可以化成： $$ r_j\le r_i$$ $$\left|x_i-x_j\right|\le r_j$$ $$\left|f_i-f_j\right|\le k$$ 所以我们先将所有点按 $r_i$ 排序，考虑如何满足下面两个式子。 这里我们考虑 $\mathrm{i}$ 向 $\mathrm{j}$ 做贡献的话，我们可以发现，假如我们使用双指针的方式来维护二式，首先就是要对于 $x_i$ 进行排序，这可能导致我们将前面的排除后，导致后面的没有统计到，但是三式 $k$ 为定值，所以得出以下顺序。 1. 排序满足一式 2. CDQ 满足三式（单边双指针实现） 4. 数据结构满足二式 这样这个题目就得以解决。 ```cpp #include<bits/stdc++.h> #define lb(x) x&-x #define N 100005 using namespace std; int n,k,m; long long ans; int pos1[N],pos2[N]; struct node{ int x,y,z,L,R; int id,flag; }p[N]; bool cmp1(node a,node b){ if(a.y!=b.y) return a.y>b.y; if(a.z!=b.z) return a.z<b.z; return a.x<b.x; } bool cmp2(node a,node b){ if(a.z!=b.z) return a.z<b.z; if(a.x!=b.x) return a.x<b.x; return a.y>b.y; } int c[3*N]; void add(int x,int v){ for(;x<=m;x+=lb(x)) c[x]+=v; } int ask(int x){ int sum=0; for(;x;x-=lb(x)) sum+=c[x]; return sum; } void clear(int x){ for(;x<=m;x+=lb(x)){ if(!c[x]) return ; c[x]=0; } } void solve(int l,int r){ if(l==r) return ; int mid=(l+r)>>1; solve(l,mid),solve(mid+1,r); sort(p+l,p+mid+1,cmp2); sort(p+mid+1,p+r+1,cmp2); int j1=l,j2=l-1; for(int i=mid+1;i<=r;i++){ while(j1<=mid&&p[i].z-p[j1].z>k) add(p[j1].x,-1),j1++; while(j2<mid&&p[j2+1].z-p[i].z<=k){ j2++; add(p[j2].x,1); } ans+=ask(p[i].R)-ask(p[i].L-1); } for(int i=j1;i<=j2;i++)add(p[i].x,-1); } int b[3*N],cnt; int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ int a,r,c; scanf("%d%d%d",&a,&r,&c); p[i].x=a; p[i].y=r; p[i].z=c; p[i].L=max(0,a-r); p[i].R=a+r; b[++cnt]=p[i].x; b[++cnt]=p[i].L; b[++cnt]=p[i].R; } sort(b+1,b+cnt+1); m=unique(b+1,b+cnt+1)-b-1; for(int i=1;i<=n;i++){ p[i].x=lower_bound(b+1,b+m+1,p[i].x)-b; p[i].L=lower_bound(b+1,b+m+1,p[i].L)-b; p[i].R=lower_bound(b+1,b+m+1,p[i].R)-b; } sort(p+1,p+n+1,cmp1); solve(1,n); printf("%lld\n",ans); return 0; } ``` 经过这个题，我们可以得出关于 CDQ 维护偏序问题时的两个小技巧。 1. 对于有交叉关系的偏序式子，可以尝试合并和简化。（实际上本题并没有减少不等式的数量，但是我们把它转化成可以用 CDQ 解决的形式） 2. 较复杂的不等式优先使用数据结构解决。