记录编号	328956	评测结果	AAAAAAAAAA
题目名称	艺术	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.240 s
提交时间	2016-10-24 19:15:53	内存使用	6.01 MiB

#include<cstdio>
const int N=100010;
typedef long long ll;
const ll maxl=1e+13;
int p[N],n,root,s[N],fa[N],son[N][2];
ll bl[N],br[N],sum[N],k[N],b[N];
ll max(ll x,ll y){return x>y?x:y;}
ll max(ll a,ll b,ll c,ll d){return max(max(a,b),max(c,d));}
inline void update(int x){
	int l=son[x][0],r=son[x][1];
	s[x]=s[l]+s[r]+1;
	bl[x]=max(bl[l],sum[l]+k[x]+bl[r]);
	br[x]=max(br[r],sum[r]+k[x]+br[l]);
	b[x]=max(0,b[l],b[r],br[l]+k[x]+bl[r]);
	sum[x]=sum[l]+k[x]+sum[r];
}
int build(int L,int R){
	if (L>R) return 0;
	int mid=(L+R)/2;
	k[mid]=p[mid];
	son[mid][0]=build(L,mid-1);
	son[mid][1]=build(mid+1,R);
	fa[son[mid][0]]=fa[son[mid][1]]=mid;
	update(mid);
	return mid;
}
inline void rotate(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (son[z][0]==y) son[z][0]=x;else
	if (son[z][1]==y) son[z][1]=x;
	update(y);
	update(x);
}
void splay(int x){
	while (fa[x]){
		int y=fa[x],z=fa[y];
		if (!z){rotate(x);return;}
		if (x==son[y][0]) rotate(y==son[z][0]?y:x);
			else rotate(y==son[z][1]?y:x);
		rotate(x);
	}
}
inline int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int main()
{
	freopen("art.in","r",stdin);
	freopen("art.out","w",stdout);
	n=read();
	for (int i=2;i<=n+1;i++) p[i]=read();
	build(1,n+2);
	for (int i=1;i<=n;i++){
		int x=read();x++;
		splay(x);k[x]=-maxl;update(x);
		printf("%lld\n",b[x]);
	}
	return 0;
}