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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#250(Div.1)D线段树_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2286字，纯文字阅读大概需要4分钟。

内容图文

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

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#250(Div.1)D线段树_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#250(Div.1)D线段树_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端