Codeforces Round #250 (Div. 1) D segment tree_html/css_WEB-ITnose

Look at the operation of type = 2. For the elements in the interval [l, r], modulo Interval update, but if you look carefully, if all elements in the interval [l, r] are less than x, then this interval does not need to be managed, so there is still an entire interval operation, so lazy is needed, and this is also considered a pruning , the rest is a single point update of type = 3, and an interval summation of type = 1. The overall operation is not difficult

int n,m;ll nnum[100000 + 55];typedef struct Node {	int l,r;	ll sum;	ll maxn;};Node tree[100000 * 4 + 55];void init() {	memset(nnum,0,sizeof(nnum));}bool input() {	while(cin>>n>>m) {		for(int i=1;i<=n;i++)scanf("%I64d",&nnum[i]);		return false;	}	return true;}void push_up(int id) {	tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;	tree[id].maxn = max(tree[id<<1].maxn,tree[id<<1|1].maxn);}void build(int l,int r,int id) {	tree[id].l = l;	tree[id].r = r;	tree[id].maxn = 0;	tree[id].sum = 0;	if(l == r) {		tree[id].maxn = nnum[l];		tree[id].sum = nnum[l];		return ;	}	int mid = (l + r)>>1;	build(l,mid,id<<1);	build(mid+1,r,id<<1|1);	push_up(id);}ll query(int l,int r,int id) {	if(tree[id].l == l && tree[id].r == r)return tree[id].sum;	int mid = (tree[id].l + tree[id].r)>>1;	if(r <= mid) return query(l,r,id<<1);	else if(l > mid) return query(l,r,id<<1|1);	else		return query(l,mid,id<<1) + query(mid + 1,r,id<<1|1);}void update(int l,int r,ll x,int id) {	if(tree[id].maxn < x) return ;	int mid = (tree[id].l + tree[id].r)>>1;	if(tree[id].l == tree[id].r) {		tree[id].sum %= x;		tree[id].maxn = tree[id].sum;		return ;	}	if(r <= mid)update(l,r,x,id<<1);	else if(l > mid)update(l,r,x,id<<1|1);	else {		update(l,mid,x,id<<1);		update(mid + 1,r,x,id<<1|1);	}	push_up(id);}void update2(int pos,int val,int id) {	if(tree[id].l == tree[id].r) {		tree[id].sum = tree[id].maxn = val;		return ;	}	int mid = (tree[id].l + tree[id].r)>>1;	if(pos <= mid)update2(pos,val,id<<1);	else update2(pos,val,id<<1|1);	push_up(id);}void cal() {	build(1,n,1);	int q = m;	while(q--) {		int type;		scanf("%d",&type);		if(type == 1) {			int l,r;			scanf("%d %d",&l,&r);			ll ans = query(l,r,1);			printf("%I64d\n",ans);		}		else if(type == 2) {			int l,r;			ll x;			scanf("%d %d %I64d",&l,&r,&x);			update(l,r,x,1);		}		else {			int k,x;			scanf("%d %d",&k,&x);			update2(k,x,1);		}	}}void output() {}int main() {	while(true) {		init();		if(input())return 0;		cal();		output();	}	return 0;}