YBTOJ 取模问题

一道特别水的线段树基础题。

不过发生了一些有意思的事情：
我最开始没算复杂度，就直接去想怎么对区间取模操作写懒标记和pushdown。
其实因为取模不会进行太多次，而且在中间可以特判结束向下递归，因此直接单点修改即可。

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define lson k<<1
#define rson k<<1|1
const int maxn=1e5+40;
int n,m;
long long sum[maxn<<2],input[maxn]; 
void build(int k,int l,int r)
{
	if(l==r)
	{
		sum[k]=input[l];
		return;
	}
	build(lson,l,mid);
	build(rson,mid+1,r);
	sum[k]=sum[lson]+sum[rson];
	return;
}	
void longchange(int k,int l,int r,int x,int y,int mo)
{
	if(l==r) 
	{
		sum[k]%=mo;
		return;
	}
	if(sum[k]<mo) return;
	if(x<=mid) longchange(lson,l,mid,x,y,mo);
	if(y>=mid+1) longchange(rson,mid+1,r,x,y,mo);
	sum[k]=sum[lson]+sum[rson];
	return;
}
void dotchange(int k,int l,int r,int x,int v)
{
	if(l==r)
	{
		sum[k]=v;
		return;	
	}
	if(x<=mid) dotchange(lson,l,mid,x,v);
	else dotchange(rson,mid+1,r,x,v);
	sum[k]=sum[lson]+sum[rson];
	return; 
}
long long longquery(int k,int l,int r,int x,int y)
{
	if(x<=l && r<=y) return sum[k];
	long long res=0;
	if(x<=mid) res+=longquery(lson,l,mid,x,y);
	if(y>=mid+1) res+=longquery(rson,mid+1,r,x,y);
	return res;	
}
int main()
{
	int l,r,x,k,y,t; 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld",&input[i]);
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&t);
		if(t==1)
		{
			scanf("%d%d",&l,&r);
			long long ans=longquery(1,1,n,l,r); 
			printf("%lld\n",ans);
		}
		if(t==2)
		{
			scanf("%d%d%d",&l,&r,&x);
			longchange(1,1,n,l,r,x);	
		}
		if(t==3)
		{
			scanf("%d%d",&k,&y);
			dotchange(1,1,n,k,y);	
		}
	}	
	return 0;
}	

YBTOJ 取模问题

原文：https://www.cnblogs.com/mint-hexagram/p/15269045.html