Codeforces722C题解

发表于

并查集 + 乱搞

Codeforces 722C Destroying Array题解

题目描述

You are given an array consisting of n n non-negative integers $a_{1},a_{2},…,a_{n}$
You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 1 to n 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$.

输入格式

The first line of the input contains a single integer n ( 1<=n<=100000 1<=n<=100000 ) — the length of the array.

The second line contains $ n $ integers $a_{1},a_{2},…,a_{n}$

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

输出格式

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.

INPUT & OUTPUT’s examples

Input’s e.g. #1

1
2
3
4
1 3 2 5
3 4 1 2

Output’s e.g. #1

1
2
3
4
5
4
3
0

分析

看题之后，应该想起来某JSOI2008星球大战上考过的类似思路吧。

就是倒着做，把毁灭改成创造（和平就是好）

我们每次从全是 X 的序列里创造一个数，然后求最大字段和。

很显然可以并查集，用并查集来维护字段和，然后用一个sum[i]数组来维护以i为父节点的集合的和。

因为每添加一个点，某些字段就可能会扩展，所以我们在加入的时候把这个点的左右两端的点所在的集合合并，并且把他们的和加起来。

因为是倒着处理，那我们就倒着输出。因为最后一个答案是此数列全部元素的和，无意义，所以舍弃。注意最后输出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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e5 + 10;
long long a[MAXN],des[MAXN],UFS[MAXN];
long long cnt,Max,sum[MAXN],ans[MAXN];
int n;
/* functions */
inline long long Find(long long x){
    if(x == UFS[x]) return x;
    else return UFS[x] = Find(UFS[x]);
}
int main(int argc,char *argv[]){
    scanf("%d",&n);
    FORL(i,1,n,1) scanf("%lld",&a[i]);
    FORL(i,1,n,1) scanf("%lld",&des[i]);
    ROFL(i,n,1,1){
        long long now = des[i];
        if(UFS[now] == 0) UFS[now] = now, sum[now] = a[now];
        long long findnow = Find(now);
        if(UFS[now - 1] != 0 && now - 1 > 0){
            long long l = Find(now - 1);
            if(findnow != l){
                sum[now] += sum[l]; sum[l] = 0; UFS[l] = now;
            }
        }
        if(UFS[now + 1] != 0 && now + 1 <= n){
            long long r = Find(now + 1);
            if(findnow != r){
                sum[now] += sum[r]; sum[r] = 0; UFS[r] = now;
            }
        }
        Max = std::max(Max,sum[now]);
        ans[++cnt] = Max;
    }
    ROFL(i,n-1,1,1) printf("%lld\n",ans[i]);
    puts("0");
    return 0;
}

THE END