一个板板的带权并查集

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define foR(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=1e6+5;
int n,a[N],b[N];
int fa[N],sum[N];
inline void init() {For(i,1,n) fa[i]=i,sum[i]=a[i];}
inline int find(int x) {
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline void Union(int x,int y) {
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	fa[fx]=fy;
	sum[fy]+=sum[fx];
	return; 
}
int ans[N];
bool tag[N];//标记是否活着 
signed main() {
	cin>>n;
	For(i,1,n) scanf("%lld",&a[i]);
	For(i,1,n) scanf("%lld",&b[i]);
	init();
	ans[n]=0;
	foR(i,n,1) {
		int x=b[i];
		if(tag[x-1]) Union(x,x-1);
		if(tag[x+1]) Union(x,x+1);
		tag[x]=true;
		ans[i-1]=max(ans[i],sum[find(x)]);
	}
	For(i,1,n) printf("%lld\n",ans[i]);
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000005;

int n , a[ N ] , b[ N ];
bool alive[ N ];
int fa[ N ] , sz[ N ] , ans[ N ];

int find( int x )
{
	if( x == fa[ x ] )
		return x;

	return fa[ x ] = find( fa[ x ] );
}

void unionn( int x , int y )
{
	int fx = find( x ) , fy = find( y );
	sz[ fy ] += sz[ fx ];
	fa[ fx ] = fy;
}

signed main() 
{
	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 , sz[ i ] = a[ i ];

	int mx = 0;
	for( int t = n ; t >= 1 ; t -- )
	{
		int i = b[ t ];
		alive[ i ] = true;
		if( alive[ i - 1 ] )
			unionn( i , i - 1 );
		if( alive[ i + 1 ] )
			unionn( i , i + 1 );
		mx = max( mx , sz[ find( i ) ] );
		ans[ t - 1 ] = mx;
	} 

	for( int i = 1 ; i <= n ; i ++ )
		cout << ans[ i ] << endl;

	return 0;
}