记录编号	89268	评测结果	AAAAAAAAAA
题目名称	树	最终得分	100
用户昵称	超级傲娇的AC酱	是否通过	通过
代码语言	C++	运行时间	1.083 s
提交时间	2014-02-28 21:56:21	内存使用	0.27 MiB

#include<cstdio>
#include<vector>
using namespace std;
const double Value=3.14;
struct SgTree
{
	int L,R;
	SgTree *LeftChild,*RightChild;
	int num;
};
vector<int>A;
SgTree *ConstNode=new SgTree;
SgTree *Root=new SgTree;
void Build(int,int,SgTree *);
int Sum(int,int,SgTree *);
void Cut(int,SgTree *);
int main()
{
	int n,m,i,x,y;
	freopen("treed.in","r",stdin);
	freopen("treed.out","w",stdout);
	scanf("%d",&n);
	A.resize(n);
	for(i=0;i<n;i++)
		scanf("%d",&A[i]);
	Build(0,n-1,Root);
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%.2lf\n",Sum(x-1,y-1,Root)*Value);
		Cut((x-1+y-1)/2,Root);
	}
	return 0;
}
void Build(int l,int r,SgTree *Node)
{
	Node->L=l;Node->R=r;
	if(l==r)
	{
		Node->LeftChild=ConstNode;
		Node->RightChild=ConstNode;
		Node->num=A[l];
	}
	else
	{
		Node->LeftChild=new SgTree;
		Node->RightChild=new SgTree;
		Build(l,(l+r)/2,Node->LeftChild);
		Build((l+r)/2+1,r,Node->RightChild);
		Node->num=Node->LeftChild->num+Node->RightChild->num;
	}
}
int Sum(int l,int r,SgTree *Node)
{
	if(l==Node->L&&Node->R==r)
		return Node->num;
	else
	{
		int Mid=(Node->L+Node->R)/2;
		if(l>Mid)return Sum(l,r,Node->RightChild);
		if(r<=Mid)return Sum(l,r,Node->LeftChild);
		if(l<=Mid&&Mid<r)
			return Sum(l,Mid,Node->LeftChild)+Sum(Mid+1,r,Node->RightChild);
	}
}
void Cut(int pos,SgTree *Node)
{
	if(pos==Node->L&&pos==Node->R)
		Node->num=0;
	else
	{
		int Mid=(Node->L+Node->R)/2;
		if(pos<=Mid)
			Cut(pos,Node->LeftChild);
		if(pos>Mid)
			Cut(pos,Node->RightChild);
		Node->num=Node->LeftChild->num+Node->RightChild->num;
	}
}