CodeForces 438D The Child and Sequence（线段树区间取模）

CodeForces 438D The Child and Sequence

洛谷 The Child and Sequence

题目大意

给出一个长度为$n$的非负整数序列$a$，需要支持以下操作：

• 给出$l,r$，求$l,r$之间的数的和
• 给出$l,r,x$，将$l,r$之间的每个$a_i$都对$x$取模
• 给出$k,v$，将$a_k$的值改为$v$

题解

如果只有$1,3$操作，那么这道题就是一道满足单点修改和区间查询的线段树模板。下面，我们考虑如何处理区间取模操作。

令$a,b$都为正整数，则

• 若$a<b$，则$a\%b=a$
• 若$a\ge b$，则$a\%b<a/2$

$a<b$时$a\%b=a$很显然，那为什么$a\ge b$时$a\%b<a/2$呢？

令$a=kb+p(0\le p<b)$，则当$a\le b$时$k\ge 1$，$kb\ge b>p$，可得$kb+p>2p$，即$a>2p$，可得$p<a/2$。

所以，对于一个数$x$，在不修改的情况下，只会被模$\log x$次，最多只会修改$m$次，所以总时间复杂度为$O((n+m)\log w)$，其中$w$为最大的$a_i$值。

注意在线段树中不仅要维护区间和，还要维护区间最大值。对于操作$2$，如果一个区间的最大值小于当前的模数，则这个区间就不用修改了。对于需要模的$a_i$，我们暴力地将每一个值都模一遍。根据上面的分析，这样处理不会TLE。

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
int n,m;
long long ans,tr[400005],mx[400005];
void  pushup(int k){
	tr[k]=tr[lc]+tr[rc];
	mx[k]=max(mx[lc],mx[rc]);
}
void build(int k,int l,int r){
	if(l==r){
		scanf("%lld",&tr[k]);
		mx[k]=tr[k];
		return;
	}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(k);
}
void pt(int k,int l,int r,int x,int y,int t){
	if(mx[k]<t) return;//判断区间最大值是否大于等于当前模数
	if(l==r){//将每一个值都模一遍
		tr[k]%=t;
		mx[k]=tr[k];
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) pt(lc,l,mid,x,y,t);
	if(y>mid) pt(rc,mid+1,r,x,y,t);
	pushup(k);
}
void ch(int k,int l,int r,int x,int t){
	if(l==r){
		mx[k]=tr[k]=t;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) ch(lc,l,mid,x,t);
	else ch(rc,mid+1,r,x,t);
	pushup(k);
}
void find(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		ans+=tr[k];
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) find(lc,l,mid,x,y);
	if(y>mid) find(rc,mid+1,r,x,y);
}
int main()
{
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1,tp,l,r,k,x;i<=m;i++){
		scanf("%d",&tp);
		if(tp==1){
			scanf("%d%d",&l,&r);
			ans=0;
			find(1,1,n,l,r);
			printf("%lld\n",ans);
		}
		else if(tp==2){
			scanf("%d%d%d",&l,&r,&x);
			pt(1,1,n,l,r,x);
		}
		else{
			scanf("%d%d",&k,&x);
			ch(1,1,n,k,x);
		}
	}
	return 0;
}