【模板】维护序列2(线段树)

内网传送门

【题目分析】

取模取挂可真是令人质壁分离。。。。

两两乘积和可以直接用两个区间的区间和相乘再加上两个区间各自的乘积和得到,而相邻乘积和直接两段相加再加上左区间右端点与右区间左端点乘积就好了。

注意+MOD%MOD

【代码~】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=1e5+10;
const LL MOD=1000000007;

LL n,q;
LL a[MAXN];
struct Tree{
	LL l,r;
	LL ll,rr;
	LL mul,sum,summ;
	void init(){l=r=ll=rr=sum=summ=mul=0;}
	friend inline Tree operator+(const Tree &a,const Tree &b){
		Tree ret;
		if(a.ll==a.rr&&!a.ll){
			ret=b;
			return ret;
		}
		ret.l=a.l,ret.r=a.r;
		ret.ll=a.ll,ret.rr=b.rr;
		ret.mul=((((a.summ*b.summ)%MOD+a.mul)%MOD+b.mul)%MOD+MOD)%MOD;
		ret.sum=(((a.sum+b.sum)%MOD+a.rr*b.ll%MOD)%MOD+MOD)%MOD;
		ret.summ=((a.summ+b.summ)%MOD+MOD)%MOD;
		return ret;
	}
}tr[MAXN<<2],ans;

LL Read(){
	LL i=0,f=1;
	char c=getchar();
	for(;(c>'9'||c<'0')&&c!='-';c=getchar());
	if(c=='-')  f=-1,c=getchar();
	for(;c>='0'&&c<='9';c=getchar())  i=(i<<3)+(i<<1)+c-'0';
	return i*f;
}

#define lc (root<<1)
#define rc (root<<1|1)
void push_up(LL root){tr[root]=tr[lc]+tr[rc];}

void build(LL root,LL l,LL r){
	tr[root].l=l,tr[root].r=r;	
	if(l==r){
		tr[root].ll=tr[root].rr=tr[root].summ=a[l];
		return ;
	}
	LL mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	push_up(root);
}

void update(LL root,LL l,LL r,LL x,LL key){
	if(l==r){
		tr[root].ll=tr[root].rr=tr[root].summ=key;
		return ;
	}
	LL mid=(l+r)>>1;
	if(x<=mid)  update(lc,l,mid,x,key);
	else  update(rc,mid+1,r,x,key);
	push_up(root);
}

void query(LL root,LL l,LL r,LL L,LL R){
	if(l>R||r<L)  return ;
	if(L<=l&&r<=R){
		ans=ans+tr[root];
		return ;
	}
	LL mid=(l+r)>>1;
	if(R<=mid)  query(lc,l,mid,L,R);
	else{
		if(L>mid)  query(rc,mid+1,r,L,R);
		else  query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R);
	}
}

int main(){
	n=Read(),q=Read();
	for(LL i=1;i<=n;++i)  a[i]=Read();
	build(1,1,n);

	while(q--){
		char cz[5];
		scanf("%s",cz);
		LL l=Read(),r=Read();
		if(cz[0]=='M')  update(1,1,n,l,r);
		else{
			ans.init();
			query(1,1,n,l,r);
			if(cz[0]=='A')  cout<<ans.sum<<'\n';
			else  cout<<ans.mul<<'\n';
		}
	}
}

 

上一篇:Vue事件总线(EventBus)使用详细介绍


下一篇:线段树