CF722C-Destroying-Array题解

发布于 2019-11-09  544 次阅读

题目描述

点我传送

You are given an array consisting of n non-negative integers a1, a2, ..., an.

You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 to n defining the order elements of the array are destroyed.

After each element is destroyed you have to find out the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum possible. The sum of elements in the empty segment is considered to be 0.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the length of the array.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

The third line contains a permutation of integers from 1 to n — the order used to destroy elements.

Output

Print n lines. The i-th line should contain a single integer — the maximum possible sum of elements on the segment containing no destroyed elements, after first i operations are performed.

Note

Consider the first sample:

  1. Third element is destroyed. Array is now 1 3  *  5. Segment with maximum sum 5 consists of one integer 5.
  2. Fourth element is destroyed. Array is now 1 3  *   * . Segment with maximum sum 4 consists of two integers 1 3.
  3. First element is destroyed. Array is now  *  3  *   * . Segment with maximum sum 3 consists of one integer 3.
  4. Last element is destroyed. At this moment there are no valid nonempty segments left in this array, so the answer is equal to 0.

以下内容来自bing翻译

‎您得到一个由‎‎n‎‎个非负整数组成的数组‎a1‎，a‎2‎，...， ‎n.
‎您将逐个销毁数组中的整数。因此，将为您提供从‎‎1‎‎到‎‎n‎‎的整数排列，定义数组的顺序元素将被销毁。‎
‎销毁每个元素后，您必须找出数组的段，以便它不包含任何已销毁的元素，并且其元素的总和是尽可能可能的。空段中的元素之和被视为‎‎0‎‎。

题解

正着做不好处理，那我们考虑倒着处理。

我们先假定这个序列是空的，之后每次把摧毁的数倒着加入序列，同时把它左右两边的数与它合并，顺便求一个$\max$，最后倒序输出答案便可。

用并查集实现。

代码

#include <iostream>
#include <stack>
using namespace std;

const int maxn = 100005;
int n, m, a[maxn], broken[maxn], fa[maxn];
long long sum[maxn];
bool tag[maxn];

stack<long long> ans; //记录答案，因为是倒序输出，用栈可以方便点

int find(int x) //并查集
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (register int i = 1; i <= n; i++)
    {
        fa[i] = i;
        cin >> a[i];
        sum[i] = a[i];    //初始每个节点是独立的
    }

    for (register int i = 1; i <= n; i++)
        cin >> broken[i]; //被摧毁的数

    ans.push(0);  //一开始序列是0
    long long cnt = 0;
    for (register int i = n; i > 1; i--)
    {
        int now = broken[i], fnow = find(now);
        tag[broken[i]] = true;    //这个元素被加入了序列
        if (now > 1 and tag[now - 1])  //判断左端点
        {
            int fz = find(now - 1);   //并查集合并
            if (fz != fnow)
            {
                sum[now] += sum[fz];  //合并
                sum[fz] = 0;  //清零
                fa[fz] = now;
            }
        }
        if (now < n and tag[now + 1])  //判断右端点
        {
            int fz = find(now + 1);  //并查集合并
            if (fz != fnow)
            {
                sum[now] += sum[fz]; //合并
                sum[fz] = 0;  //清零
                fa[fz] = now;
            }
        }
        cnt = max(cnt, sum[now]);  //取最大值
        ans.push(cnt);
    }
    while (n--)  //倒序输出答案
    {
        cout << ans.top() << endl;
        ans.pop();
    }
    return 0;
}

$finish$