【bzoj3262】陌上花开 CDQ分治+树状数组

时间:2022-05-18 03:30:44

题目描述

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

输入

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

输出

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

样例输入

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


题解

CDQ分治+树状数组

先将第一维排序,直接干掉第一维,然后第二维使用CDQ分治。

按照CDQ分治的思(tao)路,将所求区间[l,r]化为两个子区间[l,mid]和[mid+1,r],先处理左边,再处理右边,最后处理左边对右边的影响。

将[l,mid]和[mid+1,r]按照第二维排序,然后寻找左区间左端和右区间左端的y值哪个小。如果左边小(包括等于),就把左边的第三维加到树状数组中,左区间左端+1;否则查询第三维以下的个数加入答案中,右区间左端+1,最后再在树状数组中减回去(CDQ分治绝对不能使用memset!)。

因为本题是对区间的处理,所以我使用了归并排序,亲测快排时间是这个的3倍左右。

排序会改变次序,所以需要使用结构体储存num。

然后由每个元素的num得到num为某值的个数即可。

由于题目中可能存在三维都相同的两个元素,所以必须先去重,统计个数;计算答案时要把这些相同的也算在内。

#include <cstdio>
#include <algorithm>
using namespace std;
struct data
{
int x , y , z , num , cnt;
}a[100010] , v[100010] , tmp[100010];
int n , k , tot , f[200010] , ans[100010];
bool cmp(data a , data b)
{
return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x;
}
void update(int x , int a)
{
int i;
for(i = x ; i <= k ; i += i & -i) f[i] += a;
}
int query(int x)
{
int i , ans = 0;
for(i = x ; i ; i -= i & -i) ans += f[i];
return ans;
}
void solve(int l , int r)
{
if(l == r) return;
int mid = (l + r) >> 1 , i = l , j = mid + 1 , p = l;
solve(l , mid) , solve(mid + 1 , r);
while(i <= mid || j <= r)
{
if(i <= mid && (j > r || v[i].y <= v[j].y)) tmp[p ++ ] = v[i] , update(v[i].z , v[i].cnt) , i ++ ;
else tmp[p] = v[j] , tmp[p ++ ].num += query(v[j].z) , j ++ ;
}
for(i = l ; i <= mid ; i ++ ) update(v[i].z , -v[i].cnt);
for(i = l ; i <= r ; i ++ ) v[i] = tmp[i];
}
int main()
{
int i;
scanf("%d%d" , &n , &k);
for(i = 1 ; i <= n ; i ++ ) scanf("%d%d%d" , &a[i].x , &a[i].y , &a[i].z);
sort(a + 1 , a + n + 1 , cmp);
for(i = 1 ; i <= n ; i ++ )
{
if(a[i].x != a[i - 1].x || a[i].y != a[i - 1].y || a[i].z != a[i - 1].z) v[++tot] = a[i];
v[tot].cnt ++ ;
}
solve(1 , tot);
for(i = 1 ; i <= tot ; i ++ ) ans[v[i].num + v[i].cnt - 1] += v[i].cnt;
for(i = 0 ; i < n ; i ++ ) printf("%d\n" , ans[i]);
return 0;
}