$Pairs$Pairs

题目描述见链接 .

$正解部分$正解部分

第一个子任务额外开一个指针即可解决问题, 这里不再多说 .

然后解决第二个子任务:

首先要知道 曼哈顿距离 转 切比雪夫距离,
这里补充以下内容,

切比雪夫距离: $d=\max (\mid x_i-x_j\mid )$d=max(∣xi​−xj​∣)

设 $(x_1,y_1)$(x1​,y1​) 与 $(x_2,y_2)$(x2​,y2​) 的 曼哈顿距离 是 $d$d, 则

​d=∣x1​−x2​∣+∣y1​−y2​∣  =max(x1​−x2​+y1​−y2​, x2​−x1​+y1​−y2​, x1​−x2​+y2​−y1​, x2​−x1​−y2​+y1​)  =max(∣(x1​+y1​)−(x2​+y2​)∣,∣(x1​−y1​)−(x2​−y2​)∣)​

由此得出 $d$d 同样可以表示为 $(x_1+y_1,x_1-y_1)$(x1​+y1​,x1​−y1​) 与 $(x_2+y_2,x_2-y_2)$(x2​+y2​,x2​−y2​) 之间的 切比雪夫距离 .

将所有坐标 $(x_i,y_i)$(xi​,yi​) 转化为 $(x_i+y_i,x_i-y_i)$(xi​+yi​,xi​−yi​) 后,
$(x_1,y_1)$(x1​,y1​) 和 $(x_2,y_2)$(x2​,y2​) 能够互相听见的条件变为了 $\max (\mid x_2-x_1\mid ,\mid y_2-y_1\mid )\le D$max(∣x2​−x1​∣,∣y2​−y1​∣)≤D ,
于是把坐标按 $x$x 坐标排序, 维护一个类似 子任务一 的指针保证 $\mid x_2-x_1\mid \le D$∣x2​−x1​∣≤D,
然后使用 以 $y$y 为下标的 树状数组 去查询 $[y_i-D,y_i+D]$[yi​−D,yi​+D] 内的点数 即为 $i$i 对答案的贡献 .

现在来讨论第三个子任务怎么解决,

同样将 $x,y$x,y 两维放到 切比雪夫 坐标系中, $z$z 仍然在 曼哈顿 坐标系中,
由于 $M\le 75$M≤75, 所以每个面可以维护一个前缀和 $sum[i,j]$sum[i,j] 表示这个面 $(i,j)$(i,j) 点左下方的动物数量,
按 $z$z 为第一关键字, $x$x 为第二关键字, $y$y 为第三关键字 从小到大 排序, 然后遍历,
设现在要计算点 $(x_1,y_1,z_1)$(x1​,y1​,z1​) 对答案的贡献, 首先枚举 $z$z 为 $z_2$z2​ 的面, 其中 $z_2\le z_1$z2​≤z1​,
然后求这个面中满足条件: $\max (\mid x_1-x_2\mid ,\mid y_1-y_2\mid )+z_1-z_2\le D$max(∣x1​−x2​∣,∣y1​−y2​∣)+z1​−z2​≤D 的点数,
化简得 $\max (\mid x_1-x_2\mid ,\mid y_1-y_2\mid )\le D-(z_1-z_2)$max(∣x1​−x2​∣,∣y1​−y2​∣) ≤ D−(z1​−z2​), 设 $d=D-(z_1-z_2)$d=D−(z1​−z2​),
取出 $x$x 进行化简, $\mid x_1-x_2\mid \le d$∣x1​−x2​∣≤d, 得 $x_1-x_2\le d$x1​−x2​≤d 或者 $x_2-x_1\le d$x2​−x1​≤d,
$y$y 的化简同理,
最后只需要在 $\left(\right[x-d,x+d],[y-d,y+d\left]\right)$([x−d,x+d],[y−d,y+d]) 使用前缀和查询即可 .

$实现部分$实现部分

• 曼哈顿 转 切比雪夫 时 $y$y 坐标可能出现负数, 要注意加上一个数 .
• 注意 第三个子任务 统计答案时 当 $z_2=z_1$z2​=z1​ 时 $(x,y)$(x,y) 会计算 $2$2 次, 因此同一个面的答案要除 $2$2 .
• 子任务一的指针 初值必须为 $1$1, 不能为 $0$0 .
• 子任务三 中 前缀和数组 $y$y维 的大小原应该开 $3M$3M , 由于下标右移数组大小需要增大 $M$M, 总共需要开 $4M$4M .
  但是为了保险还是尽量开 理论上的 $2$2 倍吧 …
