记录编号	58232	评测结果	AAAAAAAAAA
题目名称	树	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	2.815 s
提交时间	2013-04-18 18:24:57	内存使用	7.83 MiB

#include<fstream>
#include<iomanip>
using namespace std;
ifstream fi("treed.in");
ofstream fo("treed.out");
class bb
{
public:
	int l,r,Lchild,Rchild,s;//左界右界左儿子右儿子区间高度总值
}tree[400000];
int n,m,tot,d[200000];
double ans;
void maketree(int root,int x,int y)
{
	tree[root].l=x;
	tree[root].r=y;
	if(x!=y)//非叶子节点
	{
		int mid=(x+y)/2;
		tot++;
		tree[root].Lchild=tot;
		maketree(tot,x,mid);
		tot++;
		tree[root].Rchild=tot;
		maketree(tot,mid+1,y);
		tree[root].s=tree[tree[root].Lchild].s+tree[tree[root].Rchild].s;
	}
	else//叶子节点
	{
		tree[root].s=d[x];
		tree[root].Lchild=-1;
		tree[root].Rchild=-1;
	}
}
int quest(int root,int x,int y)//查询[x,y]
{
	if(root==-1)return 0;
	if(y<tree[root].l||tree[root].r<x)return 0;//不相交区间
	if(tree[root].Lchild==-1)return tree[root].s;//叶子节点
	if(x<=tree[root].l&&tree[root].r<=y)return tree[root].s;//全覆盖区间
	//相交区间
	int sum=0;
	if(x<=tree[tree[root].Lchild].r)//左区间
		sum+=quest(tree[root].Lchild,x,y);
	if(tree[tree[root].Rchild].l<=y)//右区间
		sum+=quest(tree[root].Rchild,x,y);
	return sum;
}
void cutdown(int root,int x)
{
	if(tree[root].l>x||tree[root].r<x)return;//不相交区间
	if(tree[root].Lchild==-1)//叶子节点
	{
		tree[root].s=0;
		d[x]=0;
		return;
	}
	tree[root].s-=d[x];
	cutdown(tree[root].Lchild,x);
	cutdown(tree[root].Rchild,x);
}
int main()
{
	fi>>n;
	for(int i=1;i<=n;i++)fi>>d[i];
	tot=0;
	maketree(0,1,n);
	fi>>m;
	/*for(int i=0;i<n*2;i++)
		fo<<tree[i].l<<' '<<tree[i].r<<' '<<tree[i].s<<endl;*/
	int a,b;
	for(int i=1;i<=m;i++)
	{	
		fi>>a>>b;
		ans=quest(0,a,b);//fo<<a<<' '<<b<<' '<<ans<<endl;
		ans*=3.14;
		fo<<setprecision(2)<<setiosflags(ios::fixed)<<ans<<endl;
		cutdown(0,(a+b)/2);
	}
	return 0;
}