题目描述 Description
在一个凉爽的夏夜，xth 和 rabbit 来到花园里砍树。为啥米要砍树呢？是这样滴，
小菜儿的儿子窄森要出生了。Xth这个做伯伯的自然要做点什么。于是他决定带着
rabbit 去收集一些木材，给窄森做一个婴儿车……（xth 早就梦想着要天天打菜儿
他儿窄森的小 pp，到时候在婴儿车里安装一个电子遥控手臂，轻轻一按，啪啪
啪……“乌卡卡——”xth 邪恶滴笑了，“不要告诉 rabbit，她会说我缺德的……”
xth 如是说）。
花园里共有n棵树。为了花园的整体形象，rabbit 要求 xth只能在m个区域砍伐，我
们可以将这m个区域看成m个区间，树的间距相等，都是1，我们将每个区间设为
[x, y]。那么长度为k的区间中就有k棵树。树木的高度不等。现在 xth 想测量一下，
每个区间树木砍伐后所得的木材量是多少，而且每次测量后他都会砍下标号为
(x+y)/2
的那棵作为纪念。以方便他安排人手。(同一个区间的树木可以重复砍伐，我们认
为被砍过的树木高度为0)
每棵树的木材量=树的高度∗ 3.14（注意是3.14不是π）。
输入描述 Input Description
第一行，一个整数n。
第二行，共n个整数，表示每棵树的高度。
第三行，一个整数m，表示共m个区间。
以下m行，每个区间[x, y]的左右端点x, y。
输出描述 Output Description
共m行，每行一个数，表示每个区间的木材量。
结果精确到小数点后两位。
样例输入 Sample Input
5
1 2 3 4 5
2
1 4
2 4
样例输出 Sample Output
31.40
21.98
数据范围及提示 Data Size & Hint
对于30%的数据，有n ≤ 5000,m ≤ 5000;
对于100%的数据，有n ≤ 200000,m ≤ 200000;
#include<cstring> #include<iostream> #include<cstdio> #define lson l,m,now*2 #define rson m+1,r,now*2+1 #define lch now*2 #define rch now*2+1 #define m (l+r)/2 #define M 200010 using namespace std; int sum[M*4],n,p; int read() {char c=getchar();int num=0,flag=1;while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}return num*flag; } void push_up(int now) {sum[now]=sum[lch]+sum[rch]; } void build(int l,int r,int now) {if(l==r){sum[now]=read();return;}build(lson);build(rson);push_up(now); } int query(int x,int y,int l,int r,int now) {if(l>=x&&r<=y)return sum[now];int ans=0;if(x<=m)ans+=query(x,y,lson);if(y>m)ans+=query(x,y,rson);return ans; } void change(int pos,int l,int r,int now) {if(l==r){sum[now]=0;return;}if(pos<=m)change(pos,lson);else change(pos,rson);push_up(now); } int main() {n=read();build(1,n,1);p=read();for(int i=1;i<=p;i++){int x=read(),y=read();double ans=(double)query(x,y,1,n,1)*3.14;printf("%.2lf\n",ans);change((x+y)/2,1,n,1);}return 0; }
