记录编号	330447	评测结果	AAAAAAAAAA
题目名称	艺术	最终得分	100
用户昵称	Ezoi_Vermouth	是否通过	通过
代码语言	C++	运行时间	1.871 s
提交时间	2016-10-26 16:43:57	内存使用	3.91 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;

typedef long long LL;

const int maxn=100000+10;

LL n,maxm,ans[maxn];
LL fa[maxn],dis[maxn],a[maxn],b[maxn];
LL vis[maxn];

LL find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

void mixed(int x,int y)
{
	LL fx=find(x);
	LL fy=find(y);
	fa[fy]=fx;
	dis[fx]+=dis[fy];
}

int main()
{
	freopen("art.in","r",stdin);
	freopen("art.out","w",stdout);
	maxm=-INF;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) {fa[i]=i;dis[i]=a[i];}
	for(int i=n;i>1;i--) 
	{
		vis[b[i]]=1;
		//if(i==n) {ans[i]=a[b[i]];continue;}
		if(vis[b[i]+1]) mixed(b[i],b[i]+1);
		if(vis[b[i]-1]) mixed(b[i]-1,b[i]);
		LL t=dis[find(b[i])];
		if(t>maxm) maxm=t;
		ans[i]=maxm;
	}
	for(int i=2;i<=n+1;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}