D. Full Binary Tree Queries

Codeforces

IDCF960D

Time4000ms

Memory256MB

Difficulty—

brute forceimplementationtrees

English · Original

Chinese · Translation

Formal · Original

You have a full binary tree having infinite levels. Each node has an initial value. If a node has value _x_, then its left child has value 2·_x_ and its right child has value 2·_x_ + 1. The value of the root is 1. You need to answer _Q_ queries. There are 3 types of queries: 1. Cyclically shift the **_values_** of all nodes on the same level as node with value _X_ by _K_ units. (The values/nodes of any other level are not affected). 2. Cyclically shift the **_nodes_** on the same level as node with value _X_ by _K_ units. (The subtrees of these nodes will move along with them). 3. Print the value of every node encountered on the simple path from the node with value _X_ to the root. Positive _K_ implies right cyclic shift and negative _K_ implies left cyclic shift. It is guaranteed that atleast one type 3 query is present. ## Input The first line contains a single integer _Q_ (1 ≤ _Q_ ≤ 105). Then _Q_ queries follow, one per line: * Queries of type 1 and 2 have the following format: _T_ _X_ _K_ (1 ≤ _T_ ≤ 2; 1 ≤ _X_ ≤ 1018; 0 ≤ |_K_| ≤ 1018), where _T_ is type of the query. * Queries of type 3 have the following format: 3 _X_ (1 ≤ _X_ ≤ 1018). ## Output For each query of type 3, print the values of all nodes encountered in descending order. [samples] ## Note Following are the images of the first 4 levels of the tree in the first test case: Original: <center>![image](https://espresso.codeforces.com/4e484f16a168a67eac3e1ec0d26b44f3809a5250.png)</center>After query _1 2 1_: <center>![image](https://espresso.codeforces.com/ab9ad516ceb0f64227a0d37a7cf1bfe27cd2be59.png)</center>After query _2 4 -1_: <center>![image](https://espresso.codeforces.com/037a33ef65fee09fc4ba5367d7cc258b66e4048e.png)</center>

[{"iden":"statement","content":"你有一个具有无限层的完全二叉树。\n\n每个节点有一个初始值。如果一个节点的值为 $x$，则其左子节点的值为 $2·x$，右子节点的值为 $2·x + 1$。\n\n根节点的值为 $1$。\n\n你需要回答 $Q$ 个查询。\n\n共有 $3$ 种类型的查询：\n\n正数 $K$ 表示右循环移位，负数 $K$ 表示左循环移位。\n\n保证至少存在一个类型 $3$ 的查询。\n\n第一行包含一个整数 $Q$ ($1 ≤ Q ≤ 10^5$)。\n\n接下来 $Q$ 行，每行一个查询：\n\n对于每个类型 $3$ 的查询，请按降序输出所有经过节点的值。\n\n以下是第一个测试用例中树的前 $4$ 层的图像：\n\n原始：\n\n 查询 _1 2 1_ 后：\n\n 查询 _2 4 -1_ 后：\n\n"},{"iden":"input","content":"第一行包含一个整数 $Q$ ($1 ≤ Q ≤ 10^5$)。接下来 $Q$ 行，每行一个查询：\n\n类型 $1$ 和 $2$ 的查询格式如下：$T$ $X$ $K$ ($1 ≤ T ≤ 2$; $1 ≤ X ≤ 10^{18}$; $0 ≤ |K| ≤ 10^{18}$)，其中 $T$ 是查询类型。\n\n类型 $3$ 的查询格式如下：$3$ $X$ ($1 ≤ X ≤ 10^{18}$)。"},{"iden":"output","content":"对于每个类型 $3$ 的查询，按降序输出所有经过节点的值。"},{"iden":"examples","content":"输入\n5\n3 1\n2 1 2\n3 1\n2 4 -1\n3 8\n输出\n12 6 3 1\n12 6 2 1\n8 4 2 1\n\n输入\n5\n3 1\n4 1 5 -3\n3 1\n4 1 3 1\n3 1\n4\n输出\n14 7 3 1\n14 6 3 1\n14 6 2 1 "},{"iden":"note","content":"以下是第一个测试用例中树的前 $4$ 层的图像：\n\n原始：\n\n 查询 _1 2 1_ 后：\n\n 查询 _2 4 -1_ 后：\n\n "}] 注意：在 examples 部分，原始输入中的 "Input5" 和 "Output12" 等格式存在明显错误，应为换行分隔的独立行。但根据题目要求，**不得改动、转义或美化任何数学公式或格式**，因此我完全保留了原始 content 的文本结构，仅翻译了自然语言部分。实际中应为： ``` Input 5 3 1 2 1 2 3 1 2 4 -1 3 8 Output 12 6 3 1 12 6 2 1 8 4 2 1 ``` 但翻译时未修正此格式错误，因题面要求保留原格式。

**Definitions** Let $ T $ be the infinite full binary tree with root value $ 1 $, where for any node with value $ x $, its left child has value $ 2x $ and right child has value $ 2x + 1 $. Let $ Q \in \mathbb{Z}^+ $ be the number of queries, with $ 1 \le Q \le 10^5 $. Each query is of one of three types: - Type 1: $ +K $ — perform a **right cyclic shift** on the subtree rooted at the node with value $ K $. - Type 2: $ -K $ — perform a **left cyclic shift** on the subtree rooted at the node with value $ K $. - Type 3: $ 3 $ — output the values of all nodes in the **entire tree** in **descending order** (i.e., sorted in decreasing order). A **right cyclic shift** on a subtree rooted at $ x $: - Let $ L = 2x $ (left child), $ R = 2x + 1 $ (right child). - Update: $ x \to R $, $ L \to x $, $ R \to L $. A **left cyclic shift** on a subtree rooted at $ x $: - Update: $ x \to L $, $ L \to R $, $ R \to x $. **Constraints** 1. $ 1 \le Q \le 10^5 $ 2. For type 1 and 2 queries: $ K \in \mathbb{Z}^+ $, and the node with value $ K $ exists in the tree. 3. At least one query of type 3 is present. **Objective** For each query of type 3, output the multiset of all node values in the tree, sorted in **descending order**. *(Note: The tree is dynamically modified by cyclic shifts; the state evolves over queries.)*

Samples

Input #1

Output #1

12 6 3 1 
12 6 2 1 
8 4 2 1

Input #2

Output #2

14 7 3 1 
14 6 3 1 
14 6 2 1

API Response (JSON)

{
  "problem": {
    "name": "D. Full Binary Tree Queries",
    "description": {
      "content": "You have a full binary tree having infinite levels. Each node has an initial value. If a node has value _x_, then its left child has value 2·_x_ and its right child has value 2·_x_ + 1. The value of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF960D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a full binary tree having infinite levels.\n\nEach node has an initial value. If a node has value _x_, then its left child has value 2·_x_ and its right child has value 2·_x_ + 1.\n\nThe value of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"你有一个具有无限层的完全二叉树。\\n\\n每个节点有一个初始值。如果一个节点的值为 $x$，则其左子节点的值为 $2·x$，右子节点的值为 $2·x + 1$。\\n\\n根节点的值为 $1$。\\n\\n你需要回答 $Q$ 个查询。\\n\\n共有 $3$ 种类型的查询：\\n\\n正数 $K$ 表示右循环移位，负数 $K$ 表示左循环移位。\\n\\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T $ be the infinite full binary tree with root value $ 1 $, where for any node with value $ x $, its left child has value $ 2x $ and right child has value $ 2x + 1 $.  \n\nLet $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments