[ABC368G] Add and Multiply Queries 讲解

zrl123456 · 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 的值域）。

代码