本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-25 13:14:37

[ABC368G] Add and Multiply Queries

题目考察：set（STL），树状数组。
题目简述：
给你两个序列 $\{a_n\},\{b_n\}$，有 $q$ 次操作，每个操作可能是以下三种之一：

1. 将 $a_{pos}$ 改为 $x$。
2. 将 $b_{pos}$ 改为 $x$。
3. 设 $f_i(x)$ 为 $\max(x+a_i,x\times b_i)$，给你区间 $[l,r]$，求 $ans=f_r(f_{r-1}(\dots(f_{l+1}(f_l(0)))))$。

数据范围：

• $1\le n,q\le 10^5$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^9$
• 在 $1,2$ 操作中，$1\le pos\le n$
• 在 $1,2$ 操作中，$1\le x\le 10^9$
• 在 $3$ 操作中，$1\le l\le r\le n$
• 在 $3$ 操作中，$1\le ans\le 10^{18}$

乍一看这道题既不满足前缀和的性质，也不满足 ST 表的性质，非常不可做。

实际上我们发现在 $x\in[l,r]$ 的点中 $b_x>1$ 的最多只有 $60$ 个（因为 $ans\le 10^{18}$）。
那么我们将加的数扔进树状数组里，将大于一的乘的数的下标扔进 set 里，查询的时候暴力去找第一个非 $1$ 的乘的数，用树状数组去求前面的和就可以了。

时间复杂度为 $\Theta(n\log V\log n)$（$V$ 是 $ans$ 的值域）。

代码