hdu_5618_Jam's problem again(cdq分治+lowbit)

题意：

给你n个点，每个点有一个坐标(x,y,z)，找出有ans个点，3个坐标都比该点小，这个点的level就为ans,然后让你输出所有点的ans.

题解：

对于第一维，直接排序，后面两维的处理可以用线段树套lowbit，但空间用的很大，这里满足运用cdq分治的条件，所有用cdq分治套lowbit，常数很小。

注意相同点的处理。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 
 5 const int N=1e5+7;
 6 int t,n,sum[N];
 7 
 8 struct node
 9 {
10     int x,y,z,cnt,id;
11     bool operator < (const node &b)const
12     {
13         if(x==b.x&&y==b.y)return z<b.z;
14         if(x==b.x)return y<b.y;
15         return x<b.x;
16     }
17     bool operator == (const node &b)const{return x==b.x&&y==b.y&&z==b.z;}
18 }a[N],b[N];
19 
20 bool cmp(node a,node b){return a.id<b.id;}
21 
22 inline void add(int x,int c){while(x<N)sum[x]+=c,x+=x&-x;}
23 inline  int ask(int x){int an=0;while(x)an+=sum[x],x-=x&-x;return an;}
24 
25 void solve(int l,int r)
26 {
27     if(l==r)return;
28     int mid=l+r>>1;
29     solve(l,mid),solve(mid+1,r);
30     for(int i=l,j=l,k=mid+1;i<=r;i++)
31     {
32         if((a[j].y<=a[k].y||r<k)&&j<=mid)b[i]=a[j++],add(b[i].z,1);
33         else b[i]=a[k++],b[i].cnt+=ask(b[i].z);
34     }//当左半边的y大于当前右半边的y时，先将这个点更新了，这样就保证了前面的y都是比这个点小
35     F(i,l,mid)add(a[i].z,-1),a[i]=b[i];
36     F(i,mid+1,r)a[i]=b[i];
37 }
38 
39 int main()
40 {
41     scanf("%d",&t);
42     while(t--)
43     {
44         scanf("%d",&n);
45         F(i,1,n)
46         {
47             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
48             a[i].id=i,a[i].cnt=0;
49         }
50         sort(a+1,a+1+n);
51         for(int i=n-1;i>0;i--)if(a[i]==a[i+1])a[i].cnt=a[i+1].cnt+1;
52         solve(1,n);
53         sort(a+1,a+1+n,cmp);
54         F(i,1,n)printf("%d
",a[i].cnt);
55     }
56     return 0;
57 }

View Code