{"problem":{"name":"[PA 2021] Areny","description":{"content":"Bajtek 在圣诞节收到了父母送的最新电脑游戏 Byte Defence 4。他兴致勃勃地打开游戏开始玩。游戏里操控的角色叫 Bajtonator，需要通过打怪、完成任务和升级装备来变强。地图上有 $n$ 个特殊的竞技场，里面有很稀有的掉落品。但有 $n$ 种通行证，想进某个竞技场必须持有对应的通行证。 这个游戏的规则如下： 1. 如果你有某个竞技场的通行证，就可以进入该竞技场与怪物战斗。进","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9052"},"statements":[{"statement_type":"Markdown","content":"Bajtek 在圣诞节收到了父母送的最新电脑游戏 Byte Defence 4。他兴致勃勃地打开游戏开始玩。游戏里操控的角色叫 Bajtonator，需要通过打怪、完成任务和升级装备来变强。地图上有 $n$ 个特殊的竞技场，里面有很稀有的掉落品。但有 $n$ 种通行证，想进某个竞技场必须持有对应的通行证。\n\n这个游戏的规则如下：\n\n1. 如果你有某个竞技场的通行证，就可以进入该竞技场与怪物战斗。进入竞技场不会消耗通行证，怪物会在你离开后复活，所以同一张通行证可以反复使用，反复挑战同一竞技场。\n2. 每个竞技场都有一个事先公开、固定不变的通行证池，池里的通行证不会被移出或改变。击败竞技场里的怪物后，除了可能掉落稀有物品外，还会从该竞技场的通行证池里随机抽取一张通行证，复制一份交给你。所以你可能在多次胜利后拥有相同类型的多张通行证副本。\n\n看了攻略后，Bajtek 得知竞技场编号越大越难。他的实力可以用一个整数 $k$ 来表示：他一定能在编号小于等于 $k$ 的竞技场获胜，而对编号大于 $k$ 的竞技场他一定无法获胜。\n\n开始时他没有任何通行证，只能花钱买**一张**。买哪一张最划算呢？\n\n他认为，如果买了竞技场 $A$ 的通行证，凭借这个起始通行证和之后的战斗所得通行证，**无论如何**他最终都能进入竞技场 $B$ 并获胜，那这张通行证就是值得买的。\n\n所以他想知道，对于某个固定的 $k$，有多少有序竞技场对 $(A,B)$ 满足：\n\n1. $A\\neq B$。\n2. 如果只买了竞技场 $A$ 的通行证，凭借这个起始通行证和之后的战斗所得通行证，无论如何他最终都能进入竞技场 $B$ 并获胜。\n\n你需要对于 $k=1,2,\\cdots,n$ 计算这样的有序对 $(A,B)$ 的个数。\n\n## Input\n\n第一行，一个整数 $n\\;(2\\le n\\le 2\\cdot 10^5)$，表示竞技场的数量。\n\n接下来 $n$ 行，其中第 $i$ 行先是一个整数 $l_i\\;(1\\le l_i)$，表示第 $i$ 个竞技场的通行证池大小。随后给出 $l_i$ 个整数，表示该池中每种通行证能进入的竞技场编号。所有 $l_i$ 的总和不超过 $5\\cdot10^5$。\n\n## Output\n\n一行，$n$ 个整数，其中第 $i$ 个整数表示 $k = i$ 时的答案。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9052","tags":["2021","PA（波兰）"],"sample_group":[["9\n2 2 3\n1 1\n1 2\n1 5\n3 5 8 9\n1 5\n2 6 4\n2 5 9\n3 5 8 5","0 1 4 4 5 6 7 7 7"]],"created_at":"2026-03-03 11:09:25"}}