给你一个下标从

是从右向左第一个小于strength[i]的下标是left如果不存在left是-1;right是从左向右第一个小于等于strength[i]的下标如果不存在right为m_c。

如果一个子数组strength[li,ri]的最小值是strength[i]且strength[i]左边没有和它相等的值。

则

我们可以这样计算这些子数组和的和。

累加strength[i]它出现的次数。

无论li和ri取值什么i都在子数组中所以i出现(i-left)(right-i)次。

li为left1时,ri无论取值什么都包括strength[left1]

li为left1和left2时ri无论取值什么都包括strength[left2]

(left,i)中的元素分别出现:right-i次、(right-i)*2、(right-i)*3…

(i,right)中的元素分别出现…、(i-left)*2、(i-left)次

前缀和

vPreSum2[i]记录strength[j]*(j1)的和j取值范围[0,i)。

核心代码

nums.size();m_vLeft.assign(m_c,

m_c);stackint

sta.top()))){m_vRight[sta.top()]

i;sta.pop();}if

sta.top();}sta.emplace(i);}}int

m_c;vectorint

CreatePreSumC1097Int(strength);vectorC1097Int

vPreSum2

strength[i];vPreSum2.emplace_back(vPreSum2.back()

biRet

i;//右边界的可选范围[i,right)//计算(left,i)的巫师和C1097Int

leftTotal

(left1);//计算(i,right)的巫师和C1097Int

rightTotal

rightLen;//计算以小标i为最弱力量的子数组C1097Int

cur

v2.size()){assert(false);return;}for

(int

slu.totalStrength(strength);Assert(78,

res);}{Solution

slu.totalStrength(strength);Assert(1,

res);}{Solution

slu.totalStrength(strength);Assert(14,

res);}{Solution

slu.totalStrength(strength);Assert(44,

res);}{Solution

slu.totalStrength(strength);Assert(213,

res);}{Solution

slu.totalStrength(strength);Assert(611131623,

2023年3月版

std::lower_bound(vValueIndex.begin(),

vValueIndex.end(),

vValueIndex.emplace_back(strength[i],

i);

std::lower_bound(vValueIndex.begin(),

vValueIndex.end(),

vValueIndex.emplace_back(strength[i],

i);

vSum1[iLeftLeft])*iLeftLeft;llLeftSum

(iRightLen

vSum1[iRightLeft])*(iRightRight

(vSum2[iRightRight

拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

https://edu.csdn.net/lecturer/6176

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。

子墨子言之事无终始无务多业。

也就是我们常说的专业的人做专业的事。

如果程序是一条龙那算法就是他的是睛

测试环境