2 条题解

  • 0
    @ 2026-9-3 21:01:26

    这题好像没有通法，所以我选择分部来写

    1.暴力

    对于n≤1000n \le 1000 ,O(n2n ^ 2)枚举点不多讲

    #include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200500
using namespace std;

inline int read() {
	int x = 0,f = 1; char s = getchar();
	while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
	while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar();}
	return x * f;
}

int n,m,B,D;
int b[N][4];

inline int DD(int x) {return x < 0 ? -x : x;}

inline bool Calc(int x,int y) {
	int x1 = b[x][0],y1 = b[x][1],z1 = b[x][2];
	int x2 = b[y][0],y2 = b[y][1],z2 = b[y][2];
	if(DD(x1 - x2) + DD(y1 - y2) + DD(z1 - z2) <= D) return true;
	return false;
}

int main() {
	B = read(),n = read(),D = read(),m = read();
	
	int ans = 0;
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j < B;j ++)
			b[i][j] = read();
	for(int i = 1;i <= n;i ++)
		for(int j = i + 1;j <= n;j ++)
			if(Calc(i,j)) ans ++;
	printf("%d\n",ans);
	
	return 0;
}

    2.B == 1 的情况

    一维可以考虑下权值线段树，MM过大可以考虑动态开点

    具体怎么实现呢：

    对于点ii,设它坐标为x[i]x[i]，那么，对答案有影响的是（x[i]−Dx[i]-D,x[i]+Dx[i]+D）的范围

    所以，对于前i−1i -1 个点，用权值线段树来维护（x[i]−Dx[i]-D,x[i]+Dx[i]+D）区间上点的个数，

    统计完成后，在将次点插入到线段树中即可

    #include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200500
using namespace std;

inline int read() {
	int x = 0,f = 1; char s = getchar();
	while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
	while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar();}
	return x * f;
}

int n,m,B,D;
struct node {
	int x,y,z;
}a[N];

inline int DD(int x) {return x < 0 ? -x : x;}

struct Tree {
	int l,r;
	long long tag;
} tr[N * 50];
int tot,root;

inline void Insert(int &k,int l,int r,int a) {
	if(!k) k = ++ tot;
	if(l == r) {
		tr[k].tag ++;
		return ;
	}
	int mid = (l + r) >> 1;
	if(a <= mid) Insert(tr[k].l,l,mid,a);
	else Insert(tr[k].r,mid + 1,r,a);
	tr[k].tag = tr[tr[k].l].tag + tr[tr[k].r].tag;
}

inline long long Ask(int k,int l,int r,int a,int b) {
	if(!k) return 0;
	if(a <= l && r <= b) return tr[k].tag;
	int mid = (l + r) >> 1; long long res = 0;
	if(a <= mid) res += Ask(tr[k].l,l,mid,a,b);
	if(b > mid) res += Ask(tr[k].r,mid + 1,r,a,b);
	return res;
}

