首页 > 代码库 > hdu 3074 求区间乘积
hdu 3074 求区间乘积
线段树水题
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) long long num[4*50000]; int update(int L,int R,int pos,int k,int mark) { if(L==pos&&R==pos) { num[mark]=k; return 0; } int mid=(L+R)/2; if(pos<=mid) { update(L,mid,pos,k,LL(mark)); } else { update(mid+1,R,pos,k,RR(mark)); } num[mark]=(num[LL(mark)]%1000000007)*(num[RR(mark)]%1000000007)%1000000007; return 0; } long long find(int L,int R,int left,int right,int mark) { long long sum=1; if(L==left&&R==right) { sum=num[mark]; return sum; } int mid=(L+R)/2; if(right<=mid) { sum=find(L,mid,left,right,LL(mark)); } else if(left>mid) { sum=find(mid+1,R,left,right,RR(mark)); } else { sum=(find(L,mid,left,mid,LL(mark))%1000000007)*(find(mid+1,R,mid+1,right,RR(mark))%1000000007)%1000000007; } return sum; } int main() { int n,m,T,i,j,a,b,c; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<=4*n;i++) num[i]=1; for(i=1;i<=n;i++) { scanf("%d",&a); update(1,n,i,a,1); } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&c,&a,&b); if(c==0) { printf("%lld\n",find(1,n,a,b,1)); } else { update(1,n,a,b,1); } } } return 0; }
hdu 3074 求区间乘积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。