bzoj3262: 陌上花开(cdq分治+树状数组)

3262: 陌上花开

题目：传送门

题解：

　　 %%%cdq分治

　　很强大的一个暴力...感觉比分块高级多了

　　这道题目就是一个十分经典的三维偏序的例题：

　　一维直接暴力排序x

　　二维用csq维护y

　　三维用树状数组来搞

　　最后ans处理答案，注意：全部值相等，相互之间也算自己更加漂亮

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 struct flower
 8 {
 9     int x,y,z,f,tot;
10 }a[210000],ba[210000];int n,m,len;
11 void ins(int x,int y,int z)
12 {
13     len++;
14     a[len].x=x;a[len].y=y;a[len].z=z;
15     a[len].tot=1;a[len].f=0;
16 }
17 bool cmp(flower n1,flower n2)
18 {
19     if(n1.x!=n2.x)return n1.x<n2.x;
20     if(n1.y!=n2.y)return n1.y<n2.y;
21     return n1.z<n2.z;
22 }
23 void qtt()
24 {
25     int x,y,z;
26     for(int i=1;i<=n;i++)
27         scanf("%d%d%d",&x,&y,&z),ins(x,y,z);
28     sort(a+1,a+len+1,cmp);
29     n=1;
30     for(int i=2;i<=len;i++)
31         if(a[n].x==a[i].x && a[n].y==a[i].y && a[n].z==a[i].z)
32             a[n].tot++;
33         else 
34             a[++n]=a[i];
35 }
36 
37 int s[210000];
38 int lowbit(int x){return x&-x;}
39 void add(int x,int k)
40 {
41     while(x<=m)
42     {
43         s[x]+=k;
44         x+=lowbit(x);
45     }
46 }
47 int getsum(int x)
48 {
49     int ans=0;
50     while(x)
51     {
52         ans+=s[x];
53         x-=lowbit(x);
54     }
55     return ans;
56 }
57 
58 void cdq(int l,int r)
59 {
60     if(l==r)return ;
61     int mid=(l+r)/2;
62     cdq(l,mid);cdq(mid+1,r);
63     
64     int i=l,j=mid+1,p=l;
65     while(i<=mid && j<=r)
66     {
67         if(a[i].y<=a[j].y)add(a[i].z,a[i].tot),ba[p++]=a[i++];
68         else a[j].f+=getsum(a[j].z),ba[p++]=a[j++];
69     }
70     while(i<=mid)add(a[i].z,a[i].tot),ba[p++]=a[i++];
71     while(j<=r)a[j].f+=getsum(a[j].z),ba[p++]=a[j++];
72     
73     for(int i=l;i<=mid;i++)add(a[i].z,-a[i].tot);
74     
75     for(int i=l;i<=r;i++)a[i]=ba[i];
76 }
77 int ans[110000];
78 int main()
79 {
80     scanf("%d%d",&n,&m);
81     qtt();
82     
83     memset(s,0,sizeof(s));
84     cdq(1,n);
85     
86     memset(ans,0,sizeof(ans));
87     for(int i=1;i<=n;i++)ans[a[i].f+a[i].tot-1]+=a[i].tot;
88     for(int i=0;i<len;i++)printf("%d
",ans[i]);
89     return 0;
90 }