Blackops

初心易得，始终难守

0%

2017年浙江工业大学大学生程序设计迎新赛热身赛 H 方块 III（思维+线段树）

发表于 分类于 ， ，

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述
有 N 个方块排成一排，每个方块都染有颜色，第 i 个的颜色为 Ci，一共有M种颜色，每种颜色的方块都有不同的价值Wi，现在要求找出一段方块，使得其中只出现过一次的方块的价值总和最大。
输入描述:
T组数据。
每组数据第一行，包含两个整数N和M
接下来一行包含N个整数Ci，代表每个方块的颜色
最后一行包含M个整数Wi，表示每种颜色的价值
T = 10
1 <= N, M <= 105，1 <= Ci <= M，1 <= Wi <= 109
输出描述:
每组数据一个整数，表示答案。
示例1
输入

5 3
1 2 1 1 3
30 40 50
10 5
5 4 3 5 3 1 2 4 2 1
78 65 99 132 200
输出

90
574

题目链接：H.方块 III
膜了别人的代码才发现这题这么简单，一直以为是什么$O(n)$的神奇算法，实际上是考虑每一个位置的颜色的贡献，进行范围更新。
假设当前的位置为$i$，颜色为$c_i$，该种颜色的权值为$w_i$，那么由于两个即以上颜色共存在一个区间的时候贡献为$0$，也就是说当前颜色有贡献的区间仅仅是$[上一个c_i出现位置+1,i]$，考虑完当前位置的颜色贡献，还要取消掉上一个该颜色出现位置的影响，然后所有点的贡献中的最大值就是数列$[1,i]$答案，维护一个区间更新，区间查询（实际上只需要查询根节点即可）的线段树，做一遍$O(nlog(n))$的更新即可。
代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct seg
{
    int l, mid, r;
    LL v, ad;
} T[N << 2];
int c[N], n, m;
LL w[N];
vector<int>pos[N];

void init()
{
    for (int i = 0; i <= m; ++i)
        pos[i].clear();
}
inline void pushup(int k)
{
    T[k].v = max(T[LC(k)].v, T[RC(k)].v);
}
inline void pushdown(int k)
{
    if (T[k].ad)
    {
        T[LC(k)].v += T[k].ad;
        T[RC(k)].v += T[k].ad;
        T[LC(k)].ad += T[k].ad;
        T[RC(k)].ad += T[k].ad;
        T[k].ad = 0;
    }
}
void build(int k, int l, int r)
{
    T[k].l = l;
    T[k].r = r;
    T[k].mid = MID(l, r);
    T[k].v = T[k].ad = 0;
    if (l == r)
        return ;
    build(LC(k), l, T[k].mid);
    build(RC(k), T[k].mid + 1, r);
}
inline void update(int k, int l, int r, LL v)
{
    if (l <= T[k].l && T[k].r <= r)
    {
        T[k].v += v;
        T[k].ad += v;
    }
    else
    {
        pushdown(k);
        if (l <= T[k].mid)
            update(LC(k), l, r, v);
        if (r > T[k].mid)
            update(RC(k), l, r, v);
        pushup(k);
    }
}
int main(void)
{
    int i;
    while (~scanf("%d%d", &n, &m))
    {
        init();
        for (i = 1; i <= n; ++i)
            scanf("%d", &c[i]);
        for (i = 1; i <= m; ++i)
            scanf("%lld", &w[i]);
        LL ans = 0;
        build(1, 1, n);
        for (i = 1; i <= n; ++i)
        {
            int sz = pos[c[i]].size();
            int C = c[i];
            int V = w[C];
            if (!sz)
                update(1, 1, i, V);
            else if (sz == 1)
            {
                update(1, 1, pos[C][sz - 1], -V);
                update(1, pos[C][sz - 1] + 1, i, V);
            }
            else
            {
                update(1, pos[C][sz - 2] + 1, pos[C][sz - 1], -V);
                update(1, pos[C][sz - 1] + 1, i, V);
            }
            ans = max(ans, T[1].v);
            pos[C].push_back(i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}