HDU - 5618 Jam's problem again(cdq分治和整体二分)

悠悠 2022-06-07 09:52 160阅读 0赞

[点我看题][Link 1]

题意:在三维坐标系中有n个点(x,y,z),对于某两个点i(xi,yi,zi)和j(xj,yj,zj),如果xi>xj且yi>yj且zi>zj,则i点的level加1,求每个点的level.

分析:cdq分治+树状数组.

参考代码:

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    const int maxn = 1e5+10;
    int n;
    struct Point{
        int x,y,z,id;
        Point(){}
        Point( int xx, int yy, int zz, int i)
        {
            x = xx, y = yy, z = zz, id = i;
        }
    }p[maxn],tmp[maxn];
    int maxz;
    int res[maxn];
    int bit[maxn];
    
    bool cmp( Point p, Point q)
    {
        if( p.x != q.x)
            return p.x < q.x;
        if( p.y != q.y)
            return p.y < q.y;
        return p.z < q.z;
    }
    
    bool cmp1( Point p, Point q)
    {
        if( p.y != q.y)
            return p.y < q.y;
        return p.id < q.id;
    }
    
    inline int lowbit( int x)
    {
        return x&(-x);
    }
    
    void add( int x, int val)
    {
        while( x <= maxz)
        {
            bit[x] += val;
            x += lowbit(x);
        }
    }
    
    int sum( int x)
    {
        int ans = 0;
        while( x)
        {
            ans += bit[x];
            x -= lowbit(x);
        }
        return ans;
    }
    
    void cdq( int l, int r)
    {
        if( l == r)
            return;
        int mid = (l+r)>>1;
        int sub = 0;
        for( int i = l; i <= mid; i++)
            tmp[sub++] = Point(0,p[i].y,p[i].z,0);
        for( int i = mid+1; i <= r; i++)
            tmp[sub++] = Point(0,p[i].y,p[i].z,p[i].id);
        sort(tmp,tmp+sub,cmp1);
        for( int i = 0; i < sub; i++)
        {
            if( tmp[i].id == 0)
                add(tmp[i].z,1);
            else
                res[tmp[i].id] += sum(tmp[i].z);
        }
        for( int i = 0; i < sub; i++)
            if( tmp[i].id == 0)
                add(tmp[i].z,-1);
        cdq(l,mid);
        cdq(mid+1,r);
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            maxz = 0;
            scanf("%d",&n);
            for( int i = 1; i <= n; i++)
            {
                scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
                p[i].id = i;
                maxz = max(maxz,p[i].z);
            }
            sort(p+1,p+1+n,cmp);
    
            mem(res,0);
            int cnt = 0;
            for( int i = n; i>= 1; i--)
            {
                if( p[i].x == p[i+1].x && p[i].y == p[i+1].y && p[i].z == p[i+1].z)
                    cnt++;
                else
                    cnt = 0;
                res[p[i].id] += cnt;
            }
            cdq(1,n);
            for( int i = 1; i <= n; i++)
                printf("%d\n",res[i]);
        }
    
        return 0;
    }

[Link 1]: http://acm.split.hdu.edu.cn/showproblem.php?pid=5618