BZOJ1807 [Ioi2007]Pairs 彼此能听得见的动物对数 [树状数组, 曼哈顿转切比雪夫]

$Pairs$

题目描述见链接 .

---

$color{red}{正解部分}$

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

---

然后解决第二个子任务:

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

切比雪夫距离: $d = max(|x_i-x_j|)$

设 $(x_1, y_1)$ 与 $(x_2, y_2)$ 的 曼哈顿距离 是 $d$, 则

$egin{aligned} & d = |x_1-x_2| + |y_1-y_2|\ & = max(x_1-x_2+y_1-y_2, x_2-x_1+y_1-y_2, x_1-x_2+y_2-y_1, x_2-x_1-y_2+y_1)\ & = max(|(x_1+y_1)- (x_2+y_2)|, |(x_1-y_1) -(x_2-y_2)|)\ end{aligned}$

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

---

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

---

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

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

---

$color{red}{实现部分}$

• 曼哈顿 转 切比雪夫 时 $y$ 坐标可能出现负数, 要注意加上一个数 .
• 注意 第三个子任务 统计答案时 当 $z_2 = z_1$ 时 $(x, y)$ 会计算 $2$ 次, 因此同一个面的答案要除 $2$ .
• 子任务一的指针 初值必须为 $1$, 不能为 $0$ .
• 子任务三 中 前缀和数组 $y$维 的大小原应该开 $3M$ , 由于下标右移数组大小需要增大 $M$, 总共需要开 $4M$ .
  但是为了保险还是尽量开 理论上的 $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
", 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
", 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
", 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;
}