WA on #2~#10

Link

Code

#include<bits/stdc++.h>
#define mid ((pl+pr)>>1)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
typedef long long ll;

const int Maxn=1e5+7,Mod=1e9+7;
int n,m;
int a[Maxn];
ll t[Maxn<<2][2];
//t[0]:维护区间平方和，t[1]：维护区间和
//a=t2(l,r)/len,S=t1(l,r)/len
//s^2=S-a^2

ll qpow(int a,int b=Mod-2){
	if(b==1)return a;
	ll tmp=qpow(a,b>>1);
	if(b&1)return tmp*a%Mod*tmp%Mod;
	return tmp*tmp%Mod;
}

void Build(int p,int pl,int pr){
	if(pl==pr)return t[p][0]=a[pl]*a[pl]%Mod,t[p][1]=a[pl],void();
	Build(ls(p),pl,mid);
	Build(rs(p),mid+1,pr);
	t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%Mod;
	t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%Mod;
}
void Update(int x,ll k,int p,int pl,int pr){
	if(x==pl&&x==pr){
		t[p][0]=k*k%Mod,t[p][1]=k;
		return;
	}
	if(x<pl||pr<x)return;
	Update(x,k,ls(p),pl,mid);
	Update(x,k,rs(p),mid+1,pr);
	
	t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%Mod;
	t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%Mod;
}
ll Query(int l,int r,int op,int p,int pl,int pr){
	if(l<=pl&&pr<=r)return t[p][op]%Mod;
	if(r<pl||pr<l)return 0;
	return (Query(l,r,op,ls(p),pl,mid)+
		Query(l,r,op,rs(p),mid+1,pr))%Mod;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i],a[i]%=Mod;
	Build(1,1,n);
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		x%=Mod,y%=Mod;
		if(op==1)Update(x,y,1,1,n);
		else{
			ll inv=qpow(y-x+1);
			ll s1=Query(x,y,0,1,1,n)*inv%Mod;
			ll s2=Query(x,y,1,1,1,n)*inv%Mod;
			cout<<((s1-qpow(s2,2))%Mod+Mod)%Mod<<'\n';
		}
	}
	return 0;
}