HDU-3074-Multiply game
http://acm.hdu.edu.cn/showproblem.php?pid=3074
求区间元素的乘积,可以更新元素,线段树即可
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Mod 1000000007
#define N 50005
int num[N];
struct cam
{
int x; //起点
int y; //终点
__int64 mul; //乘积
}list[N*4];
void build(int k,int x,int y)
{
int mid;
list[k].x=x;
list[k].y=y;
if(list[k].x==list[k].y)
{
list[k].mul=num[x];
return;
}
mid=(x+y)/2;
build(k<<1,x,mid);
build(k<<1|1,mid+1,y);
list[k].mul=(list[k<<1].mul*list[k<<1|1].mul)%Mod;
}
__int64 find(int k,int x,int y)
{
int mid;
if(list[k].x==x&&list[k].y==y)
return list[k].mul;
mid=(list[k].x+list[k].y)/2;
if(x>mid)
return find(k<<1|1,x,y);
else if(y<=mid)
return find(k<<1,x,y);
return (find(k<<1,x,mid)*find(k<<1|1,mid+1,y))%Mod;
}
void update(int k,int x,int y)
{
int mid;
if(list[k].x==x&&list[k].y==x)
{
list[k].mul=y;
return;
}
mid=(list[k].x+list[k].y)/2;
if(x<=mid)
update(k<<1,x,y);
else
update(k<<1|1,x,y);
list[k].mul=(list[k<<1].mul*list[k<<1|1].mul)%Mod;
}
int main()
{
int i,t;
int n,m;
int c,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%d %d %d",&c,&a,&b);
if(c==0)
printf("%I64d\n",find(1,a,b));
else
{
num[a]=b;
update(1,a,b);
}
}
}
return 0;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
算法-确定比赛名次(HDU-1285).rar
最短路(HDU-2544).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar
算法-排列2(HDU-1716)(包含源程序).rar
算法-排列组合(HDU-1521)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar