CF762E

chen_qian · 2021-03-22 19:40:33 · 题解

发现还没有 CDQ 分治的题解，来写一个。

一个最浅显的思路，就是找

满足以上四个条件的点对数量。这四个偏序关系让我们很容易想到 CDQ 分治。

所以就直接上四维 CDQ 吧。

这样会超时，所以，我们考虑简化条件。具体来说，就是把几个不等式合并，然后就可以尝试 CDQ 了。

很容易发现一二三式可以整合成

但是我们既然要使用 CDQ ，我们一定要保证不等式两边不会有相互的关系。以上这个式子不满足这个条件。所以我们需要拆掉绝对值，或者 \min。但显然，假如我们拆掉绝对值，那式子就拆回去了，所以我们考虑拆右边。那么条件可以化成：

所以我们先将所有点按 r_i 排序，考虑如何满足下面两个式子。

这里我们考虑 \mathrm{i} 向 \mathrm{j} 做贡献的话，我们可以发现，假如我们使用双指针的方式来维护二式，首先就是要对于 x_i 进行排序，这可能导致我们将前面的排除后，导致后面的没有统计到，但是三式 k 为定值，所以得出以下顺序。

1. 排序满足一式

2. CDQ 满足三式（单边双指针实现）

3. 数据结构满足二式

这样这个题目就得以解决。

#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. 较复杂的不等式优先使用数据结构解决。