数学计算题解
查看原帖
数学计算题解
1070754
lijunxi20231818楼主2024/8/28 18:24

题目传送

可以比较容易地注意到:

本题中出现的除法运算的除数,必定在此前的乘法运算中出现。

且良心出题人还告诉我们

(保证第 pospos 次操作一定为类型 1,对于每一个类型 1 的操作至多会被除一次)

则考虑不进行除法,而是删除此前对应的乘法操作。

(不说就不能愉快segmentsegment treetree了)

那么,我们的需求就是

1.1. 单点修改(乘法的乘数改为1) 2.2. 区间查询(即计算乘积)

到这里,思路已经显然。 考虑线段树维护区间乘法。

对于操作类别为11的操作ii,我们直接把这个对应的线段树叶子结点的mulmul值设置为mm

对于操作类别为22的操作jj,考虑将pospos对应叶子结点的mulmul值设置为11

特别地,注意将叶子结点的mulmul值初始化为11,这是因为操作2使用的pospos叶子结点必定是操作11的,故所以操作22对应结点始终为初始值。 (当然,涉及乘法运算的,初始值都应该设置为1)

线段树的queryquery维护乘积即可A掉此题

2024/8/28 18:24
加载中...