记录编号 |
231324 |
评测结果 |
AAAAAAAAAA |
题目名称 |
树 |
最终得分 |
100 |
用户昵称 |
liu_runda |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.198 s |
提交时间 |
2016-02-26 09:57:43 |
内存使用 |
1.45 MiB |
显示代码纯文本
#include<cstdio>
int lowbit(int x){
return x&-x;
}
int a[200005];
int c[200005];
int n;
void update(int pos,int w){
for(int i=pos;i<n;i+=lowbit(i))c[i]+=w;
}
int getsum(int r){
int ans=0;
for(int i=r;i>0;i-=lowbit(i))ans+=c[i];
return ans;
}
int query(int l,int r){
int sum=getsum(r)-getsum(l-1);
update((l+r)>>1,-a[(l+r)>>1]);
a[(l+r)>>1]=0;
return sum;
}
int read(){
int x;char ch;
while(ch=getchar(),ch>'9'||ch<'0');
x=ch-48;
while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
return x;
}
int main(){
freopen("treed.in","r",stdin);
freopen("treed.out","w",stdout);
n=read();
for(int i=1;i<=n;++i){
a[i]=read();
update(i,a[i]);
}
int m;m=read();
int a,b;
while(m--){
a=read();b=read();
printf("%.2lf\n",3.14*query(a,b));
}
fclose(stdin);fclose(stdout);
return 0;
}