int main() {
	B = read(),n = read(),D = read(),m = read();
	
    if(B == 1) {
		long long ans = 0;
		for(int i = 1;i <= n;i ++)
			a[i].x = read();
		for(int i = 1;i <= n;i ++) {
			ans += Ask(root,1,m,a[i].x - D,a[i].x + D);
			Insert(root,1,m,a[i].x);
		}
		printf("%lld\n",ans); return 0;
	}
    
	return 0;
}

    3.B == 2 的情况

    这就比较自闭了

    由题意得，距离公式为dis=∣x1−x2∣+∣y1−y2∣dis=|x_1- x_2|+|y_1-y_2|

    要使dis≤Ddis \le D ,发现以ii为中心，2∗D2*D的对角线长的菱形为覆盖矩阵（不懂得可以画画图）

    发现，难以维护菱形中的点的个数；

    所以，我们要旋转坐标系，disdis为曼哈顿距离，也就是转为切比雪夫公式就行了

    具体的证明（不太会，我的理解）就是：

    重写便曼哈顿距离：dis=∣x1−x2∣+∣y1−y2∣dis=|x_1- x_2|+|y_1-y_2|

    把绝对值拆开:

    1.disdis = x1x_1 - x2x_2 + y1y_1 - y2y_2 (x1≥x2x_1\ge x_2 且y1≥y2y_1 \ge y_2)

    2.disdis = x2x_2 - x1x_1 + y1y_1 - y2y_2 (x1≤x2x_1 \le x_2 且y1≥y2y_1 \ge y_2)

    3.disdis = x1x_1 - x2x_2 + y2y_2 - y1y_1 (x1≥x2x_1 \ge x_2 且y1≤y2y_1 \le y_2)

    4.disdis = x2x_2 - x1x_1 + y2y_2 - y1y_1 (x1≤x2x_1 \le x_2 且y1≤y2y_1 \le y_2)

    发现：1与41与4互为绝对值，2与32与3互为绝对值

    在把柿子组合下：$dis = max(|(x_1 + y_1) - (x_2 + y_2)|,|(x_1+y_2) - (x_2 + y_1)|)$

    这个和切比雪夫公式对比下：dis=max(∣x1−x2∣,∣y1−y2∣)dis = max(|x_1-x_2|,|y_1-y_2|)

    发现对于坐标(xi,yi)(x_i,y_i),可以转化为(xi+yi,xi−yi)(x_i+y_i,x_i-y_i)

    具体的操作是，对于转化后的点：

    先按xx为关键字排序，O(n)O(n)扫描，再用一个指针来记录ii这个点的最远的距离，设为tailtail

    那么，对于tail−>itail->i的区间，再符合yiy_i的坐标范围就行啦；可以用上文提到的权值线段树维护yiy_i

    代码：

    #include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200500
using namespace std;

inline int read() {
	int x = 0,f = 1; char s = getchar();
	while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
	while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar();}
	return x * f;
}

int n,m,B,D;
struct node {
	int x,y,z;
}a[N];

inline int DD(int x) {return x < 0 ? -x : x;}

struct Tree {
	int l,r;
	long long tag;
} tr[N * 50];
int tot,root;

inline void Insert(int &k,int l,int r,int a,int b) {
	if(!k) k = ++ tot;
	if(l == r) {
		tr[k].tag += b;
		return ;
	}
	int mid = (l + r) >> 1;
	if(a <= mid) Insert(tr[k].l,l,mid,a,b);
	else Insert(tr[k].r,mid + 1,r,a,b);
	tr[k].tag = tr[tr[k].l].tag + tr[tr[k].r].tag;
}

inline long long Ask(int k,int l,int r,int a,int b) {
	if(!k) return 0;
	if(a <= l && r <= b) return tr[k].tag;
	int mid = (l + r) >> 1; long long res = 0;
	if(a <= mid) res += Ask(tr[k].l,l,mid,a,b);
	if(b > mid) res += Ask(tr[k].r,mid + 1,r,a,b);
	return res;
}

inline bool cmp1(const node &a,const node &b) {
	return a.x < b.x;
}

int main() {
	B = read(),n = read(),D = read(),m = read();
	
	if(B == 2) {
		long long ans = 0;
		for(int i = 1;i <= n;i ++)
			a[i].x = read(),a[i].y = read();
		for(int i = 1;i <= n;i ++) {
			int x = a[i].x,y = a[i].y;
			a[i].x = x + y; 
			a[i].y = x - y;
		}
		sort(a + 1,a + n + 1,cmp1); 
		int tl = 1; Insert(root,-m,m,a[1].y,1);
		for(int i = 2;i <= n;i ++) {
			while(DD(a[tl].x - a[i].x) > D)
				Insert(root,-m,m,a[tl].y,-1),tl ++;
			ans += Ask(root,-m,m,a[i].y - D,a[i].y + D);
			Insert(root,-m,m,a[i].y,1);
		}
		printf("%lld\n",ans); return 0;
	}
	
	return 0;
}

    3.B==3的情况

    观察到M≤75M\le75 ,显然可以乱搞

    其实也不是乱搞；

    借鉴下B==2B==2的情况，可以想到B==2B==2时时一个平面

    而对于此情况可以把维度提高，也就是多个平面

    再次提及M≤75M\le75，所以对于每层开个桶；

    之后对于每层求二维前缀和，这样就可以O(1)O(1)求此面的任意大小的矩形中点的个数

    不妨设ii号所在层数为zz

    那么可以强制选zz层以下的，这样可以不会算重

    对于zz这一层要单独来算贡献，因为计算时会记录自己，并且同层会记录两边，所以要单独计算

    具体见代码：

    #include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200500
