D. The Child and Sequence(线段树+思维)

题目大意：
给你一个序列，你要在这个序列上进行操作。
操作 $1:$1:给定区间 $[l,r]$[l,r]，对序列中这个区间的所有数 $ai,i=[l,r]$ai,i=[l,r]求和。
操作 $2:$2:给你区间 $[l,r]和x$[l,r]和x,对 $i=[l,r],ai$i=[l,r],ai mod $x$x。
操作 $3:$3:给你两个数个数 $i,k,$i,k,将 $ai=k$ai=k。
思路：
注意到 $m=1e5$m=1e5，所以整体时间复杂度 $O\left(nlogn\right)$O(nlogn)，也就是说你的所以操作时间复杂度不超过 $O\left(logn\right)$O(logn)才过通过这个题。注意到区间求和，单点操作用线段树都可以在 $O\left(logn\right)$O(logn)做到，唯一有难度的就是操作对对区间所以数取模。首先考虑一个小小的剪枝，如果某个区间里面的最大数都 <x，那么这个区间不用管了，因为 $p$p mod x=p,p<x。当 $p>x,p$p>x,p mod x<=x/2。稍微证明一下。
令 $r=x$r=x mod $p$p
那么有 $x=kp+r$x=kp+r
当 $k=0,r=x=x$k=0,r=x=x mod $p$p.
当 $k>0,x$k>0,x mod p=r<p， 2r/2<(p+r)/2<(kp+r)/2<=x/2。
也就是说对于区间内的每个数 $x$x，对它取mod，这个数至少会减低 $x/2$x/2，那么我们每次对这个数进行取模，这个数到 $0$0的时间复杂度也无非就是 $O\left(logx\right)$O(logx)，所以整体时间复杂度 $O\left(mlogmlogx\right)$O(mlogmlogx)，带两个 $log$log是可以过这道题的。
总结：
关于取模这里，其实不用证明也很容易想到，因为当 $x$x mod $p,且x>p$p,且x>p，只有当 $p=x/2$p=x/2这个时候才能取到最大值。它在其他地方的取模是对称的，函数图像大概是正态分布的函数图。对称轴就是 $x/2$x/2。
代码：

#include<iostream>
using namespace std;
int n,m;
typedef long long int ll;
const int maxn = 1e5 + 10;
struct seg{
	int l,r;
	ll s,m;
	seg(){s = 0,m = 0;}
	seg(int a,int b):l(a),r(b){}
}tree[maxn << 2];
void build(int id,int l,int r){
	if(l == r){
		tree[id] = {l,r};
		scanf("%d",&tree[id].s);
		tree[id].m = tree[id].s;
		return ;
	}
	int mid = l + r >> 1;
	tree[id] = {l,r};
	build(id << 1,l, mid);
	build((id << 1) + 1,mid + 1,r);
	tree[id].s = tree[id << 1].s + tree[(id << 1) + 1].s; 
	tree[id].m = max(tree[id << 1].m , tree[(id << 1) + 1].m);
}
void update(int id,int a,ll b){
	if(tree[id].l == tree[id].r && tree[id].l == a){
		tree[id].s = b;
		tree[id].m = b;
		return ;
	}
	int mid = tree[id].l + tree[id].r >> 1; 
	if(a <= mid)update(id << 1,a,b);
	else update((id << 1) + 1,a,b);
	tree[id].s = tree[id << 1].s + tree[(id << 1) + 1].s;
	tree[id].m = max(tree[id << 1].m,tree[(id << 1) + 1].m);
}
void update2(int id,int l,int r,ll x){
	if(tree[id].m < x)return;
	if(tree[id].l == tree[id].r && tree[id].l >= l && tree[id].r <= r){
		tree[id].s %= x;
		tree[id].m = tree[id].s;	
		return ;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	if(r <= mid)update2(id << 1,l,r,x);
	else if(l > mid)update2((id << 1) + 1,l,r,x);
	else update2(id << 1,l,r,x),update2((id << 1) + 1,l,r,x);
	tree[id].m = max(tree[id << 1].m,tree[(id << 1) + 1].m);
	tree[id].s = tree[id << 1].s + tree[(id << 1) + 1].s;
}
ll query(int id,int l,int r){
	if(tree[id].l >= l && tree[id].r <= r){
		return tree[id].s;
	}
	ll ans = 0;
	int mid = tree[id].l + tree[id].r >> 1;
	if(r <= mid)return ans += query(id << 1,l,r);
	else if(l > mid)return ans += query((id << 1) + 1,l,r);
	else return ans += query(id << 1,l,r) + query((id << 1) + 1,l,r);
}
void solved(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	int l,r,k,x;
	while(m--){
		int ins;scanf("%d",&ins);
		if(1 == ins){
			scanf("%d%d",&l,&r);
			printf("%lld\n",query(1,l,r));
		}
		if(2 == ins){
			scanf("%d%d%d",&l,&r,&x);
			update2(1,l,r,x);
		}
		if(3 == ins){
			scanf("%d%d",&k,&x);
			update(1,k,x);
		}
	}
}
int main(){
	solved();
	return 0;
}