C. Destroying Array 并查集，逆向思维

用并查集维护线段，从后往前枚举没个删除的位置id[i]

那么，现在删除了这个，就是没有了的，但是上一个id[i + 1]就是还没删除的。

然后现在进行合并

int left = id[i + 1];(相当于每次都加入一个元素a[left])

它在这个位置，如果能和左右的合并，就是左右邻居都有元素，那么当然是合并最好，因为元素都是大于0的，越长越好。

合并的时候再记录一个数组sum[pos]表示以这个为根的总和是多少。
按并查集的思路更新整个并查集即可、

注意一点的就是，

要求ans[i]

那么ans[i + 1]是在没有id[i + 1]这个元素的前提下的最大值，现在有了这个元素，但是不见得会变大。

所以

ans[i] = max(ans[i + 1], sum[find(id[i + 1)]);

要和前一个比较一下

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  + ;

int fa[maxn];

LL sum[maxn];

int find(int u) {

    if (fa[u] == u) return fa[u];

    else return fa[u] = find(fa[u]);

}

void merge(int x, int y) {

    x = find(x);

    y = find(y);

    if (x != y) {

        fa[y] = x;

        sum[x] += sum[y];

    }

}

int a[maxn];

int id[maxn];

bool has[maxn];

LL ans[maxn];

void work() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; ++i) fa[i] = i;

    for (int i = ; i <= n; ++i) scanf("%d", &a[i]);

    for (int i = ; i <= n; ++i) scanf("%d", &id[i]);

    ans[n] = ;

    for (int i = n - ; i >= ; --i) {

        int left = id[i + ];

        sum[left] = a[left];

        if (has[left + ]) {

            merge(left, left + );

        }

        if (has[left - ]) {

            merge(left, left - );

        }

        ans[i] = max(ans[i + ], sum[find(left)]);

        has[left] = ;

    }

    for (int i = ; i <= n; ++i) {

        printf("%I64d\n", ans[i]);

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    work();

    return ;

}

巴特西

C. Destroying Array 并查集，逆向思维

最新文章

热门文章