[IOI2007]pairs 解题报告
https://www.luogu.com.cn/problem/P4648
观察题设方式，不难想到针对 \(B=1,2,3\) 单独作答。
\(B=1,O(N)\)
直接排序+双指针即可。
namespace ST1 {
int a[N]; ll ans;
void main(){
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1,j=1;i<=n;i++){
while(j<=n&&a[j]-a[i]<=d)j++;
ans+=j-i-1;
}
cout<\(B=2,O(N\log 3M)\)
在平面直角坐标系中，两个点 \((x_1,y_1),(x_2,y_2)\) 之间的曼哈顿距离 = \((x_1+y_1,x_1-y_1),(x_2+y_2,x_2-y_2)\) 之间的切比雪夫距离。
本题是一个不等式的限制，容易想到曼转切，将每个点 \((x,y)\to (x+y,x-y)\)。
先讲一个暴力思路
我们其实就是要对每个点 \((x,y)\) 求平面上 \((x-d,y-d)\to (x+d,y+d)\) 子矩阵和 \(-1\)（因为会包含 \((x,y)\) 自身）。
更好的思路
可以沿用上面的，以 \(x\) 关键字排序+双指针（下面记左右指针为 \(i,j\)），原因是切比雪夫距离 \(\max(x_j-x_i,y_j-y_i)\le d\) 成立的条件之一是 \(x_j-x_i\le d\)。
\(i,j\) 之间的 \(y\)，每到一个就加入桶，则转为求值域上 \([x_i-d,x_i+d]\) 的和。容易用树状数组维护。注意值域可能为负，统一加上 \(M\) 即可。
namespace ST2 {
int c[V+5]; ll ans;
struct P{int x,y;}a[N];
bool operator<(P a,P b){return a.x>a[i].x>>a[i].y,a[i].x+=a[i].y,a[i].y=a[i].x-2*a[i].y,a[i].x+=vm,a[i].y+=vm;
sort(a+1,a+n+1);
for(int i=1,j=1;i<=n;i++){
add(a[i].y,-1);
while(j<=n&&a[j].x-a[i].x<=d)add(a[j].y,1),j++;
ans+=ask(min(a[i].y+d,3*vm))-ask(max(a[i].y-d,1)-1);
}
cout< \(B=3,O(9M^2+N\cdot M)\)
当你从 \(B=2\) 看到 \(B=3\) 时，你会发现 \(M\) 一下子减到了 \(75\)，这意味着 \(B=2\) 的暴力可以用在这里，其实是题目给我们减少了代码量！
对 \((x,y,z)\) 的前二维曼转切，并将每个点看成 \(z\) 平面上的点，平面与平面之间分开。
对于每个点 \((x_i,y_i,z_i)\)，枚举另一个点的 \(z_j\)，则所求即 \(z_j\) 平面上的 \((x_i-l,y_i-l)\to(x_i+l,y_i+l)\) 子矩阵和 \(-[z_i=z_j]\)。
每个平面大小很小，预处理出二维前缀和。
namespace ST3 {
int s[U][U][U]; ll ans;
struct P{int x,y,z;}a[N];
void main(){
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y>>a[i].z,a[i].x+=a[i].y,a[i].y=a[i].x-2*a[i].y,a[i].x+=vm,a[i].y+=vm,s[a[i].z][a[i].x][a[i].y]++;
for(int c=1;c<=vm;c++)
for(int i=1;i<=3*vm;i++)
for(int j=1;j<=3*vm;j++)
s[c][i][j]+=s[c][i-1][j]+s[c][i][j-1]-s[c][i-1][j-1];
for(int i=1;i<=n;i++){
for(int j=1;j<=vm;j++){
int l=d-abs(a[i].z-j);
if(l<0)continue;
//(a[i].x-l,a[i].y-l)->(a[i].x+l,a[i].y+l)
int X1=max(a[i].x-l,1),Y1=max(a[i].y-l,1),X2=min(a[i].x+l,3*vm),Y2=min(a[i].y+l,3*vm);
ans+=s[j][X2][Y2]-s[j][X1-1][Y2]-s[j][X2][Y1-1]+s[j][X1-1][Y1-1]-(a[i].z==j);
}
}
cout<主函数
using namespace std;
const int N=1e5+5,V=75e4*3,U=75*3+5;
typedef long long ll;
int B,n,d,vm;
int main(){
cin>>B>>n>>d>>vm;
if(B==1)ST1::main();
if(B==2)ST2::main();
if(B==3)ST3::main();
}
易错点
- long long
- 加上 \(M\) 后值域为 \(3M\)