封印序列

题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,…,a_n$。

其中的所有元素将被逐个封印。

具体封印顺序可以用一个 $1∼n$ 的排列 $b_1,b_2,…,b_n$描述;

第 $i$ 个被封印的元素即为 $a_{bi}$ 。

你需要完成 $n$ 个任务（编号 $1∼n$），其中第 $i$ 个任务是：对于完成前 $i$ 次封印的序列，请你找到序列中的一个连续子序列（可以为空），使得该子序列不含任何被封印的元素，且子序列内各元素之和尽可能大，输出这个子序列元素和的最大可能值。

空序列的元素和视为 $0$。

输入格式

第一行包含整数 $n$。

第二行包含 $a_1,a_2,…,a_n$。

第三行包含 $b_1,b_2,…,b_n$。

输出格式

共 $n$ 行，第 $i$ 行输出第 $i$ 个任务的结果。

数据范围

前 $4$ 个测试点满足 $1\leq n\leq 10$。
所有测试点满足 $1\leq n\leq 1e5，0\leq a_i\leq 1e9，b_1∼b_n$ 是一个 $1∼n$ 的排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
输入样例1：
4
1 3 2 5
3 4 1 2
输出样例1：
5
4
3
0
输入样例2：
5
1 2 3 4 5
4 2 3 5 1
输出样例2：
6
5
5
1
0
输入样例3：
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6
输出样例3：
18
16
11
8
8
6
6
0

解题思路

从左往右为封印一个元素，从右往左则为插入一个元素，故本体可以视为不断插入元素，求取最大子段和。
插入一个元素有三种可能，孤立/与左边相连/与右边相连，容易想到可以用并查集来维护；
这里采取的序列并查集较为特殊，每个区间以右端点为代表节点（父节点）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

int a[N],b[N],p[N]; //分别记录元素、删除顺序、并查集
LL ans[N],s[N]; //ans记录每次的最大字段和、s记录最大值
bool st[N]; //st判断插入与否

int n;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    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) p[i] = i;
    for(int i = n; i ; -- i) {
        int k = b[i];
        st[k] = true, s[k] = a[k];
        if(st[k+1]) s[find(k+1)] += s[k], p[k] = find(k+1);
        if(st[k-1]) s[find(k)] += s[k-1], p[k-1] = find(k);
        ans[i-1] = max(ans[i],s[find(k)]);
    }
    for(int i = 1; i <= n; ++ i) cout << ans[i] << endl;
    return 0;
}