• 这道题目卡空间, 开数组要尽量节制 …

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 1e5 + 5;

int N;
int D;
int M;

ll Ans;

struct Node{ int x, y, z, id; } A[maxn];

bool cmp_1(Node a, Node b){ return a.x==b.x?(a.y==b.y?a.z<b.z:a.y<b.y):a.x<b.x; }

namespace Task_1{ 
        void Solve_1(){ 
                N = read(), D = read(), M = read(); 
                for(reg int i = 1; i <= N; i ++) A[i].x = read(); 
                std::sort(A+1, A+N+1, cmp_1); 
                int t = 1; 
                for(reg int i = 1; i <= N; i ++){ 
                        while(t < i && A[i].x - A[t].x > D) t ++; 
                        Ans += i - t; 
                } 
                printf("%lld\n", Ans); 
        }
}

namespace Task_2{

        struct Bit_Tree{
                int v[200005];
                void Add(int k, int x){ while(k<=M)v[k]+=x,k+=k&-k; }
                int Query(int k){ if(k<=0) return 0; int s=0; while(k)s+=v[k],k-=k&-k; return s; }
        } bit_t;

        void Solve_2(){
                N = read(), D = read(), M = read();
                for(reg int i = 1; i <= N; i ++){
                        A[i].x = read(), A[i].y = read();
                        int tmp = A[i].x;
                        A[i].x = A[i].x + A[i].y;
                        A[i].y = tmp - A[i].y + M;
                }
                std::sort(A+1, A+N+1, cmp_1);
                int t = 0; M <<= 1;
                for(reg int i = 1; i <= N; i ++){
                        while(t < i && A[i].x-A[t].x > D){ if(t != 0) bit_t.Add(A[t].y, -1); t ++; }
                        int l = std::max(0, A[i].y-D), r = std::min(M, A[i].y+D);
                        int res = bit_t.Query(r) - bit_t.Query(l-1);
                        Ans += res;
                        bit_t.Add(A[i].y, 1);
                }
                printf("%lld\n", Ans);
        }
}

namespace Task_3{

        ll Tmp_1;

        int sum[80][355][505];

        bool cmp_2(Node a, Node b){ return a.z==b.z?(a.x==b.x?a.x<b.x:a.y<b.y):a.z<b.z; }

        void Solve_3(){
                N = read(), D = read(), M = read();
                D = std::min(D, 4*M);
                for(reg int i = 1; i <= N; i ++){
                        A[i].x = read(), A[i].y = read(), A[i].z = read();
                        int tmp = A[i].x;
                        A[i].x = A[i].x + A[i].y, A[i].y = tmp - A[i].y;
                        sum[A[i].z][A[i].x][A[i].y+M] ++, Tmp_1 --;
                }
                for(reg int i = 1; i < 80; i ++)
                        for(reg int j = 1; j < 355; j ++)
                                for(reg int k = -M+1; k < 400; k ++)
                                        sum[i][j][k+M] += sum[i][j-1][k+M] + sum[i][j][k-1+M] - sum[i][j-1][k-1+M];
                std::sort(A+1, A+N+1, cmp_2);
                for(reg int i = 1; i <= N; i ++){
                        for(reg int j = 1; j < A[i].z; j ++){
                                int new_d = D - (A[i].z - j);
                                if(new_d < 0) continue ;
                                int x2 = std::max(1, A[i].x-new_d), y2 = std::max(1, A[i].y-new_d+M);
                                Ans += sum[j][A[i].x+new_d][A[i].y+new_d+M] - sum[j][x2-1][A[i].y+new_d+M] - sum[j][A[i].x+new_d][y2-1] + sum[j][x2-1][y2-1];
                        } 
                        int j = A[i].z;
                        int new_d = D - (A[i].z - j); 
                        if(new_d < 0) continue ; 
                        int x2 = std::max(1, A[i].x-new_d), y2 = std::max(1, A[i].y-new_d+M); 
                        Tmp_1 += sum[j][A[i].x+new_d][A[i].y+new_d+M] - sum[j][x2-1][A[i].y+new_d+M] - sum[j][A[i].x+new_d][y2-1] + sum[j][x2-1][y2-1];
                }
                Ans += Tmp_1 >> 1;
                printf("%lld\n", Ans);
        }
}

int main(){
        int Type = read();
        if(Type == 1) Task_1::Solve_1();
        else if(Type == 2) Task_2::Solve_2();
        else Task_3::Solve_3();
        return 0;
}