首页 > 其他 > 详细

CF438D The Child and Sequence

时间:2020-09-17 09:36:12      阅读:15      评论:0      收藏:0      [点我收藏+]

标签:turn   -cp   %d   scanf   -s   -a   

CF438D The Child and Sequence

题意:给定一个序列,支持三种操作;
1,单点修改
2,区间查询
3,区间取模
难点在于区间取模,思考使一个数取模变为1时间复杂度是log的,因此记录一个最大值,当模数<=最大值时,暴力取模;

#include<iostream>
#include<cstdio>
#define l(o) (o<<1)
#define r(o) ((o<<1)|1)
#define mid ((l+r)>>1)
#define LL long long
using namespace std;
const int N=1e5+7;
int n,m,ans;
LL a[N],sum[N<<2],maxn[N<<2];

void up(int o){
	sum[o]=sum[l(o)]+sum[r(o)];
	maxn[o]=max(maxn[l(o)],maxn[r(o)]);
}

void build(int o,int l,int r){
	if(l==r){
		scanf("%d",&sum[o]);
		maxn[o]=sum[o];
		return;
	}
	build(l(o),l,mid);
	build(r(o),mid+1,r);
	up(o);
}

void change(int o,int l,int r,int k,int val){
	if(l==r){
		sum[o]=maxn[o]=val;
		return;
	}
	if(k<=mid) change(l(o),l,mid,k,val);
	if(k>mid) change(r(o),mid+1,r,k,val);
	up(o);
}

void cmod(int o,int l,int r,int L,int R,int p){
	if(maxn[o]<p) return;
	if(l==r){
		sum[o]%=p;
		maxn[o]%=p;
		return;
	}
	if(L<=mid) cmod(l(o),l,mid,L,R,p);
	if(R>mid) cmod(r(o),mid+1,r,L,R,p);
	up(o);
}

LL ask(int o,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return sum[o];
	}
	LL res=0;
	if(L<=mid) res=ask(l(o),l,mid,L,R);
	if(R>mid) res+=ask(r(o),mid+1,r,L,R);
	return res;
}

int main(){
	scanf("%d%d",&n,&m);
//	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int x,y,opt,val;
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1){
			cout<<1LL*ask(1,1,n,x,y)<<"\n";
		}
		if(opt==2){
			scanf("%d",&val);
			cmod(1,1,n,x,y,val);
		}
		if(opt==3){
			change(1,1,n,x,y);
		}
	}
}

CF438D The Child and Sequence

标签:turn   -cp   %d   scanf   -s   -a   

原文:https://www.cnblogs.com/Aswert/p/13683019.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号