선분 트 리 템 플 릿 모드 (트 리 만 들 기 + 구간 수정 (더하기 & 곱 하기) + 구간 조회)
3070 단어 데이터 구조
#include
using namespace std;
const int N=5e4+20;
const int mod=1e9+7;
int n,m;
struct node
{
int mul,add,sum,l,r,siz;///mul add sum siz
} T[4*N+1];
void update(int k)///
{
T[k].sum=(T[k*2].sum%mod+T[k*2+1].sum%mod)%mod;
}
void pushdown2(int a,int b)
{
T[a].mul=(T[a].mul%mod*T[b].mul%mod)%mod;
T[a].add=(T[a].add*T[b].mul)%mod;
T[a].add=(T[a].add+T[b].add)%mod;
T[a].sum=(T[a].sum%mod*T[b].mul%mod)%mod;
T[a].sum=(T[a].sum+T[b].add%mod*T[a].siz)%mod;
}
void pushdown(int k)///
{
if(T[k].add==0&&T[k].mul==1)
return ;
pushdown2(k*2,k);
pushdown2(k*2+1,k);
T[k].add=0;
T[k].mul=1;
}
void build(int k,int ll,int rr)///
{
T[k].l=ll;
T[k].r=rr;
T[k].siz=rr-ll+1;
T[k].mul=1;
if(ll==rr)
{
scanf("%d",&T[k].sum);
return ;
}
int mid=(ll+rr)/2;
build(k*2,ll,mid);
build(k*2+1,mid+1,rr);
update(k);
}
void mul_interval(int k,int ll,int rr,int val)/// 1 (l,r) val
{
if(ll<=T[k].l&&T[k].r<=rr)
{
T[k].sum=(T[k].sum*val)%mod;
T[k].mul=(T[k].mul*val)%mod;
T[k].add=(T[k].add*val)%mod;
return ;
}
pushdown(k);
int mid=(T[k].l+T[k].r)/2;
if(ll<=mid)
mul_interval(k*2,ll,rr,val);
if(rr>mid)
mul_interval(k*2+1,ll,rr,val);
update(k);
}
void add_interval(int k,int ll,int rr,int val)/// 2 (l,r) val
{
if(ll<=T[k].l&&T[k].r<=rr)
{
T[k].sum=(T[k].sum+T[k].siz*val)%mod;
T[k].add=(T[k].add+val)%mod;
return ;
}
pushdown(k);
int mid=(T[k].l+T[k].r)/2;
if(ll<=mid)
add_interval(k*2,ll,rr,val);
if(rr>mid)
add_interval(k*2+1,ll,rr,val);
update(k);
}
int ask_sum(int k,int ll,int rr)/// (l,r)
{
int ans=0;
if(ll<=T[k].l&&T[k].r<=rr)
{
ans=(ans+T[k].sum)%mod;
return ans;
}
pushdown(k);
int mid=(T[k].l+T[k].r)/2;
if(ll<=mid)
ans=(ans+ask_sum(k*2,ll,rr))%mod;
if(rr>mid)
ans=(ans+ask_sum(k*2+1,ll,rr))%mod;
return ans%mod;
}
int main()
{
int t,k,n;
scanf("%d",&t);
while(t--)
{
memset(T,0,sizeof(T));
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--)
{
scanf("%d",&k);
int a,b,val;
if(k==1)/// 1
{
scanf("%d%d%d",&a,&b,&val);
mul_interval(1,a,b,val);
}
else if(k==2)/// 2
{
scanf("%d%d%d",&a,&b,&val);
add_interval(1,a,b,val);
}
else if(k==3)///
{
scanf("%d%d",&a,&b);
int ans=ask_sum(1,a,b);
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.