a541:
[模板] 三維偏序 / 陌上花開
內容
題目背景
陌上花開，可緩緩歸矣 ——吳越王
翻譯：田間阡陌上的花開了，你可以一邊賞花，一邊慢慢回來。
隱意：春天都到了，你怎麼還沒有回來。形容吳越王期盼夫人早日歸來的急切心情。
Ask：那麼這和這題有什麼關係呢？
Answer：並沒有什麼關係，增強國文水平而已，現在來看一道題目：陌上花開。這就有關係了吧。
題目描述
有 $ 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 \ne 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
測資資訊：
記憶體限制：
128
MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (6%): 1.0s , <1M
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 2.0s , <10M
公開 測資點#5 (6%): 2.0s , <10M
公開 測資點#6 (6%): 2.0s , <10M
公開 測資點#7 (6%): 2.0s , <10M
公開 測資點#8 (6%): 2.0s , <10M
公開 測資點#9 (6%): 2.0s , <10M
公開 測資點#10 (6%): 2.0s , <1M
公開 測資點#11 (6%): 2.0s , <10M
公開 測資點#12 (6%): 2.0s , <10M
公開 測資點#13 (6%): 2.0s , <1M
公開 測資點#14 (6%): 2.0s , <1M
公開 測資點#15 (6%): 2.0s , <1M
公開 測資點#16 (6%): 2.0s , <1M
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (6%): 1.0s , <1M
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 2.0s , <10M
公開 測資點#5 (6%): 2.0s , <10M
公開 測資點#6 (6%): 2.0s , <10M
公開 測資點#7 (6%): 2.0s , <10M
公開 測資點#8 (6%): 2.0s , <10M
公開 測資點#9 (6%): 2.0s , <10M
公開 測資點#10 (6%): 2.0s , <1M
公開 測資點#11 (6%): 2.0s , <10M
公開 測資點#12 (6%): 2.0s , <10M
公開 測資點#13 (6%): 2.0s , <1M
公開 測資點#14 (6%): 2.0s , <1M
公開 測資點#15 (6%): 2.0s , <1M
公開 測資點#16 (6%): 2.0s , <1M
提示 ：
對於100%的測資$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。
由於出題者太笨debug不出來，所以搬來這邊繼續debug，除非你分治超強，不然請跳過這題
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 147 | a541 | 46 | 2024-11-22 00:19 |