题目
题目描述 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$不是$\pi$）。
输入描述 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;
Solution
这是我见过的废话最多的题目之一。。。。
树状数组或线段树均可以过，反正都是单点修改区间查询即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
int N, M;
int a[MAXN], c[MAXN];
inline int lowbit(int x)
{
return x & (-x);
}
inline void Modify(int pos, int val)
{
for (register int i = pos; i <= N; i += lowbit(i)) c[i] += val;
}
inline int query(int pos)
{
int ret = 0;
for (register int i = pos; i >= 1; i -= lowbit(i)) ret += c[i];
return ret;
}
int main(int argc, char **argv)
{
ios::sync_with_stdio(false);
cin >> N;
for (register int i = 1; i <= N; ++i)
{
cin >> a[i];
Modify(i, a[i]);
}
cin >> M;
while (M--)
{
int l, r;
cin >> l >> r;
printf("%.2lf\n",3.14 * (query(r) - query(l - 1)));
Modify((l + r) >> 1, -a[(l + r) >> 1]);
a[(l + r) >> 1] = 0;
}
return 0;
}
