#P10793. [2024年7月福建集训]Sequence 序列

    ID: 9913 传统题 1000ms 512MiB 尝试: 117 已通过: 6 难度: 9 上传者: 标签>CF2600省选/NOI-2-adic 赋值排序贪心交换论证一维前缀和二分查找

[2024年7月福建集训]Sequence 序列

题目描述

给定 nn,选择一个长度为 nn 的初始正整数数组 a1,…,ana_1,\ldots,a_n,使它可以通过下面的操作变成一个严格递增的正整数数组。

每个位置有一个操作计数 bib_i,初值为 00。每次选择一个位置 ii,把该位置的当前值 vv 改为 (v−2bi)⋅2(v-2^{b_i})\cdot2,随后将 bib_i 加一。只有操作后的值仍是正整数时,才可以进行该操作。允许某个位置从不操作。

首先最小化初始数组的元素和 ∑iai\sum_i a_i。若有多个初始数组达到最小和,选择字典序最小的一个。请输出该最小和,以及每个询问指定位置的初始值。

输入格式

第一行两个整数 n,Qn,Q(1≤n≤1091\le n\le10^9,1≤Q≤2×1051\le Q\le2\times10^5)。

第二行 QQ 个整数 q1,…,qQq_1,\ldots,q_Q(1≤qi≤n1\le q_i\le n),可以重复或不按顺序给出。

输出格式

第一行输出最小的初始元素和。接下来 QQ 行,第 ii 行输出所求初始数组的 aqia_{q_i}。

输入输出样例 #1

输入 #1

15 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

输出 #1

71
1
2
3
3
5
4
4
6
5
5
7
6
6
7
7