CodeforcesRound#250(Div.1)D线段树_html/css_WEB-ITnose

看看type = 2的操作，对于区间[l,r]内的元素对x取模，由于取模肯定不能和取模，所以只能每个元素取模，看上去不是区间更新，但是仔细一看，若区间[l,r]内所有的元素都小于x,那么这一区间不需要管，所以还是存在区间整段操作，所以需要lazy,这里也算是一个剪枝了，剩下的就是type = 3的 单点更新，还有type = 1的区间求和，整体操作不难

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