BZOJ 3747: [POI2015]Kinoman

考虑枚举起点，找一个最远的右端点使得以这个点为起点的答案最大

用线段树维护，需要设计一种标记，使得含有多个数的前缀中减去这个数的贡献

考虑这样设计，对于第一次出现的数，对其赋值$w[i]$

第二次出现赋值$-w[i]$

第三次出现赋值为0

这样前缀和就满足多次出现的数不会计算贡献

再维护前驱节点和后驱节点，每次删去开头的数，维护一下后驱节点

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 1000010
 6 #define INF 0x3f3f3f3f3f3f3f3f
 7 int n, m, f[N], pre[N], nx[N];
 8 ll w[N], v[N];
 9 map <int, int> mp;
10 
11 namespace SEG
12 {
13     ll Max[N << 2], lazy[N << 2];
14     void init()
15        { 
16         memset(Max, 0, sizeof Max);
17         memset(lazy, 0, sizeof lazy);   
18     }
19     void pushdown(int id)
20     {
21         if (!lazy[id]) return;
22         lazy[id << 1] += lazy[id];
23         Max[id << 1] += lazy[id];
24         lazy[id << 1 | 1] += lazy[id];
25         Max[id << 1 | 1] += lazy[id]; 
26         lazy[id] = 0;
27     }
28     void update(int id, int l, int r, int ql, int qr, ll val)
29     {
30         if (l >= ql && r <= qr) 
31         {
32             lazy[id] += val;
33             Max[id] += val;
34             return;
35         }
36         pushdown(id); 
37         int mid = (l + r) >> 1;
38         if (ql <= mid) update(id << 1, l, mid, ql, qr, val);
39         if (qr > mid) update(id << 1 | 1, mid + 1, r, ql, qr, val);
40         Max[id] = max(Max[id << 1], Max[id << 1 | 1]); 
41     }
42 }
43 
44 int main()
45 {
46     while (scanf("%d%d", &n, &m) != EOF)
47     {
48         for (int i = 1; i <= n; ++i) scanf("%d", f + i);
49         for (int i = 1; i <= m; ++i) scanf("%lld", w + i);
50         mp.clear();
51         for (int i = 1; i <= n; ++i)
52         {
53             if (mp.find(f[i]) != mp.end())
54                 pre[i] = mp[f[i]];
55             else
56                 pre[i] = 0;
57             mp[f[i]] = i;
58         }
59         mp.clear(); 
60         for (int i = n; i >= 1; --i)
61         {
62             if (mp.find(f[i]) != mp.end())
63                 nx[i] = mp[f[i]];
64             else
65                 nx[i] = n + 1;
66             mp[f[i]] = i;
67         }
68         for (int i = 1; i <= n; ++i)
69         {
70             if (pre[i] == 0) v[i] = w[f[i]];
71             else if (v[pre[i]] == w[f[pre[i]]]) v[i] = -w[f[i]]; 
72             else v[i] = 0;
73         }
74         SEG::init();
75         for (int i = 1; i <= n; ++i)
76             SEG::update(1, 1, n, i, n, v[i]);
77         ll res = 0;
78         for (int i = 1; i <= n; ++i)
79         {
80             res = max(res, SEG::Max[1]);
81             SEG::update(1, 1, n, i, n, -v[i]);
82             if (nx[i] != n + 1)
83             {
84                 SEG::update(1, 1, n, nx[i], n, -v[nx[i]]);
85                 v[nx[i]] = w[f[nx[i]]];
86                 SEG::update(1, 1, n, nx[i], n, v[nx[i]]);
87                 if (nx[nx[i]] != n + 1)
88                 {
89                     v[nx[nx[i]]] = -v[nx[i]];
90                     SEG::update(1, 1, n, nx[nx[i]], n, -v[nx[i]]);
91                 }
92             }
93         }
94         printf("%lld
", res);
95     }
96     return 0;
97 }

View Code