交错序列——差分:GZOI2023D2T3

单点修改,全局查询交错序列最大值( max ⁡ ( ∑ i ( − 1 ) i b i ) \max(\sum_i (-1)^ib_i) max(i(1)ibi)), b b b a a a 的子序列

正常做法是线段树,但对于交错序列问题,有一种更好的方法,就是差分

考虑 a i − a j a_i-a_j aiaj,本质就是 [ j + 1 , i ] [j+1,i] [j+1,i] 的差分数组之和。由于选的段数没有限制,那必然是全选正数文章来源地址https://uudwc.com/A/JwkNJ

原文地址:https://blog.csdn.net/zhangtingxiqwq/article/details/133247058

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年09月25日 06:05
下一篇 2023年09月25日 06:06