P3810 【模板】三维偏序(陌上花开)

    • 1K通过
    • 2.3K提交
  • 题目提供者 zcysky 管理员
  • 评测方式 云端评测
  • 标签 K-D Tree cdq分治 分治 树状数组 概率论,统计 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    这是一道模板题

    可以使用bitset,CDQ分治,K-DTree等方式解决。

    题目描述

    有 $ n $ 个元素,第 $ i $ 个元素有 $ a_i $ 、 $ b_i $ 、 $ c_i $ 三个属性,设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 的 $ j $ 的数量。

    对于 $ d \in [0, n) $ ,求 $ f(i) = d $ 的数量

    输入输出格式

    输入格式:

    第一行两个整数 $ n $ 、 $ k $ ,分别表示元素数量和最大属性值。

    之后 $ n $ 行,每行三个整数 $ a_i $ 、 $ b_i $ 、 $ c_i $ ,分别表示三个属性值。

    输出格式:

    输出 $ n $ 行,第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。

    输入输出样例

    输入样例#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
    输出样例#1: 复制
    3
    1
    3
    0
    1
    0
    1
    0
    0
    1

    说明

    $ 1 \leq n \leq 100000, 1 \leq k \leq 200000 $

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。