[JOI 2022 Final] 星际蛋糕 / Intercastellar

Luogu

IDLGP8160

Time2000ms

Memory537MB

DifficultyP2

二分2022O2优化前缀和JOI（日本）

castella 的形状是一个在水平方向上很长的长方体。它被切成了 $N$ 段，其中从左往右的第 $i$ 段的长度为整数 $A_i$。几分钟前，我们得知 JOI 星球的居民不喜欢偶数。为了解决此问题，你需要不断执行下列操作，直到不存在长度为偶数的段。 1. 在长度为偶数的段中，你选择最靠右的一段。 2. 你将选中的这一段切成两个长度相等的段。也就是说，假设选中的这一段的长度是 $k$，你将其切成长度为 $\displaystyle \frac{k}{2}$ 的两段。你不改变其他段的位置。为了确认操作是否被正确地执行了，比太郎让你回答 $Q$ 个询问。第 $j$ 个询问如下： - 当所有操作执行完毕后，从左往右的第 $X_j$ 段的长度为多少？给定 castella 的信息与询问，请写一个程序回答所有询问。 ## Input 第一行，一个正整数 $N$。接下来 $N$ 行，第 $i$ 行一个正整数 $A_i$。接下来一行，一个正整数 $Q$。接下来 $Q$ 行，第 $j$ 行一个正整数 $X_j$。 ## Output 输出 $Q$ 行，第 $j$ 行一个数，表示第 $j$ 个询问的答案。 [samples] ## Background 在 30XX 年，由于科学家和工程师的不断努力，不同星球之间的互动变得非常活跃。比太郎是一只河狸，他现在是一项交流项目的大使。他的任务是向不同星球的居民介绍地球上的食物。他将在下午 1 点出发去 JOI 星球。现在，比太郎正计划向 JOI 星球的居民介绍 castella。castella 已经被切成了若干段。castella 是一种由面粉、鸡蛋、糖和淀粉糖浆制成的烘烤海绵蛋糕。 ![](https://cdn.luogu.com.cn/upload/image_hosting/krpqlhl4.png) ## Note **【样例解释 \#1】** 一开始，castella 从左到右的段的长度分别为 $14, 9, 8, 12$。当所有操作执行完毕后，castella 被切成了 $15$ 段。从左到右的段的长度分别为 $7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3$。这个样例满足子任务 $2, 3$ 的限制。 **【样例解释 \#2】** 这个样例满足所有子任务的限制。 **【样例解释 \#3】** 这个样例满足子任务 $2, 3$ 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** 对于 $100 \%$ 的数据，$1 \le N, Q \le 2 \times {10}^5$，$1 \le A_i \le {10}^9$，$1 \le X_j \le {10}^{15}$，$X_j \le X_{j + 1}$，保证当所有操作执行完毕后，castella 被切成了至少 $X_Q$ 段。 - 子任务 $1$（$25$ 分）：$A_i \le 8$。 - 子任务 $2$（$35$ 分）：$N, Q \le 1000$。 - 子任务 $3$（$40$ 分）：无特殊限制。 ---- **译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T1「[インターカステラー](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t1.pdf) / [Intercastellar](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t1-en.pdf)」**

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[JOI 2022 Final] 星际蛋糕 / Intercastellar",
    "description": {
      "content": "castella 的形状是一个在水平方向上很长的长方体。它被切成了 $N$ 段，其中从左往右的第 $i$ 段的长度为整数 $A_i$。 几分钟前，我们得知 JOI 星球的居民不喜欢偶数。为了解决此问题，你需要不断执行下列操作，直到不存在长度为偶数的段。 1. 在长度为偶数的段中，你选择最靠右的一段。 2. 你将选中的这一段切成两个长度相等的段。也就是说，假设选中的这一段的长度是 $k$，你将其",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 549888
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8160"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "castella 的形状是一个在水平方向上很长的长方体。它被切成了 $N$ 段，其中从左往右的第 $i$ 段的长度为整数 $A_i$。\n\n几分钟前，我们得知 JOI 星球的居民不喜欢偶数。为了解决此问题，你需要不断执行下列操作，直到不存在长度为偶数的段。\n\n1. 在长度为偶数的段中，你选择最靠右的一段。\n2. 你将选中的这一段切成两个长度相等的段。也就是说，假设选中的这一段的长度是 $k$，你将其...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments