洛谷4648 [IOI2007] pairs 动物对数 范围与提示 一维：M 最大是 75000000 二维：M 最大是 75000 三维：M 最大是 75
要分情况讨论啊！
一维
双指针 随便搞，一个指头，没个头找个最大尾，计入答案。
二维
曼哈顿转切比雪夫+扫描线+树状数组 很容易想到一个点能看到的点呈一个45°斜角的正方形，这太难处理了。 转成切比雪夫距离就变成了端端正正的正方形，转换公式：(x,y)->(x+y,x-y)。 转好后，那不就是扫描线了？问题是求每个正方形中包含点的个数和。 一个正方形拆成3条线，一条是入，在(x-d,y)这个位置+1；第二条是查询，在(x,y)这个位置求sum(y-d,y+d)；第三条是出，给(x+d,y)-1。 很明显这样做的话是一个改点求段的树状数组。也可以维护一个改段求点的树状数组，不过时间上不如前者优秀。
三维
曼哈顿转切比雪夫+枚举+前缀和 可以看到三维中m的值是大大减小了，因为三维真的没有什么好方法来做。 可以先枚举一个点(x,y,z)，记它所处的层数于x，再枚举一个层数j，如果|x-j|<=d，那么我们就求第j层以(y,z)为正方形中心，边长为2*(d-|x-j|)中包含了多少个点。注意当x=j时自己也会被算一次，答案要额外减掉个n。 为了求出正方形内点的个数，预处理出一个前缀和s[x][y][z]表示在第x层矩形(1,1)-(y,z)中点的个数，查询时注意边界问题。
注释部分是改段求点。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=100010; namespace task1 { int n,d,m; int a[MAXN]; void solve() { scanf("%d%d%d",&n,&d,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); ll ans=0; for(int l=1,r=0;l<=n;l++) { while(r<n && a[r+1]-a[l]<=d) r++; ans+=r-l; } printf("%lld\n",ans); } } namespace task2 { int n,d,m; int b[MAXN*3];//debug struct U{int x,y1,y2,c;}a[MAXN*3];int len=0; bool cmp(U a1,U a2) { if(a1.x!=a2.x) return a1.x<a2.x; return a1.c>a2.c;//1-0-(-1)最前 } int s[MAXN*3]; void add(int x,int c) { for(;x<=len;x+=x&-x) s[x]+=c; } int query(int x) { int re=0; for(;x>=1;x-=x&-x) re+=s[x]; return re; } void solve() { scanf("%d%d%d",&n,&d,&m); for(int i=1;i<=n;i++) { int X,Y;scanf("%d%d",&X,&Y); int x=X+Y,y=X-Y; /*a[++len]=(U){x-d,y-d,y+d,1};b[len]=y;//debug b[len]=d a[++len]=(U){x+d,y-d,y+d,-1};b[len]=y-d; a[++len]=(U){x,y,0,0};b[len]=y+d;//0 统计答案的标记 */ a[++len]=(U){x-d,y,0,1};b[len]=y;//debug b[len]=d a[++len]=(U){x+d,y,0,-1};b[len]=y-d; a[++len]=(U){x,y-d,y+d,0};b[len]=y+d;//0 统计答案的标记 } sort(a+1,a+len+1,cmp); sort(b+1,b+len+1); ll ans=0; /*for(int i=1;i<=len;i++) if(!a[i].c) { int p=lower_bound(b+1,b+len+1,a[i].y1)-b; ans+=query(p); } else { int p1=lower_bound(b+1,b+len+1,a[i].y1)-b; int p2=lower_bound(b+1,b+len+1,a[i].y2)-b; add(p1,a[i].c);add(p2+1,-a[i].c); }*/ for(int i=1;i<=len;i++) if(a[i].c==0) { int p1=lower_bound(b+1,b+len+1,a[i].y1)-b; int p2=lower_bound(b+1,b+len+1,a[i].y2)-b; ans+=query(p2)-query(p1-1); } else { int p=lower_bound(b+1,b+len+1,a[i].y1)-b; add(p,a[i].c); } printf("%lld\n",(ans-n)/2); } } namespace task3 { const int MAXM=80; int n,d,m; struct U{int x,y,z;}a[MAXN]; ll s[MAXM][MAXM+MAXM][MAXM+MAXM]; ll query(int x,int y,int z) { if(y>150) y=150;else if(y<0) y=0; if(z>150) z=150;else if(z<0) z=0; return s[x][y][z]; } void solve() { scanf("%d%d%d",&n,&d,&m); for(int i=1;i<=n;i++) { int X,Y,Z;scanf("%d%d%d",&X,&Y,&Z); int x=Y+Z,y=Y-Z+75;//??? a[i]=(U){X,x,y};//debug {x,X,Y} s[X][x][y]++; } for(int i=1;i<=75;i++) for(int j=1;j<=150;j++) for(int k=1;k<=150;k++) s[i][j][k]+=s[i][j-1][k]+s[i][j][k-1]-s[i][j-1][k-1]; ll ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=75;j++) if(abs(a[i].x-j)<=d) { int rest=d-abs(a[i].x-j); ans+=query(j,a[i].y+rest,a[i].z+rest)+query(j,a[i].y-rest-1,a[i].z-rest-1) -query(j,a[i].y-rest-1,a[i].z+rest)-query(j,a[i].y+rest,a[i].z-rest-1);//正方形(a[i].y-rest,a[i].z-rest)-(a[i].y+rest,a[i].z+rest) } printf("%lld\n",(ans-n)/2); } } int main() { int B;scanf("%d",&B); if(B==1) task1::solve(); if(B==2) task2::solve(); if(B==3) task3::solve(); return 0; }
