HDU-4027-Can you answer these queries
線段樹成段更新，n比較小，更新到每個葉子節點，注意1開根號後仍是1，不需要再更新
[cpp]
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
typedef __int64 LL;
#define N 100010
struct cam
{
int x;
int y;
LL sum;
}list[N*5];
void build(int k,int x,int y)
{
list[k].x=x;
list[k].y=y;
if(x==y)
{
scanf("%I64d",&list[k].sum);
return;
}
int mid;
mid=(x+y)/2;
build(k<<1,x,mid);
build(k<<1|1,mid+1,y);
list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
void update(int k,int x,int y)
{
if(list[k].sum==list[k].y-list[k].x+1) //1開根號仍未1，不需要更新
return;
if(list[k].x==list[k].y)
{
list[k].sum=(LL)sqrt((double)list[k].sum);
return;
}
int mid=(list[k].x+list[k].y)/2;
if(x>mid)
update(k<<1|1,x,y);
else if(y<=mid)
update(k<<1,x,y);
else
{
update(k<<1,x,mid);
update(k<<1|1,mid+1,y);
}
list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
LL find(int k,int x,int y)
{
int mid;
if(list[k].x==x&&list[k].y==y)
return list[k].sum;
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);
else
return find(k<<1,x,mid)+find(k<<1|1,mid+1,y);
}
int main()
{
int n,m,t,x,y;
int cnt=0;
while(scanf("%d",&n)!=EOF)
{
cnt++;
printf("Case #%d:\n", cnt);
build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&t,&x,&y);
if(x>y)
swap(x,y);
if(t==0)
update(1,x,y);
else
printf("%I64d\n",find(1,x,y));
}
printf("\n");
}
return 0;
}
作者：Cambridgeacm
