HBC226598[NOI2005]瑰丽华尔兹,dp的优化,动态规划势能线段树模板题二题解（势能线段树的使用）

凉芷算法基础篇 2023-11-09 01:44:02 50 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

智乃酱最近在学习势能线段树对于势能线段树，假设线段树的节点数为N{N}N，操作数目为M{M}M，若势能可被某种操作重置或者增加，则必须考虑最坏情况下能够提供操作总数M{M}M*|单次操作重置势能的节点总数|*|节点势能上限|的时间复杂度，则势能线段树则总时间复杂度为O(M×∣0势能时线段树操作时间复杂度∣+N×∣节点势能上限降低至0势能时间复杂度∣+M×∣线段树单次操作

智乃酱最近在学习势能线段树对于势能线段树，假设线段树的节点数为N{N}N，操作数目为M{M}M。若势能可被某种操作重置或者增加，则必须考虑最坏情况下能够提供操作总数M{M}M*|单次操作重置势能的节点总数|*|节点势能上限|的时间复杂度。则势能线段树则总时间复杂度为O(M×∣0势能时线段树操作时间复杂度∣+N×∣节点势能上限降低至0势能时间复杂度∣+M×∣线段树单次操作影响到的节点数目∣×∣操作额外提供的势能∣){O(M times |0势能时线段树操作时间复杂度|+Ntimes |节点势能上限降低至0势能时间复杂度|+Mtimes |线段树单次操作影响到的节点数目|times|操作额外提供的势能|)}O(M×∣0势能时线段树操作时间复杂度∣+N×∣节点势能上限降低至0势能时间复杂度∣+M×∣线段树单次操作影响到的节点数目∣×∣操作额外提供的势能∣)。一般来讲，在使用lazy_tag的情况下， |线段树单次操作影响到的节点数目|就是logN{logN}logN，本题中节点势能上限近似是个logN{logN}logN（其实是6）所以总复杂度是Mlog2N{Mlog^2N}Mlog2N级别的。使用势能线段树时要定义势能、势能初始值（势能最大值）、0势能点。本题中有两种可以定义势能与0势能的方法，你可以都尝试一下。定义区间开根次数cnt为势能，势能初始值为势能上限=6，定义0势能点为cnt=0，但是此方法重置势能比较困难，强烈不推荐使用。定义区间最大值max与区间最小值min的差值diff为势能，势能初始值为差值diff，定义0势能点为diff=0。 -------------------------------------------------------------------------------------------------------------------------- 给你一个长度大小为N{N}N的正整数数组，进行M{M}M次操作，操作有下列两种。给定区间[l,r]{[l,r]}[l,r]对区间中所有数字开根号向下取整，即ai=⌊ai⌋(l≤i≤r)a_i= lfloor sqrt{a_i} rfloor(l leq i leq r)ai=⌊ai⌋(l≤i≤r)。给定区间[l,r]{[l,r]}[l,r]，对区间中每个数字加上一个正整数x{x}x。查询给定区间[l,r]{[l,r]}[l,r]的元素和，即求∑i=lraisum_{i=l}^{r}a_{i}∑i=lrai。