CodeforcesRound#250(Div.1)D线段树_html/css

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;}