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 = + ;
 
int n, m;
int A[MaxN], W[MaxN], Last[MaxN], F[MaxN];
 
typedef long long LL;
 
LL Ans;
LL T[MaxN * ], D[MaxN * ];
 
inline LL gmax(LL a, LL b) {
    return a > b ? a : b;
}
 
inline void Update(int x) {
    T[x] = gmax(T[x << ], T[x << | ]);
}
 
inline void Read(int &num) {
    char c; c = getchar();
    while (c < '' || c > '') c = getchar();
    num = c - ''; c = getchar();
    while (c >= '' && c <= '') {
        num = num * + c - '';
        c = getchar();
    }
}
 
inline void Paint(int x, LL num) {
    D[x] += num;
    T[x] += num;
}
 
inline void PushDown(int x) {
    if (D[x] == ) return;
    Paint(x << , D[x]);
    Paint(x << | , D[x]);
    D[x] = ;
}
 
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) >> ;
    LL ret = ;
    if (l <= m) ret = gmax(ret, Add(x << , s, m, l, r, num));
    if (r >= m + ) ret = gmax(ret, Add(x << | , m + , t, l, r, num));
    Update(x);
    return ret;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = ; i <= n; i++) {
        Read(A[i]);
        F[i] = Last[A[i]];
        Last[A[i]] = i;
    }
    for (int i = ; i <= m; i++) Read(W[i]);
    Ans = ;       
    for (int i = ; i <= n; i++) {
        Ans = gmax(Ans, Add(, , n, F[i] + , i, W[A[i]]));
        if (F[i] != ) Ans = gmax(Ans, Add(, , n, F[F[i]] + , F[i], -W[A[i]]));
    }
    printf("%lld\n", Ans);
    return ;
}

最新文章

  1. C#将字节流加密解密
  2. Linux中MySQL的基本操作
  3. Selenium+Python+Eclipse网页自动化集成环境配置(附简单的测试程序)
  4. js动态切换图片
  5. java输入输出流小细节
  6. Swift语法基础入门三(函数, 闭包)
  7. 《C++ 标准库》读书笔记 - 第二章 Introduction to C++ and the Standard Library
  8. 朴素贝叶斯算法 &amp; 应用实例
  9. android之ViewStub的使用
  10. Ubuntu下安装Redis并实现远程访问
  11. JDBC&amp;&amp;c3p0、事务、批处理、多线程 于一体的经典秘方QueryRunner
  12. php 常用的知识点归集(上)
  13. bzoj 3513: [MUTC2013]idiots FFT
  14. WCF系列教程之WCF服务配置工具
  15. 【转】C++中嵌入python程序——参数传递
  16. tk.mybatis通用工具采坑记
  17. hdoj:2031
  18. Servlet基本_クッキー、URLリライティング
  19. Java学习之String
  20. 每日英语:How the College Bubble Will Pop

热门文章

  1. Block知识点总结
  2. 【转】Chrome 控制台不完全指南
  3. SAMSUNG某型号一千短信成功记录!对比其他软件恢复不成功的案列!
  4. Android学习起步 - 新建工程及相关
  5. PHP文件操作系统----主要的文件操作函数
  6. Python基础教程【读书笔记】 - 2016/7/31
  7. UIScrollView,UIPageControl
  8. CentOS系统内核升级
  9. [BZOJ 3110] [Zjoi2013] K大数查询 【树套树】
  10. 安装asterisk
  11. 论文笔记--PCN:Real-Time Rotation-Invariant Face Detection with Progressive Calibration Networks
  12. ACCESS 查询重复记录
  13. 数据库子查询和join的比较
  14. 开源深度学习架构Caffe
  15. Quartz_简单使用
  16. 安装php xdebug调试工具及性能分析工具webgrind for windows
  17. faceNet编译问题
  18. Redis之Sorted Set 有序集合
  19. Android -- 经验分享(三)
  20. 转:CentOS 7使用nmcli配置双网卡聚合LACP