using namespace std;

inline int read() {
	int x = 0,f = 1; char s = getchar();
	while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
	while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar();}
	return x * f;
}

int n,m,B,D;
struct node {
	int x,y,z;
}a[N];
int buk[100][155][155];

inline int DD(int x) {return x < 0 ? -x : x;}

int main() {
	B = read(),n = read(),D = read(),m = read();
	
	if(B == 3) {
		for(int i = 1;i <= n;i ++)
			a[i].x = read(),a[i].y = read(),a[i].z = read();
		for(int i = 1;i <= n;i ++) {
			int x = a[i].x,y = a[i].y;
			a[i].x = x + y;
			a[i].y = x - y + m;
		}
		for(int i = 1;i <= n;i ++) 
			buk[a[i].z][a[i].x][a[i].y] ++;
		for(int k = 1;k <= m;k ++) {
			for(int i = 1;i <= m * 2;i ++)
				for(int j = 1;j <= m * 2;j ++)
					buk[k][i][j] += buk[k][i - 1][j] + buk[k][i][j - 1] - buk[k][i - 1][j - 1];
		}
		long long ans1 = 0,ans2 = 0;
		for(int i = 1;i <= n;i ++) {
			for(int j = max(1,a[i].z - D);j < a[i].z;j ++) {
				int d = D - (a[i].z - j);
				int x1 = max(1,a[i].x - d),x2 = min(m * 2,a[i].x + d);
				int y1 = max(1,a[i].y - d),y2 = min(m * 2,a[i].y + d);
				ans1 += buk[j][x2][y2] - buk[j][x2][y1 - 1] - buk[j][x1 - 1][y2] + buk[j][x1 - 1][y1 - 1];
			}
			int d = D;
			int x1 = max(1,a[i].x - d),x2 = min(m * 2,a[i].x + d);
			int y1 = max(1,a[i].y - d),y2 = min(m * 2,a[i].y + d);
			ans2 += buk[a[i].z][x2][y2] - buk[a[i].z][x2][y1 - 1] - buk[a[i].z][x1 - 1][y2] + buk[a[i].z][x1 - 1][y1 - 1];
		}
		ans1 += (ans2 - n) / 2;
		printf("%lld\n",ans1); return 0;
	}
	
	return 0;
}

    最后，放上AC代码：

    #include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200500
using namespace std;

inline int read() {
	int x = 0,f = 1; char s = getchar();
	while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
	while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar();}
	return x * f;
}

int n,m,B,D;
struct node {
	int x,y,z;
}a[N];
int buk[100][155][155];

inline int DD(int x) {return x < 0 ? -x : x;}

struct Tree {
	int l,r;
	long long tag;
} tr[N * 50];
int tot,root;

inline void Insert(int &k,int l,int r,int a,int b) {
	if(!k) k = ++ tot;
	if(l == r) {
		tr[k].tag += b;
		return ;
	}
	int mid = (l + r) >> 1;
	if(a <= mid) Insert(tr[k].l,l,mid,a,b);
	else Insert(tr[k].r,mid + 1,r,a,b);
	tr[k].tag = tr[tr[k].l].tag + tr[tr[k].r].tag;
}

inline long long Ask(int k,int l,int r,int a,int b) {
	if(!k) return 0;
	if(a <= l && r <= b) return tr[k].tag;
	int mid = (l + r) >> 1; long long res = 0;
	if(a <= mid) res += Ask(tr[k].l,l,mid,a,b);
	if(b > mid) res += Ask(tr[k].r,mid + 1,r,a,b);
	return res;
}

inline bool cmp1(const node &a,const node &b) {
	return a.x < b.x;
}

