1369 xth 砍树
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 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 521 42 4 样例输出 Sample Output
31.40
21.98 数据范围及提示 Data Size & Hint
对于30%的数据，有n ≤ 5000,m ≤ 5000;
对于100%的数据，有n ≤ 200000,m ≤ 200000;//单点修改，区间询问 #include#include #include #define maxn 200010using namespace std;int n,m,ans,x,y;struct node{ int l,r,dis,next; double sum;}tree[maxn<<2];inline int init(){ int x(0),f(1);char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}void build(int now,int l,int r){ tree[now].l=l;tree[now].r=r; if(l==r) { tree[now].dis=init(); tree[now].sum=tree[now].dis*3.14; return; } int mid=(l+r)>>1; build(now<<1,l,mid);build(now<<1|1,mid+1,r); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;}double query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) return tree[now].sum; int mid=(tree[now].l+tree[now].r)>>1; if(l>mid) return query(now<<1|1,l,r); else if(r<=mid) return query(now<<1,l,r); else return query(now<<1,l,mid)+query(now<<1|1,mid+1,r);}void change(int now,int pos){ if(tree[now].l==tree[now].r) { tree[now].sum=0; return; } int mid=(tree[now].l+tree[now].r)>>1; if(pos>mid) change(now<<1|1,pos); else if(pos<=mid) change(now<<1,pos); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; }int main(){ n=init(); build(1,1,n);m=init(); for(int i=1;i<=m;i++) { x=init();y=init(); printf("%.2lf\n",query(1,x,y)); change(1,(x+y)>>1); } return 0;}