codeforces 722C （并查集）

题目链接：http://codeforces.com/contest/722/problem/C

题意：每次破坏一个数，求每次操作后的最大连续子串和。

思路：并查集逆向操作

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll sum[N], ans[N];

int n, a[N], b[N], father[N], r[N];

bool vis[N];

int finds(int x)

{

    if(father[x] != x)

        father[x] = finds(father[x]);

    return father[x];

}

void connect(int a,int b)

{

    a = finds(a);

    b = finds(b);

    if(r[a] > r[b])

        father[b] = a;

    else if(r[a] < r[b])

        father[a] = b;

    else

    {

        father[a] = b;

        r[b]++;

    }

    sum[a] = sum[b] = sum[a] + sum[b];

}

void init()

{

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

        father[i] = i;

    vis[0] = vis[n+1] = 1;

}

int main()

{

    scanf("%d",&n);

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

        scanf("%d",a+i);

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

        scanf("%d",b+i);

    init();

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

    {

        sum[b[i]] = a[b[i]];

        if(vis[b[i]-1])

            connect(b[i] - 1,b[i]);

        if(vis[b[i]+1])

            connect(b[i] + 1,b[i]);

        ans[i-1] = max(ans[i],sum[finds(b[i])]);

        vis[b[i]] = 1;

    }

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

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

    return 0;

}