NEU 1704 三维偏序（CDQ分治+树状数组）

1702: 撩妹全靠魅力值

时间限制: 10 Sec   内存限制: 128 MB
提交: 164   解决: 28
[ 提交][ 状态][ 讨论版]

题目描述

我们永远都要相信，世界是美好的，这不是一个看脸的社会。一个人的魅力主要体现在三个方面， 一方面是颜值，颜值虽然可以在很多方面让我们感受到不一样的快乐，但是它是决定不了一个人魅力；另一方面 是内涵，内涵对于一个人魅力的提升有着巨大的作用，比如高晓松啊，黄渤啊，对吧。还有一方面是智慧，一个 人的智慧值越高，那么他在未来的道路上会在一定程度上走的更平坦一些。一个人的魅力值是相对于周围人来说的，如果他的颜值，内涵和智慧值同时不低于另外一个人，那么他的魅力值就会加1，给你一些人的颜值，内涵，和智慧值，请输出这些人的魅力值。

输入

测试样例T（T<=10） 输入的人的数量n(n<=100000) 接下来n行每行三个数个数 表示这个人的颜值，内涵，智慧值（1~100000）。

输出

每个人的魅力值。

样例输入

1
4
10 4 7
10 6 6
8 2 5
7 3 10

样例输出

1
1
0
0

        经典的三维偏序问题，cdq分治同样也是经典的做法。

        不考虑这种方法的话，我们可以先对所有的数字按照x坐标排序，然后按顺序把另外两个坐标添加进二维树状数组里面，每次查询它前面的数字个数即可。然而这里总共有100000个数字，开二维树状数组即使在离散化的情况下，也会爆内存，于是貌似只能用CDQ分治。

        首先当然的，对x进行排序，然后为了分治的方便，就直接把x坐标离散化。然后直接进入分治，由于这题的cdq分治在单位区间的时候不需要进行什么修改，所以我们大可以先分治两个小部分，再处理大的区间。对于大区间，首先处理两个小区间，同时把数据按照yzx的顺序归并排序，然后从头开始依次进行插入和计算。对于x小于等于mid的点，我们把它的z坐标加入一维树状数组中，然后对于x大于mid的点，我们则统计小于等于其z坐标的点的个数。这样一来由于加入树状数组的点的x坐标都小于等于mid，而统计的点的x大于mid，x满足偏序，有由于按照了y来排序，所以y也满足偏序，故树状数组只需要一维即可统计出其偏序。

        利用cdq分治消除了x的影响，利用排序解决了y的影响，然后用树状数组统计z的个数，非常巧妙的解决了二维树状数组的空间问题。也深刻体现了cdq分治这种利用前半区间的去更新后半区间的思想。然后在实际操作中，要特别注意相等的情况，具体做法是设置一个same数组，对于相同的点我们取其最后一个数字的偏序数。具体见代码：

#include<bits/stdc++.h>
#define N 100010

using namespace std;

struct node{int x,y,z,id;} p[N],tmp[N];
int n,ans[N],same[N];

struct BinaryIndexedTree
{
	int c[N];

	inline int lowbit(int x)
	{
		return x&-x;
	}

	inline void update(int x,int k)
	{
		while (x<N)
		{
			c[x]+=k;
			x+=lowbit(x);
		}
	}

	void clear(int x)
	{
		while (x<N)
		{
			c[x]=0;
			x+=lowbit(x);
		}
	}
	inline int getsum(int x)
	{
		int ans=0;
		while (x>0)
		{
			ans+=c[x];
			x-=lowbit(x);
		}
		return ans;
	}
} BIT;

bool xyz(node a,node b)
{
    if (a.x!=b.x) return a.x<b.x;
    return a.y==b.y?a.z<b.z:a.y<b.y;
}

bool yzx(node a,node b)
{
    if (a.y!=b.y) return a.y<b.y;
    return a.z==b.z?a.x<b.x:a.z<b.z;
}

bool id(node a,node b)
{
    return a.id<b.id;
}

bool operator == (node a,node b)
{
    return a.x==b.x&&a.y==b.y&&a.z==b.z;
}

void cdq(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int p1=l,p2=mid+1,pp=l;
    while(p1<=mid&&p2<=r)							//归并排序的同时根据y来进行更新或者统计
    {
        if (yzx(p[p1],p[p2]))
        {
            if (p[p1].x<=mid) BIT.update(p[p1].z,1);				//如果是前半部分那么更新
            tmp[pp++]=p[p1++];
        } else
        {
            if (p[p2].x>mid)							//后半部分则是统计
                ans[p[p2].id]+=BIT.getsum(p[p2].z);
            tmp[pp++]=p[p2++];
        }
    }
    while(p1<=mid) tmp[pp++]=p[p1++];
    while(p2<=r)
    {
        if (p[p2].x>mid)
            ans[p[p2].id]+=BIT.getsum(p[p2].z);
        tmp[pp++]=p[p2++];
    }
    for(int i=l;i<=r;i++)
    {
        p[i]=tmp[i];
        if (p[i].x<=mid) BIT.clear(p[i].z);					//别忘了恢复树状数组
    }
}

int main()
{
    int T_T;
    cin>>T_T;
    while(T_T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            p[i]=node{x,y,z,i};
        }
        sort(p,p+n,xyz);
        memset(ans,0,sizeof(ans));
        for(int i=0,j;i<n;)
        {
            for (j=i+1;j<n&&p[j]==p[i];j++);
            for(;i<j;i++) same[p[i].id]=p[j-1].id;
        }
        for(int i=0;i<n;i++) p[i].x=i;
        cdq(0,n-1);
        sort(p,p+n,id);
        for(int i=0;i<n;i++)
            printf("%d\n",ans[same[i]]);
    }
    return 0;
}