题目传送
可以比较容易地注意到:
本题中出现的除法运算的除数,必定在此前的乘法运算中出现。
且良心出题人还告诉我们
(保证第 pos 次操作一定为类型 1,对于每一个类型 1 的操作至多会被除一次)
则考虑不进行除法,而是删除此前对应的乘法操作。
(不说就不能愉快segment tree了)
那么,我们的需求就是
1. 单点修改(乘法的乘数改为1)
2. 区间查询(即计算乘积)
到这里,思路已经显然。
考虑线段树维护区间乘法。
对于操作类别为1的操作i,我们直接把这个对应的线段树叶子结点的mul值设置为m
对于操作类别为2的操作j,考虑将pos对应叶子结点的mul值设置为1
特别地,注意将叶子结点的mul值初始化为1,这是因为操作2使用的pos叶子结点必定是操作1的,故所以操作2对应结点始终为初始值。
(当然,涉及乘法运算的,初始值都应该设置为1)
线段树的query维护乘积即可A掉此题