首页 > 代码库 > [BZOJ 3747] [POI 2015] Kinoman【线段树】
[BZOJ 3747] [POI 2015] Kinoman【线段树】
Problem Link : BZOJ 3747
题解：ZYF-ZYF 神犇的题解
解题的大致思路是，当区间的右端点向右移动一格时，只有两个区间的左端点对应的答案发生了变化。
从 f[i] + 1 到 i 的区间中的答案增加了 W[A[i]], 从 f[f[i]] + 1 到 f[i] 的区间的答案减少了 W[A[i]] ，其余区间的答案没有发生变化。
那么就是线段树的区间修改和区间最值查询。
代码如下：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm> using namespace std; const int MaxN = 1000000 + 5; int n, m;int A[MaxN], W[MaxN], Last[MaxN], F[MaxN]; typedef long long LL; LL Ans;LL T[MaxN * 4], D[MaxN * 4]; inline LL gmax(LL a, LL b) { return a > b ? a : b;} inline void Update(int x) { T[x] = gmax(T[x << 1], T[x << 1 | 1]);} inline void Read(int &num) { char c; c = getchar(); while (c < ‘0‘ || c > ‘9‘) c = getchar(); num = c - ‘0‘; c = getchar(); while (c >= ‘0‘ && c <= ‘9‘) { num = num * 10 + c - ‘0‘; c = getchar(); }} inline void Paint(int x, LL num) { D[x] += num; T[x] += num;} inline void PushDown(int x) { if (D[x] == 0) return; Paint(x << 1, D[x]); Paint(x << 1 | 1, D[x]); D[x] = 0;} LL Add(int x, int s, int t, int l, int r, int num) { if (l <= s && r >= t) { Paint(x, (LL)num); return T[x]; } PushDown(x); int m = (s + t) >> 1; LL ret = 0; if (l <= m) ret = gmax(ret, Add(x << 1, s, m, l, r, num)); if (r >= m + 1) ret = gmax(ret, Add(x << 1 | 1, m + 1, t, l, r, num)); Update(x); return ret;} int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { Read(A[i]); F[i] = Last[A[i]]; Last[A[i]] = i; } for (int i = 1; i <= m; i++) Read(W[i]); Ans = 0; for (int i = 1; i <= n; i++) { Ans = gmax(Ans, Add(1, 1, n, F[i] + 1, i, W[A[i]])); if (F[i] != 0) Ans = gmax(Ans, Add(1, 1, n, F[F[i]] + 1, F[i], -W[A[i]])); } printf("%lld\n", Ans); return 0;}
[BZOJ 3747] [POI 2015] Kinoman【线段树】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。