? 解题记录 ? ? 洛谷 ? ? 线段树 ?    2018-06-24 23:16:11    541    0    0

## 输入输出样例

```9 4
2 3 1 1 4 1 2 4 1
5 3 6 6```

`15`

## 代码能力越来越不行了……

```#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e6 + 5;
vector<int > MV[maxn];
int n, m, w[maxn], t[maxn], itr[maxn], ans;

namespace SGT {
int mx[maxn << 2], add[maxn << 2];
void push_up(int rt) {
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
void push_down(int rt) {
mx[rt << 1 | 1] += add[rt];
}
}
void Add(int l, int r, int tl, int tr, int rt, int dt) {
if(l == tl && r == tr)
return mx[rt] += dt, add[rt] += dt, void();
int mid = tl + tr >> 1;
push_down(rt);
if(r <= mid) Add(l, r, tl, mid, rt << 1, dt);
else if(l > mid) Add(l, r, mid + 1, tr, rt << 1 | 1, dt);
else Add(l, mid, tl, mid, rt << 1, dt), Add(mid + 1, r, mid + 1, tr, rt << 1 | 1, dt);
push_up(rt);
}
int Qmax(int l, int r, int tl, int tr, int rt) {
if(l == tl && r == tr) return mx[rt];
int mid = tl + tr >> 1;
if(r <= mid) return Qmax(l, r, tl, mid, rt << 1);
else if(l > mid) return Qmax(l, r, mid + 1, tr, rt << 1 | 1);
else return max(Qmax(l, mid, tl, mid, rt << 1), Qmax(mid + 1, r, mid + 1, tr, rt << 1 | 1));
}
}

int nt, *it;
signed main() {
scanf("%lld%lld", &n, &m);
For(i, 1, n) scanf("%lld", &t[i]), MV[t[i]].push_back(i);
For(i, 1, m) {
scanf("%lld", &w[i]), MV[i].push_back(n + 1);
if(MV[i].size() > 1)SGT::Add(MV[i][0], MV[i][1] - 1, 1, n, 1, w[i]);
}
ans = max(ans, SGT::Qmax(1, n, 1, n, 1));
For(i, 1, n) {
nt = t[i], it = &itr[nt];
if(*it < MV[nt].size() - 1) {
SGT::Add(MV[nt][*it], MV[nt][(*it) + 1] - 1, 1, n, 1, -w[nt]), ++(*it);
if(*it < MV[nt].size() - 1)
SGT::Add(MV[nt][*it], MV[nt][(*it) + 1] - 1, 1, n, 1, w[nt]);
}
ans = max(ans, SGT::Qmax(i, n, 1, n, 1));
}
printf("%lld\n", ans);
return 0;
}```

541 人读过

0 条评论