← 返回题目列表

Codeforces · 1452/F

F. 划分权力

中文机器翻译题面 查看原题

你被赋予了一组由二组成的多重权力。更准确地说,对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$i$$$ 不包括,您拥有等于 $$$2^i$$$ 的 $$$cnt_i$$$ 元素。

在一次操作中,您可以选择任意一个元素 $$$2^l > 1$$$ 并将其分为两个元素 $$$2^{l - 1}$$$。

您应该执行 $$$q$$$ 查询。每个查询都有两种类型之一:

- "$$$1$$$ $$$pos$$$ $$$val$$$"—分配$$$cnt_{pos} := val$$$;
- "$$$2$$$ $$$x$$$ $$$k$$$" — 计算至少需要 $$$k$$$ 元素的值低于或等于 $$$2^x$$$ 的最小操作数。

请注意,第二类型的所有查询都不会更改多重集;也就是说,您只计算最少的操作数,而不执行它们。

输入

第一行包含两个整数 $$$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}$$$)。

保证至少有一个第二类型的查询。

输出

对于第二种类型的每个查询,打印至少需要 $$$k$$$ 元素的最小操作数,其值低于或等于 $$$2^x$$$ 或 $$$-1$$$(如果没有办法做到)。

示例

输入 #1

6 11
0 1 0 0 1 0
2 1 5
2 4 18
1 1 0
2 2 5
2 0 17
1 0 3
2 1 2
1 1 4
1 4 0
1 5 1
2 2 8

输出 #1

4
16
4
-1
0
1