201709-5 除法

思路：

这道题就是一个单点更新，区间查询的问题，所以用树状数组就行了。不过说实话，自己对第四第五题的态度需要改变一下。暴力可以，但是应该看到是运行超时，而不是错误。如果运行超时看下有没有极端情况可以跳过优化一下，不要想着暴力完了就完事了。

代码：

#include 
using namespace std;
#define lowbit(i) ((i) & (-i))
const int N = 1e5 + 5;
typedef long long ll;
ll c[N];
int n,m;
ll num[N];
long long read(){//读优化，没有这个90分
    	long long x=0,f=1;
    	char c=getchar();//scanf函数比getchar函数慢不少，当需要大量输入数据时可考虑优化
    	while(c>'9'||c<'0'){
    		if(c=='-') f=-f;
    		c=getchar();
    	}
    	while(c>='0'&&c<='9'){
    		x=x*10+c-'0';
    		c=getchar();
    	}
    	return x*f;
}
void update(int x, ll v){
	for(int i = x; i <= n;i += lowbit(i)){
		c[i] += v;
	}
}
long long getsum(int x){
	long long sum = 0;
	for(int i = x;i >= 1;i -= lowbit(i)){
		sum += c[i];
	}
	return sum;
}
int main(){
	n = read(), m = read();
	for(int i = 1;i<=n;i++){
		ll v;
		v = read();
		num[i]  = v;
		update(i, v);
	}
	while(m--){
		ll opt;
		opt = read();
		if(opt == 1){
			ll l,r,v;
			l = read(), r = read(), v = read();
			if(v == 1)continue;
			for(int i = l;i<=r;i++){
				if(num[i] >= v && num[i] % v == 0){
					update(i, num[i] / v - num[i]);
					num[i] /= v;
				}
			}
		}else{
			ll l,r;
			l = read(), r = read();
			printf("%lld\n", getsum(r) - getsum(l - 1));
		}
	}
}