本文主要是介绍hdu3074(Multiply game),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
纯模板,就是把单点更新,区间求和改为单点更新,区间求积。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 60000
#define M 1000000007
struct point
{
int x,y;
__int64 sum;
}a[N*3];
void tree(int t,int x,int y)
{
a[t].x=x;
a[t].y=y;
a[t].sum=0;
if(x==y)
return ;
int temp=2*t;
int mid=(x+y)/2;
tree(temp,x,mid);
tree(temp+1,mid+1,y);
return ;
}
void IN(int t,int x,int y)
{
if(a[t].x==a[t].y)
{
a[t].sum=y;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(x<=mid)
IN(temp,x,y);
else
IN(temp+1,x,y);
a[t].sum=a[temp].sum*a[temp+1].sum%M;
return ;
}
__int64 find(int t,int x,int y)
{
__int64 sum=1;
if(a[t].x==x&&a[t].y==y)
return a[t].sum;
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(y<=mid)
sum=sum*find(temp,x,y);
else if(x>mid)
sum=sum*find(temp+1,x,y);
else
{
sum=sum*find(temp,x,mid)%M;
sum=sum*find(temp+1,mid+1,y)%M;
}
return sum;
}
int main()
{
int m,n,i,j,k,h;
int a,b,c;
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
tree(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&m);
IN(1,i,m);
}
scanf("%d",&h);
while(h--)
{
scanf("%d%d%d",&a,&b,&c);
if(a==0)
printf("%I64d\n",find(1,b,c));
else
IN(1,b,c);
}
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 60000
#define M 1000000007
struct point
{
int x,y;
__int64 sum;
}a[N*3];
void tree(int t,int x,int y)
{
a[t].x=x;
a[t].y=y;
a[t].sum=0;
if(x==y)
return ;
int temp=2*t;
int mid=(x+y)/2;
tree(temp,x,mid);
tree(temp+1,mid+1,y);
return ;
}
void IN(int t,int x,int y)
{
if(a[t].x==a[t].y)
{
a[t].sum=y;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(x<=mid)
IN(temp,x,y);
else
IN(temp+1,x,y);
a[t].sum=a[temp].sum*a[temp+1].sum%M;
return ;
}
__int64 find(int t,int x,int y)
{
__int64 sum=1;
if(a[t].x==x&&a[t].y==y)
return a[t].sum;
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(y<=mid)
return find(temp,x,y);
else if(x>mid)
return find(temp+1,x,y);
else
{
return find(temp,x,mid)%M*find(temp+1,mid+1,y)%M;
}
}
int main()
{
int m,n,i,j,k,h;
int a,b,c;
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
tree(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&m);
IN(1,i,m);
}
scanf("%d",&h);
while(h--)
{
scanf("%d%d%d",&a,&b,&c);
if(a==0)
printf("%I64d\n",find(1,b,c));
else
IN(1,b,c);
}
}
return 0;
}
这篇关于hdu3074(Multiply game)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!