CF1452F Divide Powers

给定一个由若干 $2$ 的幂次构成的多重集。更具体地说，对于每个 $i$ 从 $0$ 到 $n-1$，你有 $cnt_i$ 个元素，每个元素的值为 $2^i$。 每次操作，你可以选择任意一个 $2^l > 1$ 的元素，将其拆分为两个 $2^{l-1}$ 的元素。 你需要进行 $q$ 次询问。每个询问有两种类型： - “$1$ $pos$ $val$” —— 令 $cnt_{pos} := val$； - “$2$ $x$ $k$” —— 计算最少需要多少次操作，才能使得值小于等于 $2^x$ 的元素数量不少于 $k$。 注意，所有第二类询问都不会改变多重集本身；也就是说，你只需要计算最少操作次数，而不需要真正执行这些操作。

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 30$，$1 \le q \le 2 \cdot 10^5$），分别表示数组 $cnt$ 的大小和询问的数量。 第二行包含 $n$ 个整数 $cnt_0, cnt_1, \dots, cnt_{n-1}$（$0 \le cnt_i \le 10^6$）。 接下来的 $q$ 行，每行一个询问。每个询问有两种类型之一： - “$1$ $pos$ $val$” （$0 \le pos < n$；$0 \le val \le 10^6$）； - “$2$ $x$ $k$” （$0 \le x < n$；$1 \le k \le 10^{15}$）。 保证至少有一个第二类询问。

对于每个第二类询问，输出一行，表示最少需要多少次操作，才能使值小于等于 $2^x$ 的元素数量不少于 $k$；如果无法做到，输出 $-1$。

由 ChatGPT 4.1 翻译