前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BZOJ3262: 陌上花开(cdq分治)

BZOJ3262: 陌上花开(cdq分治)

作者头像
attack
发布2018-07-27 15:13:22
4830
发布2018-07-27 15:13:22
举报
文章被收录于专栏:数据结构与算法

Time Limit: 20 Sec  Memory Limit: 256 MB

Submit: 3627  Solved: 1705

[Submit][Status][Discuss]

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

Source

感觉cdq分治和归并排序很像qwq。

第一维可以用排序搞掉

这样我们用cdq分治统计$(l,r)$这段区间的时候只需要考虑$b$和$c$的贡献,而且只需要考虑区间$(l, mid)$对$mid + 1, r$的贡献

用树状数组维护第三维的贡献

代码语言:javascript
复制
#include<cstdio>
#include<algorithm>
#define lowbit(x) ((x) & (-x))
using namespace std;
const int MAXN = 200001;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, Max;
struct Node {
    int a, b, c, f, w;
    bool operator < (const Node &rhs) const{
        return (a == rhs.a && b == rhs.b) ? (c < rhs.c) : (a == rhs.a ? b < rhs.b : a < rhs.a);
    }
}A[MAXN], tp[MAXN];
int num = 0, ans[MAXN];
int T[MAXN];
void Add(int pos, int val) {
    for(int i = pos; i <= Max; i += lowbit(i)) T[i] += val;
}
int Query(int pos) {
    int ans = 0;
    for(int i = pos; i; i -= lowbit(i)) ans += T[i];
    return ans;
}
void CDQ(int l, int r) {
    if(l == r) return;
    int mid = l + r >> 1;
    CDQ(l, mid); CDQ(mid + 1, r);
    int i = l, j = mid + 1, P = l;
    while(i <= mid || j <= r) {
        if(j > r || (i <= mid && A[i].b <= A[j].b)) Add(A[i].c, A[i].w), tp[P++] = A[i++];
        else A[j].f += Query(A[j].c), tp[P++] = A[j++];
    }
    for(int i = l; i <= mid; i++) Add(A[i].c, -A[i].w);
    for(int i = l; i <= r; i++) A[i] = tp[i];
}
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    N = read(); Max = read();
    for(int i = 1; i <= N; i++) A[i].a = read(), A[i].b = read(), A[i].c = read(), A[i].w = 1;
    sort(A + 1, A + N + 1);
    num = 1;
    for(int i = 2; i <= N; i++)
        if(A[i].a == A[num].a && A[i].b == A[num].b && A[i].c == A[num].c) A[num].w++;
        else A[++num] = A[i];
    CDQ(1, num);
    for(int i = 1; i <= num; i++) ans[A[i].f + A[i].w - 1] += A[i].w;
    for(int i = 0; i <= N - 1; i++)
        printf("%d\n", ans[i]);
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-07-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档