int main() {
	B = read(),n = read(),D = read(),m = read();
	
	if(B == 1) {
		long long ans = 0;
		for(int i = 1;i <= n;i ++)
			a[i].x = read();
		for(int i = 1;i <= n;i ++) {
			ans += Ask(root,1,m,a[i].x - D,a[i].x + D);
			Insert(root,1,m,a[i].x,1);
		}
		printf("%lld\n",ans); return 0;
	}
	
	if(B == 2) {
		long long ans = 0;
		for(int i = 1;i <= n;i ++)
			a[i].x = read(),a[i].y = read();
		for(int i = 1;i <= n;i ++) {
			int x = a[i].x,y = a[i].y;
			a[i].x = x + y; 
			a[i].y = x - y;
		}
		sort(a + 1,a + n + 1,cmp1); 
		int tl = 1; Insert(root,-m,m,a[1].y,1);
		for(int i = 2;i <= n;i ++) {
			while(DD(a[tl].x - a[i].x) > D)
				Insert(root,-m,m,a[tl].y,-1),tl ++;
			ans += Ask(root,-m,m,a[i].y - D,a[i].y + D);
			Insert(root,-m,m,a[i].y,1);
		}
		printf("%lld\n",ans); return 0;
	}
	
	if(B == 3) {
		for(int i = 1;i <= n;i ++)
			a[i].x = read(),a[i].y = read(),a[i].z = read();
		for(int i = 1;i <= n;i ++) {
			int x = a[i].x,y = a[i].y;
			a[i].x = x + y;
			a[i].y = x - y + m;
		}
		for(int i = 1;i <= n;i ++) 
			buk[a[i].z][a[i].x][a[i].y] ++;
		for(int k = 1;k <= m;k ++) {
			for(int i = 1;i <= m * 2;i ++)
				for(int j = 1;j <= m * 2;j ++)
					buk[k][i][j] += buk[k][i - 1][j] + buk[k][i][j - 1] - buk[k][i - 1][j - 1];
		}
		long long ans1 = 0,ans2 = 0;
		for(int i = 1;i <= n;i ++) {
			for(int j = max(1,a[i].z - D);j < a[i].z;j ++) {
				int d = D - (a[i].z - j);
				int x1 = max(1,a[i].x - d),x2 = min(m * 2,a[i].x + d);
				int y1 = max(1,a[i].y - d),y2 = min(m * 2,a[i].y + d);
				ans1 += buk[j][x2][y2] - buk[j][x2][y1 - 1] - buk[j][x1 - 1][y2] + buk[j][x1 - 1][y1 - 1];
			}
			int d = D;
			int x1 = max(1,a[i].x - d),x2 = min(m * 2,a[i].x + d);
			int y1 = max(1,a[i].y - d),y2 = min(m * 2,a[i].y + d);
			ans2 += buk[a[i].z][x2][y2] - buk[a[i].z][x2][y1 - 1] - buk[a[i].z][x1 - 1][y2] + buk[a[i].z][x1 - 1][y1 - 1];
		}
		ans1 += (ans2 - n) / 2;
		printf("%lld\n",ans1); return 0;
	}
	
	return 0;
}

    撒花✿✿ヽ(°▽°)ノ✿

    • 0
      @ 2026-9-3 20:53:03

      很显然是将一维，二维，三维的情况分类讨论

      一维：

      排序后，维护一个单调指针即可

      代码（每一维我写在一个namespace里，Orz就当是这个namespace的主函数，而且我#define int long long了下同）

          int a[MAXN],d;
    void Orz() {
        scanf("%lld%lld%lld",&n,&d,&m);
        for(int i = 1; i <= n; i ++)
            scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        int j = 1;
        LL ans = 0;
        for(int i = 1; i <= n; i ++) {
            while(a[i] - a[j] > d && j < i) j ++;
            ans += i-j;
        }
        cout<<ans;
    }

      二维： 先将曼哈顿距离转化为切比雪夫距离

      不会的见这篇候选队里的日报

      下面的x,y自动视为在切比雪夫距离下的

      之后我们就将点按照y排序

      然后扫描每个点

      设该点坐标(x,y)

      用树状数组维护坐标为对于每个xix_i, (y-d <= yiy_i)的点数，同时排序后(xi,yi)(x_i,y_i)要在(x,y)(x,y)前面

      然后查询在[x−d,x+d][x-d,x+d]的点数

      struct aa
    {
        int x,y; 
    }a[MAXN];
    int d;

    bool cmp(aa a,aa b) {
        return a.y < b.y ;
    }

    void rd()
    {
        scanf("%lld%lld%lld",&n,&d,&m);
        for(int i = 1; i <= n; i ++)
        { 
        int x,y;
            scanf("%lld%lld",&x,&y);
            a[i].x = x+y;
            a[i].y = x-y; 
        }
        sort(a+1,a+n+1,cmp);
    }

    int c[MAXN*2];
    void jia(int x,int y)
    {
        while(x <= 2*m) {
            c[x] += y;
            x += lowbit(x);
        }
    }

    int he(int x)
    {
    	if(x > 2*m) x = 2*m; 
        int ans = 0;
        while(x > 0) {
            ans += c[x];
            x -= lowbit(x);
        } 
        return ans;
    }

    void Orz()
    {
        rd();
        int j = 1;
        LL ans = 0;
        for(int i = 1; i <= n; i ++) 
        {
            while(mabs(a[i].y - a[j].y) > d)  {//听说abs不资瓷long long？窝写了一个mabs
                jia(a[j].x,-1);
                j ++;
            }
            ans += he(a[i].x + d) - he(a[i].x - d-1);
            cout<<ans<<"\n";
            jia(a[i].x,1);
        }
        cout<<ans;
    }

      三维：

      注意到此时m很小，m<=75m <= 75

      我们可先将x,yx,y两维转切比雪夫距离

      然后转换后(x1,y1,z1)(x_1,y_1,z_1) (x2,y2,z2)(x_2,y_2,z_2)距离就变成了

      max(x1−x2,y1−y2)+(z1−z2)max(x_1 - x_2,y_1 - y_2) + (z_1 - z_2)

      然后我们将点按照z排序

      之后我们对于一个点 (xa,ya,za)(x_a,y_a,z_a)

      求出所有 za−d<=z<=zaz_a-d <= z <= z_a，x+za−z<=d,y+za−z<=dx+z_a - z <= d,y+z_a - z <= d的点数

      我们可以维护每一个面，点的个数的二维前缀和

      然后枚举每个面 查询一个正方形点的个数即可

      为了防止 a点 -> b点 b点->a点 重复枚举

      建议在同一个面的情况特殊处理

          struct aa {
        int x,y,z;
    } a[MAXN];
    int n,m;
    
    signed c[82][505][505];
    LL s[82][505][505];

    LL zfx(int i,int x,int y,int d)//[x-d,x+d][y-d,y+d]的正方形点数
    {
return s[i][x+d][y+d+75] - s[i][max((LL)0,x-d-1)][y+d+75]
- s[i][x+d][max((LL)0,y-d-1+75)] + s[i][max((LL)0,x-d-1)][max((LL)0,y-d-1+75)];
    } 
    LL ans = 0;
    void Orz()
    {
        scanf("%lld%lld%lld",&n,&d,&m);
        for(int i = 1; i <= n; i ++) {
            int x,y;
            scanf("%lld%lld%lld",&x,&y,&a[i].z);
            a[i].x = (x+y);
            a[i].y = x-y;
        
            c[a[i].z][a[i].x][a[i].y+75] ++;//因为a[i].y会有 < 0情况，所以加了75
  
        }
        //getchar();
        for(int i = 1; i <= m; i ++)
            for(int j = 0; j <= m*5+5; j ++)
                for(int k = -75; k <= m*5+5; k ++)
                {
                    s[i][j][k+75] = c[i][j][k+75] + s[i][j][k-1+75] + s[i][j-1][k+75] - s[i][j-1][k-1+75]; 
                }
        LL an = 0;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j < a[i].z; j ++)
            if(a[i].z - j <= d)
			{
                ans += zfx(j,a[i].x,a[i].y,d - (a[i].z - j));//同一个面的情况
            }
            int ro = i;

            an += zfx(a[i].z,a[i].x,a[i].y,d);

            an --;
        }
        cout<<ans + (an>>1);	
    }
      • 1

      [IOI 2007] pairs 动物对数

      信息

      ID
      3463
      时间
      4000ms
      内存
      268MiB
      难度
      10
      标签
      递交数
      2
      已通过
      1
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 12ms
      4. Powered by Hydro v5.0.1 Community