标签：分治 树状数组 output ++ EDA mes bsp rip pre
Description
有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1
以下N行，每行三个整数si, ci, mi (1
Output
包含N行，分别表示评级为0...N-1的每级花的数量。
Sample Input
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
Sample Output
3
1
3
0
1
0
1
0
0
1
题解
- 这显然就是个三维偏序问题
- 就先排序，cdq套树状数组就好了
代码
1 #include 2 #include 3 #include 4 #include
5 using namespace std;
6 const int N=200001;
7 struct node{ int x,y,z,id; }a[N];
8 int c[N2],k,n,b[N],bj[N],f[N];
9 int lowbit(int x){ return x&(-x); }
10 void add(int x,int v){ while(xlowbit(x); }
11 int sum(int x)
12 {
13 int ans=0;
14 while (x) ans+=c[x],x-=lowbit(x);
15 return ans;
16 }
17 bool cmp1(const node &a,const node &b)
18 {
19 if (a.x!=b.x) return a.xb.x;
20 if (a.y!=b.y) return a.yb.y;
21 return a.zb.z;
22 }
23 bool cmp2(const node &a,const node &b)
24 {
25 if (a.y!=b.y) return a.yb.y;
26 if (a.z!=b.z) return a.zb.z;
27 return a.xb.x;
28 }
29 void cdq(int l,int r)
30 {
31 if (l==r) return;
32 int mid=(l+r)>>1,flag;
33 cdq(l,mid),cdq(mid+1,r);
34 sort(a+l,a+r+1,cmp2);
35 for (int i=l;i1),flag=i:b[a[i].id]+=sum(a[i].z);
36 for (int i=l;iif (a[i].x1);
37 }
38 int main()
39 {
40 scanf("%d%d",&n,&k);
41 for (int i=1;i"%d%d%d",&a[i].x,&a[i].y,&a[i].z),a[i].id=i;
42 sort(a+1,a+1+n,cmp1);
43 for (int i=1;in;)
44 {
45 int j=i+1;
46 while (j;
47 while (i1].id,i++;
48 }
49 for(int i=1;ii;
50 cdq(1,n);
51 for(int i=1;i;
52 for(int i=0;i"%d\n",f[i]);
53 }
[cdq分治][树状数组] Bzoj P3262 陌上花开
标签：分治 树状数组 output ++ EDA mes bsp rip pre
原文地址：https://www.cnblogs.com/Comfortable/p/11145822.html