题解 | 动态最长连续子序列

从前往后的删除不知道怎么维护，但是从后往前的添加操作用并查集的思想就可以做了

/*
	这一发终于过了，只花了114514h.
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<chrono>
#include<random>
#include<unordered_map>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MAXN 1000010
#define debug cout<<"&"<<"\n"
//陪伴我一生的随机数呀 
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    std::uniform_int_distribution<int> distribution(l, r);
    return distribution(rng);
}
int e[MAXN],ne[MAXN],h[MAXN],w[MAXN],idx;
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int a[MAXN];
int b[MAXN];
int fa[MAXN];
int find(int x){
    if(x==fa[x])return x;
    else {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
int d[MAXN];//储存答案序列
void solve(){
	int n;
    cin>>n;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    unordered_map<int,int> mp;
    int mx=0;
    for(int i=n;i>=1;i--){
        d[i]=mx;
        int x=b[i];
        mp[x]=1;
        if(mp[x-1]){
            int y=find(x-1);
            fa[y]=fa[x];
            a[x]+=a[y];
        }
        if(mp[x+1]){
            int y=find(x+1);
            fa[y]=fa[x];
            a[x]+=a[y];
        }
        mx=max(mx,a[x]);
    }
    for(int i=1;i<=n;i++)
    cout<<d[i]<<"\n";
}

signed main(){
	ios;
	int t=1;
	// cin>>t;
	while(t--)
	solve();
	return 0;
}