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

範例輸出 #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

提示：

對於100%的測資 $1 \leq n \leq 10^5$ ， $1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5$ 。

由於出題者太笨debug不出來，所以搬來這邊繼續debug，除非你分治超強，不然請跳過這題

標籤:

出處:

bzoj 洛谷 [管理者：

211096@stu.c... (唐狗針)

]

編號	身分	題目	主題	人氣	發表日期
147	pusapphire@g... (pusapphire)	a541	題解 / 卡70%	44	2024-11-22 00:19