U34379.树状数组二分

已知一个数列 $a$，你需要进行下面两种操作：

1. 将某一个数修改成 $d$。
2. 查询最大的 $P(0\le P \le n)$ 满足 $\sum_{i=1}^P\ a_i \le s$

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $2$ 或 $3$ 个整数，表示一个操作，具体如下：

1. 1 x d：将第 $x$ 个数改成 $d$。
2. 2 s：查询最大的 $P(0\le P \le n)$ 满足 $\sum_{i=1}^P\ a_i \le s$

对于每一个查询，输出一行，表示答案。

对于 $50\%$ 的数据：$n \le 1000$，$m \le 1000$。
对于 $80\%$ 的数据： $1 \le n, m \le 2*{10}^5$。
对于 $100\%$ 的数据： $1 \le n, m \le 2*{10}^6$。

• $1 \le a_i \le 10^9$
• $1 \le d \le 10^9$
• $1 \le s \le 10^{15}$

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

此题输入较多需要关闭流加速

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);