首页 > 代码库 > 【树状数组】【权值分块】bzoj2352 Stars
【树状数组】【权值分块】bzoj2352 Stars
经典问题：二维偏序。给定平面中的n个点，求每个点左下方的点的个数。
因为 所有点已经以y为第一关键字，x为第二关键字排好序，所以我们按读入顺序处理，仅仅需要计算x坐标小于<=某个点的点有多少个就行。
这就是所说的：n维偏序，一维排序，二维树状数组，三维 分治 Or 树状数组套平衡树……
<法一>树状数组。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 using namespace std; 5 struct POINT 6 { 7 int x,y; 8 }; 9 int n,d[3200001],ji[1500001],m;10 POINT star[1500001];11 bool cmp(const POINT &a,const POINT &b)12 {13 if(a.x<b.x)14 return true;15 else if(a.x>b.x)16 return false;17 else if(a.y<b.y)18 return true;19 return false;20 }21 int lowbit(int x)22 {23 return x&(-x);24 }25 void update(int x,int delta)26 {27 for(;x<=m;x+=lowbit(x))28 d[x]+=delta;29 }30 int getsum(int x)31 {32 int res=0;33 for(;x>0;x-=lowbit(x))34 res+=d[x];35 return res;36 }37 int main()38 {39 scanf("%d",&n);40 for(int i=1;i<=n;i++)41 {42 scanf("%d%d",&star[i].x,&star[i].y);43 star[i].y++;44 m=max(m,star[i].y);45 }46 for(int i=1;i<=n;i++)47 {48 update(star[i].y,1);49 ji[getsum(star[i].y)-1]++;50 }51 for(int i=0;i<n;i++)52 printf("%d\n",ji[i]);53 return 0;54 }
<法二>权值分块。我会说比树状数组还快将近一倍？
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int n,x[15001],y[15001],LIMIT,r[200],l[200],num[33000],sumv[200],sz,sum,rank[33000],b[33000]; 6 void makeblock() 7 { 8 sz=(int)sqrt((double)LIMIT); if(!sz) sz=1; r[0]=-1; 9 for(sum=1;sum*sz<LIMIT;sum++)10 {11 l[sum]=r[sum-1]+1;12 r[sum]=sum*sz;13 for(int i=l[sum];i<=r[sum];i++) num[i]=sum;14 }15 l[sum]=r[sum-1]+1;16 r[sum]=LIMIT;17 for(int i=l[sum];i<=r[sum];i++) num[i]=sum;18 }19 int query(const int &V)20 {21 int cnt=0;22 for(int i=1;i<num[V];i++) cnt+=sumv[i];23 for(int i=l[num[V]];i<=V;i++) cnt+=b[i];24 ++b[V]; ++sumv[num[V]];25 return cnt;26 }27 int main()28 {29 scanf("%d",&n);30 for(int i=1;i<=n;i++)31 {32 scanf("%d%d",&x[i],&y[i]);33 LIMIT=max(LIMIT,x[i]);34 } makeblock();35 for(int i=1;i<=n;i++) ++rank[query(x[i])];36 for(int i=0;i<n;i++) printf("%d\n",rank[i]);37 return 0;38 }
【树状数组】【权值分块】bzoj2352 Stars
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。