codeforces 722C（带权并查集+反向思维）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
ll a[N],b[N],ans[N],w[N];
bool used[N];
struct DSU{
    vector<int> data;

    void init(int n){data.assign(n,-1);}

    bool unionSet(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            //if(data[y] < data[x]) swap(x,y);//使用带权并查集时注释掉
            data[x]+=data[y];
            data[y]=x;
        }
        return x != y;
    }

    bool same(int x,int y) {return root(x)==root(y);}

    int root(int x) {return data[x] < 0 ? x : data[x]=root(data[x]);}

    int Size(int x) {return -data[root(x)];}
};
void solve(){
    mst(used,false);
    int n;cin>>n;
    DSU d;
    d.init(n+5);
    rep(i,1,n+1) cin>>a[i];
    rep(i,1,n+1) cin>>b[i];
    ans[n]=0;
    rrep(i,n,2){
        int pos=b[i];
        w[pos]=a[pos];//带权并查集
        if(used[pos-1]){//前面有数就合并
            int x=d.root(pos);
            int y=d.root(pos-1);
            d.unionSet(y,x);
            w[y]+=w[x];//权值相加
        }
        if(used[pos+1]){//后面有数就合并
            int x=d.root(pos);
            int y=d.root(pos+1);
            d.unionSet(y,x);
            w[y]+=w[x];//权值相加
        }
        used[pos]=true;
        ans[i-1]=max(ans[i],w[d.root(pos)]);//求max
    }
    rep(i,1,n+1) cout<<ans[i]<<endl;
}
int main(){
    IOS;
    solve();
    return 0;
}