#P15466. 星轨序列

    ID: 14681 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-2-adic 赋值交换论证一维前缀和前后缀最值二分查找

星轨序列

题目描述

星际观测站正在校准一组星轨编号。给定一个长度为 nn 的正整数序列 aa,每个位置都有一个独立的校准计数器。

校准开始前,创建一个长度为 nn 的数组 cc,初始时所有 ci=0c_i=0。

之后你可以进行任意多次如下校准操作:

  • 选择一个位置 1≤x≤n1\le x\le n;
  • 先令
ax:=(ax−2cx)×2,a_x := (a_x-2^{c_x})\times 2,
  • 再令
cx:=cx+1.c_x := c_x+1.

如果经过若干次校准后,序列 aa 可以变成一个严格递增的正整数序列,那么称原序列 aa 为一个 可校准序列。

现在你希望构造一个长度为 nn 的可校准序列 aa,并满足:

  1. ∑i=1nai\sum_{i=1}^{n}a_i 尽可能小;
  2. 在所有总和最小的方案中,序列 aa 的字典序尽可能小。

由于 nn 可能非常大,你不需要输出整个序列。你只需要输出最小的总和,并回答若干个指定位置上的值。

给定 QQ 个位置 b1,b2,…,bQb_1,b_2,\dots,b_Q,请输出最优序列中这些位置对应的 abia_{b_i}。

输入格式

第一行两个整数 n,Qn,Q。

第二行 QQ 个正整数 b1,b2,…,bQb_1,b_2,\dots,b_Q。

输出格式

第一行输出一个整数,表示最小可能的

∑i=1nai.\sum_{i=1}^{n}a_i.

接下来 QQ 行,第 ii 行输出最优序列中的 abia_{b_i}。

样例 1 输入

10 10
1 2 3 4 5 6 7 8 9 10

样例 1 输出

38
1
2
3
3
5
4
4
5
5
6

样例 2

见选手目录下 halation/ex_halation2.inhalation/ex\_halation2.in 与 halation/ex_halation2.outhalation/ex\_halation2.out。

该样例满足子任务 22 的限制。

样例 3

见选手目录下 halation/ex_halation3.inhalation/ex\_halation3.in 与 halation/ex_halation3.outhalation/ex\_halation3.out。

该样例满足子任务 33 的限制。

数据范围

对于所有数据,满足 1≤n≤1091\le n\le 10^9,1≤Q≤1051\le Q\le 10^5。

Subtask nn QQ 分值
1 ≤8\le 8 1515
2 ≤109\le 10^9 =0=0
3 ≤1000\le 1000
4 ≤109\le 10^9 ≤10\le 10 2020
5 ≤105\le 10^5 3535