Z. Trick or Treap

Codeforces

IDCFZ

Time8000ms

Memory1024MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Halloween is almost here! Here in the United States, it is a tradition for young children to dress up as demons and super heros wonder around in the dark very late at night, visit random strangers in their houses, and ask for candy. Alice and Bob just solved a problem that required them to eat about $10^9$ candies and are very full now, so instead, they will ask their neighbors to either show them a trick, or give them a brand new treap ("trick or treap")! $q$ times, one of the following will happen: - 1. This neighbor will given them a new treap node $i$, with value $y$. Here, $i$ is the query number. - 2. This neighbor will perform a trick: if the nodes $y$ and $z$ are not in the same group, he will merge them into the same group, with $y$'s group to the left of $z$'s group. Otherwise, he will teach them how to juggle. - 3. This neighbor will perform a different trick: If the group containing node $y$ contains more than $z$ nodes, he will split the first $z$ nodes from the rest of them. Otherwise, he will teach them Kotlin. - 4. Alice's and Bob's overprotective mother will call and ask them about the sum of values in the group that $y$ is in. Can you write a bot to pretend to answer the queries for Alice so that she can continue to bother her neighbors in the middle of the night without interruption? The first line will contain a single integer $q$. $1 <= q <= 5 * 10^5$ $q$ lines follow. They will look like one of the following: - $1$ $y$. In this case $0 <= y <= 10^5$. - $2$ $y$ $z$. Nodes $y$ and $z$ will already exist. - $3$ $y$ $z$. Node $y$ will already exist. $0 < z$. - $4$ $y$. Node $y$ will already exist. For each query of type 4, print the sum of the values in the queried group. ## Input The first line will contain a single integer $q$. $1 <= q <= 5 * 10^5$ $q$ lines follow. They will look like one of the following:- $1$ $y$. In this case $0 <= y <= 10^5$.- $2$ $y$ $z$. Nodes $y$ and $z$ will already exist.- $3$ $y$ $z$. Node $y$ will already exist. $0 < z$.- $4$ $y$. Node $y$ will already exist. ## Output For each query of type 4, print the sum of the values in the queried group. [samples]

万圣节快到了！在美国，年轻孩子们有这样一种传统：装扮成恶魔或超级英雄，在深夜黑暗中四处游荡，敲开陌生人家的门，讨要糖果。爱丽丝和鲍勃刚刚解决了一个需要吃掉约 $10^9$ 颗糖果的问题，现在他们已经吃得太饱了，因此他们改为要求邻居们要么给他们表演一个把戏，要么送他们一个全新的 treap（“trick or treap”）！共进行 $q$ 次操作，每次会发生以下之一： - 1. 这位邻居会给他们一个新的 treap 节点 $i$，其值为 $y$。这里，$i$ 是查询的编号。 - 2. 这位邻居会表演一个把戏：如果节点 $y$ 和 $z$ 不在同一个组中，他会将它们合并为同一组，且 $y$ 的组位于 $z$ 的组左侧；否则，他会教他们如何玩杂耍。 - 3. 这位邻居会表演另一个把戏：如果包含节点 $y$ 的组包含超过 $z$ 个节点，他会将前 $z$ 个节点从其余部分中分离出来；否则，他会教他们 Kotlin。 - 4. 爱丽丝和鲍勃过度保护的母亲会打电话来，询问 $y$ 所在组中所有节点的值之和。你能写一个机器人来代替爱丽丝回答这些查询，让她可以在半夜持续打扰邻居而不被打断吗？第一行包含一个整数 $q$。$1 lt.eq q lt.eq 5 * 10^5$，随后有 $q$ 行，每行是以下形式之一： - $1$ $y$。此时 $0 lt.eq y lt.eq 10^5$。 - $2$ $y$ $z$。节点 $y$ 和 $z$ 已经存在。 - $3$ $y$ $z$。节点 $y$ 已经存在。$0 < z$。 - $4$ $y$。节点 $y$ 已经存在。对于每个类型为 4 的查询，输出该组中所有节点值的和。 ## Input 第一行包含一个整数 $q$。$1 lt.eq q lt.eq 5 * 10^5$，随后有 $q$ 行，每行是以下形式之一： - $1$ $y$。此时 $0 lt.eq y lt.eq 10^5$。 - $2$ $y$ $z$。节点 $y$ 和 $z$ 已经存在。 - $3$ $y$ $z$。节点 $y$ 已经存在。$0 < z$。 - $4$ $y$。节点 $y$ 已经存在。 ## Output 对于每个类型为 4 的查询，输出该组中所有节点值的和。 [samples]

**Definitions** Let $ q \in \mathbb{Z} $ be the number of queries. Let $ V \subseteq \mathbb{Z}_{\geq 0} $ be the set of node identifiers, with $ |V| \leq q $. Let $ \text{val}: V \to \mathbb{Z} $ be a function mapping each node $ i $ to its value $ y $, assigned on type-1 queries. Let $ \mathcal{G} = \{ G_1, G_2, \dots \} $ be a partition of $ V $ into ordered groups (lists), where each group $ G $ is a sequence of nodes $ (n_1, n_2, \dots, n_k) $, ordered left to right. **Constraints** 1. $ 1 \leq q \leq 5 \cdot 10^5 $ 2. For type-1 queries: $ 0 \leq y \leq 10^5 $, node $ i $ (query number) is assigned value $ y $, and is inserted as a singleton group. 3. For type-2 queries: nodes $ y, z $ exist; merge the group containing $ y $ to the left of the group containing $ z $. 4. For type-3 queries: node $ y $ exists, $ z > 0 $; if $ |G_y| > z $, split $ G_y $ into $ (n_1, \dots, n_z) $ and $ (n_{z+1}, \dots, n_k) $; otherwise, do nothing. 5. For type-4 queries: node $ y $ exists; output $ \sum_{n \in G_y} \text{val}(n) $. **Objective** For each query of type 4, compute and output: $$ \sum_{n \in G_y} \text{val}(n) $$ where $ G_y $ is the group containing node $ y $.

API Response (JSON)

{
  "problem": {
    "name": "Z. Trick or Treap",
    "description": {
      "content": "Halloween is almost here! Here in the United States, it is a tradition for young children to dress up as demons and super heros wonder around in the dark very late at night, visit random strangers in ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CFZ"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Halloween is almost here! Here in the United States, it is a tradition for young children to dress up as demons and super heros wonder around in the dark very late at night, visit random strangers in ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "万圣节快到了！在美国，年轻孩子们有这样一种传统：装扮成恶魔或超级英雄，在深夜黑暗中四处游荡，敲开陌生人家的门，讨要糖果。\n\n爱丽丝和鲍勃刚刚解决了一个需要吃掉约 $10^9$ 颗糖果的问题，现在他们已经吃得太饱了，因此他们改为要求邻居们要么给他们表演一个把戏，要么送他们一个全新的 treap（“trick or treap”）！共进行 $q$ 次操作，每次会发生以下之一：\n\n- 1. 这位邻居会给...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ q \\in \\mathbb{Z} $ be the number of queries.  \nLet $ V \\subseteq \\mathbb{Z}_{\\geq 0} $ be the set of node identifiers, with $ |V| \\leq q $.  \nLet $ \\text{val}: V \\to \\mathbb{Z}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments