python实现 CCF201709-5 除法_综合

试题编号：	201709-5
试题名称：	除法
时间限制：	10.0s
内存限制：	256.0MB
问题描述：	问题描述　　小葱喜欢除法，所以他给了你N个数a1, a2, ?, aN，并且希望你执行M次操作，每次操作可能有以下两种：　　给你三个数l, r, v，你需要将al, al+1, ?, ar之间所有v的倍数除以v。　　给你两个数l, r，你需要回答al + al+1 + ? + ar的值是多少。输入格式　　第一行两个整数N, M，代表数的个数和操作的次数。　　接下来一行N个整数，代表N个数一开始的值。　　接下来M行，每行代表依次操作。每行开始有一个整数opt。如果opt=1，那么接下来有三个数l, r, v，代表这次操作需要将第l个数到第r个数中v的倍数除以v；如果opt = 2，那么接下来有两个数l, r，代表你需要回答第l个数到第r个数的和。输出格式　　对于每一次的第二种操作，输出一行代表这次操作所询问的值。样例输入 5 3 1 2 3 4 5 2 1 5 1 1 3 2 2 1 5 样例输出 15 14 评测用例规模与约定　　对于30%的评测用例，1 ≤ N, M ≤ 1000；　　对于另外20%的评测用例，第一种操作中一定有l = r；　　对于另外20%的评测用例，第一种操作中一定有l = 1 , r = N；　　对于100%的评测用例，1 ≤ N, M ≤ 105，0 ≤ a1, a2, ?, aN ≤ 106, 1 ≤ v ≤ 106, 1 ≤ l ≤ r ≤ N。

50分代码（运行超时，树形数组）

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.insert(0,0)
tree = [0] * (n+1)          # 树形数组,注意数组要从1开始
def lowbit(x):              # 计算2^k的值（其中k为x的二进制中从最低到高位连续0的长度）return (-x) & xdef update(x, y, n):        # 单点更新'''x为更新的位置，y为更新后的值，n为数组个数tree[i] = A[i+1-2^k]+A[i+2-2^k]+...+A[i]'''i = xwhile i < n:tree[i] += yi += lowbit(i)def getsum(i):              # 单点更新的逆操作ans = 0while i > 0:ans += tree[i]i -= lowbit(i)return ans# 初始化树形数组
for i in range(1, n+1):update(i, a[i], n+1)result = []
for i in range(m):temp = list(map(int, input().split()))op, l, r = temp[0], temp[1], temp[2]if op == 2:ans = getsum(r) - getsum(l-1)  # 求l到r的和result.append(ans)elif op == 1:v = temp[3]if v == 1:continuefor i in range(l, r+1):if a[i] >= v and a[i] % v == 0:update(i, -(a[i] - a[i]//v), n+1)  # 注意这里的y为：tree[i]=tree[i]-a[i]+a[i]/va[i] = a[i] // v
for i in result:print(i)