IOI2007 Pairs 动物对数

,

曼哈顿距离转切比雪夫距离。

B=1

排序直接搞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n,d,m;
namespace Solve1{
	int a[100005];ll ans;
	inline void main(void) {
		int i;
		for (i=1;i<=n;i++) read(a[i]);
		sort(a+1,a+1+n);
		int now=0,tot=0;
		for (i=1;i<=n;i++) {
			while (now<n&&a[now+1]+d<a[i]) now++,tot--;
			ans+=tot;tot++;
		}
		printf("%lld",ans);
	}
}

B=2

对于所有点 $(x,y)$ ，变换为 $(x+y,x-y)$ 。变换前的曼哈顿距离等于变换后的切比雪夫距离。

然后就是二维偏序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
namespace Solve2{
	struct yyy{
	int x,y;
	}a[maxn];
	inline bool cmp(yyy x,yyy y) {return x.x==y.x?x.y<y.y:x.x<y.x;}
	int root,cnt;
	struct node{
		int ls,rs,size;
	}f[maxn*30];
	inline void Update(int l,int r,int &rt,int head,int k) {
		if (!rt) rt=++cnt;f[rt].size+=k;
		if (l==r) return ;
		int mid=l+r>>1;
		if (head<=mid) Update(l,mid,f[rt].ls,head,k);
		else Update(mid+1,r,f[rt].rs,head,k);
	}
	inline int Query(int l,int r,int rt,int head,int tail) {
		if (!rt) return 0;
		if (head<=l&&r<=tail) return f[rt].size;
		int mid=l+r>>1,sum=0;
		if (head<=mid) sum+=Query(l,mid,f[rt].ls,head,tail);
		if (tail>mid) sum+=Query(mid+1,r,f[rt].rs,head,tail);
		return sum;
	}
	ll ans;
	inline void main(void) {
		int i,x,y;
		for (i=1;i<=n;i++) read(x),read(y),a[i].x=x+y,a[i].y=x-y;
		sort(a+1,a+1+n,cmp);
		int now=0,tot=0;
		for (i=1;i<=n;i++) {
			while (now<n&&a[now+1].x+d<a[i].x) now++,Update(-m,m*2,root,a[now].y,-1);
			ans+=Query(-m,m*2,root,max(-m,a[i].y-d),min(2*m,a[i].y+d));
			Update(-m,2*m,root,a[i].y,1);
		}
		printf("%lld",ans);
	}
}

B=3

同样的，$(x,y,z)$ 变换为 $(x+y+z,x+y-z,x-y+z,-x+y+z)$

四维偏序，支持点的增加与删除。排序去掉一维以后用三维树状数组维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
namespace Solve3{
	struct yyy{
		int x,y,z,w;
	}a[maxn];
	ll ans;
	#define lowbit(x) ((x)&(-x))
	int f[250][250][250];
	inline void add(int x,int y,int z,int w) {
		int i,j,k;
		for (i=x;i<=m;i+=lowbit(i))
			for (j=y;j<=m;j+=lowbit(j))
				for (k=z;k<=m;k+=lowbit(k))
					f[i][j][k]+=w;
	}
	inline int query(int x,int y,int z) {
		int i,j,k,sum=0;//printf("%d %d %d ",x,y,z);
		for (i=x;i;i-=lowbit(i))
			for (j=y;j;j-=lowbit(j))
				for (k=z;k;k-=lowbit(k))
					sum+=f[i][j][k];	
		return sum;
	}
	inline bool cmp(yyy x,yyy y){return x.w<y.w;}
	inline void main(){
		int i,j,k,l,x,y,z;
		for (i=1;i<=n;i++) {
			read(x);read(y);read(z);
			a[i].w=x+y+z+m;
			a[i].x=x+y-z+m;
			a[i].y=x-y+z+m;
			a[i].z=y+z-x+m;
	//		printf("%d %d %d\n",a[i].x,a[i].y,a[i].z);
		}
		m*=3;
		sort(a+1,a+1+n,cmp);
		int now=0;
		for (i=1;i<=n;i++) {
			while (now<n&&a[now+1].w+d<a[i].w) now++,add(a[now].x,a[now].y,a[now].z,-1);
			int rx=min(m,a[i].x+d),ry=min(m,a[i].y+d),rz=min(m,a[i].z+d);
			int lx=max(0,a[i].x-d-1),ly=max(0,a[i].y-d-1),lz=max(0,a[i].z-d-1);
			ans+=query(rx,ry,rz)
			-query(lx,ry,rz)-query(rx,ly,rz)-query(rx,ry,lz)
			+query(lx,ly,rz)+query(lx,ry,lz)+query(rx,ly,lz)
			-query(lx,ly,lz);			
			add(a[i].x,a[i].y,a[i].z,1);
		}
		printf("%lld",ans);
	}
}