【BZOJ3262】陌上花开 (CDQ分治+树状数组+排序)

Time Limit: 3000 ms   Memory Limit: 256 MB

Description

  有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。

  现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。

  定义一朵花A比另一朵花B要美丽,当且仅当 $S_a \ge S_b, C_a \ge C_b, M_a \ge M_b$。

  显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

  第一行为 N,K 分别表示花的数量和最大属性值。
  以下 N 行,每行三个整数 $s_i , c_i , m_i$  表示第i朵花的属性。

Output

  包含 $N$ 行,分别表示评级为 $0…N−1$ 的每级花的数量。


Sample Input

Sample Output

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
3
1
3
0
1
0
1
0
0
1


题解

  题目大意为,给定n个三元组,每个三元组的等级为小于等于它的三元组的个数。

    其中“小于”定义为:对于两个三元组$A(s1,c1,m1)$与$B(s2,c2,m2)$,$A \le B$当且仅当$s_1 \le s_2$且$c_1 \le c_2$

且$m_1 \le b_2$。

   

  隐隐约约想到单调性的问题。

  1. 对于$s$,我们直接排序处理(按照$s$第一,$c$第二,$m$第三的优先级排序);

  2. 对于$c$,开始使用CDQ分治瞎搞(其中每次回溯的时候分别对左右区间,以$c$为第一关键字排序,为计算左区间对右区间的贡献作准备);  

  3. 对于$m$:我们在CDQ分治时,已经确定左半边区间的$s$是小于右半边区间的;这时采用双指针扫描,以右区间指针指向的三元组为基准三元组。考虑此时 $c$ 是递增的,我们就将左区间的指针移到最靠右的三元组,使得这个三元组的$c$值不超过基准三元组的$c$值;

    其中,我们一边扫描左区间一边将左区间扫过的三元组的$m$值丢进树状数组里,左指针到基准时,直接询问树状数组内小于等于与基准三元组的$m$值。

  

  完全相同的几朵花怎么办? 我们按照上面提到的排序方法排序所有花,对于相同的花,将它们的等级都标记为相同花的中等级最高的即可。

  


 #include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+,K=2e5+;
int n,k,ans[N];
struct Flower{int s,c,m,sum;}f[N];
struct Bit{
int arr[K],lis[N],cnt;
void reset(){
for(;cnt;cnt--) add(lis[cnt],-,);
}
void add(int u,int num,int flag){
if(!u) return;
if(!flag)
lis[++cnt]=u;
for(;u<=k;u+=u&-u) arr[u]+=num;
}
int que(int u){
int ret=;
for(;u;u-=u&-u) ret+=arr[u];
return ret;
}
}bit;
bool cmpAll(Flower x,Flower y){
if(x.s!=y.s) return x.s<y.s;
if(x.c!=y.c) return x.c<y.c;
return x.m<y.m;
}
bool cmpC(Flower x,Flower y){return x.c<y.c;}
void cdq(int l,int r){
if(l==r) return;
int mid=(l+r)/;
cdq(l,mid);
cdq(mid+,r);
sort(f+l,f+mid+,cmpC);
sort(f+mid+,f+r+,cmpC);
int i=l,j;
bit.reset();
for(i=l,j=mid+;j<=r;j++){
while(i<=mid&&f[i].c<=f[j].c){
bit.add(f[i].m,,);
i++;
}
f[j].sum+=bit.que(f[j].m);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d%d%d",&f[i].s,&f[i].c,&f[i].m);
sort(f+,f++n,cmpAll);
cdq(,n);
sort(f+,f++n,cmpAll);
for(int i=;i<=n;){
int j=i,maxs=;
while(f[i].s==f[j].s&&f[i].c==f[j].c&&f[i].m==f[j].m){
maxs=max(maxs,f[j].sum);
j++;
}
ans[maxs]+=j-i;
i=j;
}
for(int i=;i<=n-;i++)
printf("%d\n",ans[i]);
return ;
}

神奇代码

上一篇:关于JDBC链接数据库的代码实现


下一篇:极客DIY:制作一个可以面部、自主规划路径及语音识别的无人机