Subtask 1:

Duyệt trâu trong ~O(n^2)~

Subtask 2:

Thay vì làm xuôi từng thao tác một, ta có thể làm ngược lại từ thao tác cuối. Bài toán lúc này trở thành với mỗi bước, thêm một vị trí ~p_i~ vào dãy rồi tìm ra đoạn con liên tiếp dài nhất.

Do ~a_i > 0~, ta có thể sử dụng DSU, khi thêm vị trí ~pos~ vào dãy thì lần lượt hợp hai đoạn liên thông (hay ở đây là dãy con liên tiếp) chứa vị trí ~p-1~ và ~p+1~ với ~p~ (nếu hai vị trí này tồn tại và đã được thêm vào trước đó), sau đó cập nhật kết quả với tổng của vùng liên thông mới thêm vào.

Subtask 3:

Làm tương tự như subtask 2, tuy nhiên do ~a_i~ có thể âm nên trong DSU của ta cần lưu thêm ~4~ thông tin là:

• ~sum~ - tổng giá trị của đoạn liên thông.

• ~pref~ - prefix có tổng lớn nhất của đoạn liên thông.

• ~suf~ - suffix có tổng lớn nhất của đoạn liên thông.

• ~best~ - giá trị của đoạn con có tổng lớn nhất của đoạn liên thông.

Như vậy, khi hợp hai đoạn có cha lần lượt là ~u~ và ~v~ ~(u < v)~, ta có thể update cho đoạn mới như sau:

best[u] = max ({best[u],best[v],suf[u]+pref[v]});
pref[u] = max (pref[u],sum[u]+pref[v]);
suf[u] = max (suf[v],sum[v] + suf[u]);
sum[u] += sum[v];

Sau mỗi lần update, ta cập nhật kết quả với ~best[u]~.

Độ phức tạp: ~O(n)~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int n;
int a[N];
int p[N];
int ans[N];
int res = -1e18;
bool use[N];
struct dsu {
    int n;
    vector<int> f;
    vector<int> pref,suf,best,sum;
    dsu () {}
    dsu (int n) : n(n) {
        f.resize(n+5);
        pref.resize(n+5);
        suf.resize(n+5);
        best.resize(n+5);
        sum.resize(n+5);
        for (int i=1; i<=n; i++) {
            f[i] = i;
            pref[i] = a[i];
            suf[i] = a[i];
            best[i] = a[i];
            sum[i] = a[i];
        }
    }
    void join (int u, int v) {
        u = find (u);
        v = find (v);
        if (u == v) return;
        best[u] = max ({best[u],best[v],suf[u]+pref[v]});
        pref[u] = max (pref[u],sum[u]+pref[v]);
        suf[u] = max (suf[v],sum[v] + suf[u]);
        sum[u] += sum[v];
        f[v] = u; 
        res = max (res,best[u]);
    }
    int find (int u) {
        if (f[u] == u) return u;
        return f[u] = find (f[u]);
    }
    int get (int u) {
        return best[find(u)];
    }
}d;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    for (int i=1; i<=n; i++) {
        cin >> p[i];
    }
    d = dsu (n);
    for (int i=n; i>=1; i--) {
        int pos = p[i];
        res = max (res,a[pos]);
        use[pos] = true;
        if (use[pos+1]) d.join(pos,pos+1);
        if (use[pos-1]) d.join(pos-1,pos);
        ans[i] = res;
    }
    for (int i=1; i<=n; i++) cout << ans[i] << '\n';
}