【前缀和】【单调栈】LeetCode2281:巫师的总力量和

template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
class CRangIndex
{
public:
  template<class _Pr>
  CRangIndex(const vector<int>& nums, _Pr CurIndexCmpStackTopIndex)
  {
    m_c = nums.size();
    m_vLeft.assign(m_c, -1);
    m_vRight.assign(m_c, m_c);
    stack<int> sta;
    for (int i = 0; i < m_c; i++)
    {
      while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top())))
      {
        m_vRight[sta.top()] = i;
        sta.pop();
      }
      if (sta.size())
      {
        m_vLeft[i] = sta.top();
      }
      sta.emplace(i);
    }
  }
  int m_c;
  vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};
template<class T = long long >
vector<T> CreatePreSum(const vector<int>& nums)
{
  vector<T> preSum;
  preSum.push_back(0);
  for (int i = 0; i < nums.size(); i++)
  {
    preSum.push_back (preSum[i]+ nums[i]);
  }
  return preSum;
}
class Solution {
public:
  int totalStrength(vector<int>& strength) {
    CRangIndex ri(strength, [&](int i1, int i2) {return strength[i1] <= strength[i2]; });
    auto vPreSum = CreatePreSum<C1097Int<>>(strength);
    vector<C1097Int<>> vPreSum2 = { 0 };
    for (int i = 0 ; i < ri.m_c ;  i++ )
    {
      const auto& n = strength[i];
      vPreSum2.emplace_back(vPreSum2.back() + C1097Int<>(n)*(i+1));
    }
    C1097Int<> biRet = 0;
    for (int i = 0; i < ri.m_c; i++)
    {
      const int left = ri.m_vLeft[i];
      const int right = ri.m_vRight[i];
      const int leftLen = i - left;//左边界的可选范围(left,i]
      const int rightLen = right - i;//右边界的可选范围[i,right)
      //计算(left,i)的巫师和
      C1097Int<> leftTotal = vPreSum2[i] - vPreSum2[left + 1] - (vPreSum[i] - vPreSum[left + 1]) * (left+1);
      //计算(i,right)的巫师和
      C1097Int<> rightTotal = (vPreSum[right] - vPreSum[i + 1])*(right+1) - ( vPreSum2[right] - vPreSum2[i + 1] );
      C1097Int<> iTotal = C1097Int<>(strength[i]) * leftLen * rightLen;
      //计算以小标i为最弱力量的子数组
      C1097Int<> cur = leftTotal * rightLen + rightTotal * leftLen + iTotal;
      cur *= strength[i];
      biRet += cur;
    }
    return biRet.ToInt();
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> strength;
  {
    Solution slu;
    strength = { 2,3,4 };
    auto res = slu.totalStrength(strength);
    Assert(78, res);
  }
  {
    Solution slu;
    strength = { 1 };
    auto res = slu.totalStrength(strength);
    Assert(1, res);
  }
  {
    Solution slu;
    strength = { 1,3 };
    auto res = slu.totalStrength(strength);
    Assert(14, res);
  }
  {
    Solution slu;
    strength = { 1, 3, 1, 2 };
    auto res = slu.totalStrength(strength);
    Assert(44, res);
  }
  {
    Solution slu;
    strength = { 5,4,6 };
    auto res = slu.totalStrength(strength);
    Assert(213, res);
  }
  {
    Solution slu;
    strength.assign(100'000, 1000'000'000);
    auto res = slu.totalStrength(strength);
    Assert(611131623, res);
  }
  //CConsole::Out(res);
}

C1097Int llSum = 0;
   for (int i = 0; i < m_c; i++)
   {
     const int iLeftLeft = vLeft[i] + 1;
     const int iLeftRight = i - 1;
     const int iRightLeft = i + 1;
     const int iRightRight = vRight[i] - 1;
     const int iLeftLen = iLeftRight - iLeftLeft + 1;
     const int iRightLen = iRightRight - iRightLeft + 1;
     C1097Int llCurSun = ((long long)iLeftLen + 1)*(iRightLen + 1)*strength[i];
     C1097Int llLeftSum = 0, llRightSum = 0;
     if (iLeftLen > 0)
     {
       llLeftSum = vSum2[iLeftRight + 1] - vSum2[iLeftLeft] - (vSum1[iLeftRight + 1] - vSum1[iLeftLeft])*iLeftLeft;
       llLeftSum *= (iRightLen + 1);
     }
     if (iRightLen > 0)
     {
       llRightSum = (vSum1[iRightRight + 1] - vSum1[iRightLeft])*(iRightRight + 2) - (vSum2[iRightRight + 1] - vSum2[iRightLeft]);
       llRightSum *= (iLeftLen + 1);
     }
     llCurSun += llLeftSum;
     llCurSun += llRightSum;
     llSum += llCurSun*strength[i];
   }
   return llSum.ToInt();
 }
 int m_c;