1361. 树

★ 输入文件：treed.in 输出文件：treed.out 简单对比
时间限制：1 s 内存限制：128 MB

【问题描述】

在一个凉爽的夏夜，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不是π)

【输入格式】

第一行，一个整数n。

第二行，共n个整数，表示每棵树的高度。

第三行，一个整数m，表示共m个区间。

以下m行，每个区间[x,y]的左右端点x,y。

【输出格式】

共m行，每行一个数，表示每个区间的木材量。

结果精确到小数点后两位。

【输入样例】

1 2 3 4 5

1 4

2 4

【输出样例】

31.40

21.98

【数据规模】

对于30%的数据，有n≤5000,m≤5000;

对于100%的数据，有n≤200000,m≤200000;

【样例解释】

第一次砍[1,4]的树后，森林变为：1 0 3 4 5

呵！问题来了为什么要做这么无聊的题QAQ 就是一个线段树而已嘛

每一次取一下区间和然后把(x+y)/2全部变成0

♪(^∇^*)

#include<bits/stdc++.h>

#define LL long long

#define maxn 200005

#define ls (p*2)

#define rs (p*2+1)

#define mid (l+r>>1)

#define lson ls,l,mid

#define rson rs,mid+1,r

using namespace std;

int n,m;

int a[maxn];

LL sum[maxn<<];

void build(int p,int l,int r)

{

    if(l==r)

    {

        sum[p]=a[l];

        return;

    }

    build(lson);

    build(rson);

    sum[p]=sum[ls]+sum[rs];

    return;

}

LL Sum(int p,int l,int r,int s,int t)

{

    if(s>r||t<l)

        return ;

    if(s<=l&&r<=t)

        return sum[p];

    return Sum(lson,s,t)+Sum(rson,s,t);

}

void Change(int p,int l,int r,int posx)

{

    if(l==r)

    {

        sum[p]=;

        return;

    }

    if(posx<=mid)

        Change(lson,posx);

    else

        Change(rson,posx);

    sum[p]=sum[ls]+sum[rs];

    return;

}

int Main()

{

    freopen("treed.in","r",stdin);

    freopen("treed.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    build(,,n);

    scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

        int l,r;

        scanf("%d%d",&l,&r);

        double ans=Sum(,,n,l,r);

        printf("%.2f\n",ans*3.14);

        Change(,,n,mid);

    }

}

int hh=Main();

int main(){;}

rabbit

cogs 1361. 树 线段树

1361. 树

cogs 1361. 树线段树