HDu 3074 Multiply game(セグメントツリー)
1593 ワード
タイトルリンク:クリックしてリンクを開く
単一ポイントで区間クエリーを変更します.
pushupの場合、親ノードの値は2つのサブノードに乗算されます.
updateではそのリーフノードを変更し、pushupを上げるだけです.
コード:
単一ポイントで区間クエリーを変更します.
pushupの場合、親ノードの値は2つのサブノードに乗算されます.
updateではそのリーフノードを変更し、pushupを上げるだけです.
コード:
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
#define MAX 50010
#define mod 1000000007
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
ll sum[MAX<<2];
void pushup(int rt){
sum[rt]=(sum[rt<<1]*sum[rt<<1|1])%mod;
}
void build(int l,int r,int rt){
if(l==r){
scanf("%I64d",&sum[rt]);
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int l,int r,int rt,int p,ll d){
if(l==r){
sum[rt]=d;
return ;
}
int m=(l+r)>>1;
if(m>=p) update(lson,p,d);
else update(rson,p,d);
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
if(L<=l&&R>=r) return sum[rt];
int m=(l+r)>>1;
ll res=1;
if(m>=L){ res*=query(lson,L,R); res%=mod;}
if(m<R) {res*=query(rson,L,R); res%=mod;}
return res;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d",&n);
build(1,n,1);
scanf("%d",&m);
int t,x,y;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&t,&x,&y);
if(t){
update(1,n,1,x,y);
}
else printf("%I64d
",query(1,n,1,x,y));
}
return 0;
}