题解 P4648 【[IOI2007] pairs 动物对数】

· · 题解

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

一维：

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

代码（每一维我写在一个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)

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

然后查询在[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 <= 75

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

然后转换后(x_1,y_1,z_1) (x_2,y_2,z_2)距离就变成了

max(x_1 - x_2,y_1 - y_2) + (z_1 - z_2)

然后我们将点按照z排序

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

求出所有 z_a-d <= z <= z_a，x+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);    
    }