正文 

当前位置： 首页 > java > java教程

陌上花开

蒟蒻ZJO:-) 蒟蒻ZJO:-)     2022-08-26     679

关键词：

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

 

 

三维偏序，第一维排序，然后第二维用ＣＤＱ分治：
算法流程：
先从中间二分，把左边和右边分别按第二维排序，
这时第二维是有序的了，第一维并不是有序的，但左区间的都会比右区间的小，
这时就可以搞两个指针分别指向这两个区间，并且第三维用树状数组维护，
这样乱搞一下可以维护三维偏序。
 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define maxn 200010
15 using namespace std;
16 struct data{
17   int a,b,c,lev,num;
18 }f[maxn];
19 int co[maxn],tree[maxn],LOL=0,ans[maxn];
20 int lowbit(int x){return x&(-x);} 
21 bool cmp1(const data &a,const data &b){
22   if(a.a!=b.a) return a.a<b.a;
23   else{
24     if(a.b!=b.b) return a.b<b.b;
25     else return a.c<b.c;
26   }
27 }
28 bool cmp2(const data &a,const data &b){
29   if(a.b!=b.b) return a.b<b.b;
30   else return a.c<b.c;
31 }
32 void add(int p,int v){
33   for(int i=p;i<maxn;i+=lowbit(i)){
34     if(co[i]!=LOL) tree[i]=0;
35     co[i]=LOL;
36     tree[i]+=v;
37   }
38 }
39 int find(int p){
40   int ret=0;
41   for(int i=p;i;i-=lowbit(i))
42     if(co[i]==LOL)
43       ret+=tree[i];
44   return ret;
45 }
46 void QAQ(int l,int r){
47   if(l==r) return;
48   int mid=(l+r)>>1;
49   QAQ(l,mid),QAQ(mid+1,r);
50   sort(f+l,f+mid+1,cmp2);
51   sort(f+mid+1,f+r+1,cmp2);
52   LOL++;
53   for(int j=mid+1,i=l;j<=r;j++){
54     for(;f[i].b<=f[j].b&&i<=mid;i++)
55       add(f[i].c,f[i].num);
56     f[j].lev+=find(f[j].c);
57   }
58 }
59 int main()
60 {
61   freopen("!.in","r",stdin);
62   freopen("!.out","w",stdout);
63   int n,m,tot=0;
64   scanf("%d%d",&n,&m);
65   for(int i=1;i<=n;i++)
66     scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c),f[i].num++;
67   sort(f+1,f+n+1,cmp1);
68   for(int i=1;i<=n;i++){
69     if(i!=1 && f[i-1].a==f[i].a && f[i-1].b==f[i].b && f[i-1].c==f[i].c) f[tot].num++;
70     else f[++tot].a=f[i].a,f[tot].b=f[i].b,f[tot].c=f[i].c,f[tot].lev=f[i].lev,f[tot].num=f[i].num;
71   }
72   QAQ(1,tot);
73   for(int i=1;i<=tot;i++)
74     ans[f[i].lev+f[i].num-1]+=f[i].num;
75   for(int i=0;i<n;i++)
76     printf("%d
",ans[i]);
77   return 0;
78 }


 


 






世界名画|陌上花开，可缓缓归矣


  查看详情  

                

陌上花开


P2433-【BZOJ3262三维偏序】陌上花开Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且...  查看详情  

                

[bzoj3262]陌上花开


3262:陌上花开TimeLimit:20Sec  MemoryLimit:256MBSubmit:2497  Solved:1115[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能...  查看详情  

                

bzoj3262陌上花开cdq分治


3262:陌上花开TimeLimit: 20Sec  MemoryLimit: 256MBSubmit: 2794  Solved: 1250[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的  查看详情  

                

bzoj3262:陌上花开


//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include<vector>#definemid(  查看详情  

                

bzoj3262陌上花开


题解：裸cdq分治一开始处理相同花的时候搞错了，WA了几发#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintmaxn=200009;intn,m;intb[maxn],nn;intfsiz;intans[max  查看详情  

                

陌上花开


灼灼桃花十里，取一朵放在心上，足矣。在颠簸的车上，在遥远的路上，思念的人儿远不可及。或许人在这里，可是心，早已经飞到了天上，飞到花前，飞到你的身边。“等了好久，终于有信号了，现在月亮好圆，星星好多...  查看详情  

                

bzoj3262:陌上花开--cdq分治


3262:陌上花开TimeLimit: 20Sec  MemoryLimit: 256MBDescription有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另...  查看详情  

                

bzoj3262陌上花开（cdq分治）


【BZOJ3262】陌上花开（CDQ分治）题解原来放过这道题目，题面在这里树套树的做法也请点上面这回用CDQ分治做的其实也很简单，对于第一维排序之后显然只有前面的对后面的才会产生贡献那么，使用CDQ分治先分，每次递归子问题...  查看详情  

                

bzoj3262陌上花开


好文艺的题目。自己犯的**错误不想再提了，特别注意这题要求三个都相等时也计入统计，所以就特别处理一下。裸的三位偏序，CDQ+树状数组By：大奕哥1#include<bits/stdc++.h>2usingnamespacestd;3constintN=200005;4constintM=400005;5intn,k,tim,ans...  查看详情  

                

「bzoj」「3262」陌上花开


CDQ分治　　WA：在solve时，对y、z排序以后，没有处理「y、z相同」的情况，也就是说可能（1，2，3）这个点被放到了（2，2，3）的后面，也就是统计答案在前，插入该点在后……也就没有统计到！　　sad1#include<cstdio>2...  查看详情  

                

bzoj3262陌上花开cdq分治


#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=100005,K=200005;intn,k,tot,t[K],ans[N];structqwe{intx,y,z,con,ans;}a[N];boolcmp1(constqwe&a,const  查看详情  

                

[bzoj3262]陌上花开分治


题意　　给定三个序列$S=left{s_1,s_2,...,s_n
ight}$,$C=left{c_1,c_2,...,c_n
ight}$,$M=left{m_1,m_2,...,m_n
ight}$.　　对任意$i$,求$level_i=sum_{j
ei,1lejlen}[s_iges_j][c_igec_j][m_igem_j]$. 分析　  查看详情  

                

bzoj3262陌上花开


传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3262【题解】cdq分治。这题是三维偏序问题。我们先对整体排序，合并相同的，记原来的n为N，剩下的个数为n。然后对于b排序，把a重新编号为1...ncdq分治的时候呢，我们定义过程solve(l...  查看详情  

                

bzoj3262陌上花开cdq+树状数组


【bzoj3262】陌上花开Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca&g...  查看详情  

                

陌上花开（bzoj3262）


Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然...  查看详情  

                

p2433-bzoj3262三维偏序陌上花开------三维偏序


P2433-【BZOJ3262三维偏序】陌上花开Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且...  查看详情  

                

（三维偏序）陌上花开(代码片段)


传送门CDQ分治是一个神奇的东西……说实话我觉得看它的讲义我是真的看不懂。感觉好像分治类的算法都这样，就是讲义讲不明白，得多做题才能慢慢理解。毕竟因为分治的题主要是不知道怎么实现……得具体题目具体分析。CDQ...  查看详情