Codeforces Round #250 (Div. 1) D 線段樹

Codeforces Round #250 (Div. 1) D 線段樹

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