首页 > 代码库 > hdu_5618_Jam's problem again(cdq分治+lowbit)
hdu_5618_Jam's problem again(cdq分治+lowbit)
题目链接:hdu_5618_Jam‘s problem again
题意:
给你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\n",a[i].cnt); 55 } 56 return 0; 57 }
hdu_5618_Jam's problem again(cdq分治+lowbit)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。