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

#include <fstream>
#include <iomanip>
using namespace std;
ifstream fi("treed.in");
ofstream fo("treed.out");
int n,m,total=1,z,d[200001];
class t
{
public:
	int l,r,lc,rc,s;
};
t a[400001];
void maketree(int x,int y)
{
	int mid,root;
	root=total;
	a[root].l=x;a[root].r=y;
	if (x<y)
	{
		mid=x+y;mid=mid/2;
		a[root].lc=++total;maketree(x,mid);
		a[root].rc=++total;maketree(mid+1,y);
		a[root].s=a[a[root].lc].s+a[a[root].rc].s;
	}else
	{
		a[root].s=d[x];
		a[root].lc=-1;a[root].rc=-1;
	}
}
int sum(int x,int y,int root)
{
	int s1,s2;
	if (x>a[root].r||y<a[root].l) return 0;
	if (x<=a[root].l&&y>=a[root].r) return a[root].s;
	s1=sum(x,y,a[root].rc);
	s2=sum(x,y,a[root].lc);
	return s1+s2;
}
void add(int x,int root)
{
	if (a[root].l>x||a[root].r<x) return;
	if (a[root].lc!=-1) add(x,a[root].lc);else a[root].s=0;
	if (a[root].rc!=-1) add(x,a[root].rc);
	if (a[root].lc!=-1) a[root].s=a[a[root].lc].s+a[a[root].rc].s;
}
void init()
{
	int i,x,y;
	double ans;
	fi>>n;
	for (i=1;i<=n;i++) fi>>d[i];
	maketree(1,n);
	fi>>m;
	for (i=1;i<=m;i++)
	{
		fi>>x>>y;z=x+y;z=z/2;
		ans=sum(x,y,1);ans=ans*3.14;
		fo<<setprecision(2)<<std::fixed<<ans<<endl;
		add(z,1);
	}
}
int main()
{
	init();
	return 0;
}