首页 > 代码库 > P2433 - 【BZOJ 3262三维偏序】陌上花开------三维偏序

P2433 - 【BZOJ 3262三维偏序】陌上花开------三维偏序

P2433 - 【BZOJ 3262三维偏序】陌上花开

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

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

Hint

数据范围:
1 <= N <= 100,000, 1 <= K <= 200,000

Source

CDQ分治,树套树

AC通道

 

第一道三维偏序题,CDQ分治。(一维排序,二维CDQ分治,三维树状数组维护)

暴力做法,暴力直接枚(然而我第一次超时并且WA了,0分),正解:具体做法为:(设权值为a,b,c)

  1 : 按关键字a从小到大排序,然后去重,放入一个新的结构体

  2 : 用CDQ分治,每次划分一半区间,一直到 l==r return;然后把左右区间都重新按b排序,计算右边的每个点的答案,(此时左区间的a肯定 <= 右区间的a,左区间的b由于排序,设立两个指针i(左区间),j(右区间),i从第一位枚举,枚举所有的左区间元素,如果当前左区间的b<j指针指向的右区间的元素的<b,则把i的c以权值为下标加入树状数组里,直到不满足条件停止枚举,计算j元素的ans);右区间全部算完后在把之前加的清零,这样一定能把所有的情况都枚举到(自己模拟一遍即可),保证了答案的正确性)

 3:最后Ans[f[i].ans+f[i].s-1]+=f[i].s;因为有相同的,所以需记录一下个数。。。。。。

第一次交CDQWA了,原因是树状数组的上界写错了,应该是读进来的k而不是n,这点需注意!!

 

技术分享
 1 #define ll long long
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<iomanip>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<ctime>
10 #include<cmath>
11 #include<stack>
12 #include<map>
13 #include<set>
14 #define lowbit(p) p&(-p)
15 using namespace std;
16 const int N=100010;
17 struct node{
18     int a,b,c,s,ans; //  s  相同的个数  ans 它的答案 魅力值 
19 }a[N],f[N];
20 int n,k;
21 bool comp(const node &x,const node &y) {
22     if(x.a==y.a&&x.b==y.b) return x.c<y.c;
23     if(x.a==y.a) return x.b<y.b;
24     return x.a<y.a;
25 }
26 int gi() {
27     int res=0,f=1;
28     char ch=getchar();
29     while((ch<0||ch>9)&&ch!=-) ch=getchar();
30     if(ch==-) ch=getchar(),f=-1;
31     while(ch>=0&&ch<=9) res=res*10+ch-0,ch=getchar();
32     return res*f;
33 }
34 int Ans[N],C[N*2];
35 void add(int p,int x) {
36     while(p<=k) C[p]+=x,p+=lowbit(p);//  边界值!!!   not p<=n
37 }
38 int getsum(int p) { 
39     int sum=0;
40     while(p) sum+=C[p],p-=lowbit(p);
41     return sum;
42 }
43 bool comp2(const node&x,const node&y) {
44     if(x.b==y.b) return x.c<y.c;
45     return x.b<y.b;
46 }
47 void CDQ(int l,int r) {
48     if(l==r) return;
49     int mid=(l+r)>>1;
50     CDQ(l,mid);
51     CDQ(mid+1,r);
52     sort(f+l,f+mid+1,comp2);
53     sort(f+mid+1,f+r+1,comp2);
54     int i=l,j=mid+1;
55     while(j<=r) {
56         while(i<=mid&&f[i].b<=f[j].b) {
57             add(f[i].c,f[i].s);
58             i++;
59         }
60         f[j].ans+=getsum(f[j].c);
61         j++;
62     }
63     for(int k=l;k<i;k++) add(f[k].c,-f[k].s);//  还原 
64 }
65 int main() {
66     freopen("Alan.in","r",stdin);
67     freopen("Alan.out","w",stdout);
68     int nn=gi();k=gi();
69     for(int i=1;i<=nn;i++) a[i].a=gi(),a[i].b=gi(),a[i].c=gi();
70     sort(a+1,a+nn+1,comp);
71     int cnt=0;
72     for(int i=1;i<=nn;i++) {//  去重 
73         cnt++;
74         if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c) {
75             f[++n]=a[i];
76             f[n].s=cnt;
77             cnt=0;
78         }
79     }
80     CDQ(1,n);
81     for(int i=1;i<=n;i++) {
82         Ans[f[i].ans+f[i].s-1]+=f[i].s;//  f[i].s-1,the same with me
83     }
84     for(int i=0;i<nn;i++) printf("%d\n",Ans[i]);
85     return 0;
86 }
View Code

 

 

P2433 - 【BZOJ 3262三维偏序】陌上花开------三维偏序