备案控制台
开发者社区 人工智能 文章 正文

【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II

2024-05-07 18
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II

算法可以发掘本质，如：

一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。

二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。

三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。

四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。

一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

线段树

LeetCode:2916. 子数组不同元素数目的平方和 II

给你一个下标从 0 开始的整数数组 nums 。

定义 nums 一个子数组的 不同计数 值如下：

令 nums[i…j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i…j] 中不同值的数目为 nums[i…j] 的不同计数。

请你返回 nums 中所有子数组的 不同计数 的 平方 和。

由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

子数组指的是一个数组里面一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,2,1]

输出：15

解释：六个子数组分别为：

[1]: 1 个互不相同的元素。

[2]: 1 个互不相同的元素。

[1]: 1 个互不相同的元素。

[1,2]: 2 个互不相同的元素。

[2,1]: 2 个互不相同的元素。

[1,2,1]: 2 个互不相同的元素。

所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。

示例 2：

输入：nums = [2,2]

输出：3

解释：三个子数组分别为：

[2]: 1 个互不相同的元素。

[2]: 1 个互不相同的元素。

[2,2]: 1 个互不相同的元素。

所有不同计数的平方和为 12 + 12 + 12 = 3 。

提示：

1 <= nums.length <= 105

1 <= nums[i] <= 105

线段树

线段树的时间复杂度，单点更新（查询）下标index，时间复杂度O(logn)。index及它的祖先最多logn个。区间[l,r]更新（查询）时间复杂度也是O(logn)。涉及的节点分如下四类：一，l及它的祖先。二，r及它的祖先。三，第一类节点的右兄弟节点。四，第二类节点的左兄弟节点。显然四类节点都不超过logn。

题解

pre[j]记录nums[j…i-1]不同元素的数目。dp[j]记录nums[j…i]不同元素的数目。

处理nums[i]时：

dp[i]=1

假定nums[i1] == nums[i]，且i1是最大值

image.png

可以精简掉pre，只保留dp。

dp[i1+1…i]++。注意如果i1不存在，为-1也符合条件。

线段树

直接更新区间的时间复杂度是O(n)，处理num字符的时间复杂度是O(n)，总时间复杂度是O(nn)，超时了。用线段树，区间更新的时间复杂度是O(logn)，总时间复杂度是O(longn)。

用哈希映射或数组记录nums[i]删除出现的下标，时间复杂度O(1)。

线段树节点记录两个值：sum和sum2

image.png

子节点刷新父节点

由于深度优先，函数的最后，子孙节点都已经更新完毕。通过两个孩子，更新当前节点。

当前节点全部属于更新区域，就结束不更新子孙节点，否则是否复杂度就不是logn。

用m_vRecord记录需要更新的值。但处理要子孙节点时，统一更新。

代码

核心代码

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;;
};
template<class TSave,class TRecord,TRecord RecordNull= 0>
class CLineTree
{
public:
  CLineTree(int iEleSize) 
    :m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4),m_vRecord(m_iEleSize * 4,RecordNull)
  {
  }
  void Update( int iLeftIndex, int iRightIndex, TRecord value)
  {
    Update(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1,value);
  }
  template<class TGet>
  void Query(const TGet& oGet, int iLeftIndex, int iRightIndex)
  {
    Query(oGet, 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
  }
private:
  virtual void OnUpdateRecord(TRecord& old,const TRecord& newRecord) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) = 0;
  virtual void OnUpdate(TSave& save, const int& len, const TRecord& iUpdate) = 0;
  template<class TGet>
  void Query(const TGet& oGet, int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight)
  {
    if ((iQueryLeft <= iSaveLeft) && (iQueryRight >= iSaveRight))
    {
      oGet(m_vArr[iNode]);
      return;
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iQueryLeft)
    {
      Query(oGet,iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight);
    }
    if (iMid + 1 <= iQueryRight)
    {
      Query(oGet, iNode * 2 + 1, iMid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }   
  }
  void Update( int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value)
  {
    if (iNode >= m_vArr.size())
    {     
      return;
    }   
    if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
    { 
      OnUpdate(m_vArr[iNode], min(iSaveRight, iOpeRight) - max(iSaveLeft, iOpeLeft) + 1, value);
      OnUpdateRecord(m_vRecord[iNode], value);
      return;
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iOpeLeft)
    {
      Update( iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
    }
    if (iMid + 1 <= iOpeRight)
    {
      Update( iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
    }
    // 如果有后代，至少两个后代
    OnUpdateParent(m_vArr[iNode], m_vArr[iNode * 2] , m_vArr[iNode * 2 + 1]);
  }
  void Fresh(int iNode, int iDataLeft, int iDataRight)
  {
    if (RecordNull == m_vRecord[iNode])
    {
      return;
    }
    const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
    Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vRecord[iNode]);
    Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_vRecord[iNode]);
    m_vRecord[iNode] = RecordNull;
  }
  const int m_iEleSize;
  vector<TSave> m_vArr;
  vector<TRecord> m_vRecord;
};
class CPOW2LineTree : public CLineTree<pair<C1097Int<>, C1097Int<>>,int>
{
public:
  typedef  pair<C1097Int<>, C1097Int<>> TSave;
  typedef int TRecord;
  const TRecord RecordNull = 0 ;
  using CLineTree::CLineTree;
  // 通过 CLineTree 继承
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
  {
    old += newRecord;
  }
  // 通过 CLineTree 继承
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) override
  {
    par.first = left.first + r.first;
    par.second = left.second + r.second;
  }
  virtual void OnUpdate(TSave& save, const int& len, const TRecord& iUpdate) override
  {
    save.second += save.first * 2 * iUpdate + C1097Int<>(len) * iUpdate * iUpdate;
    save.first += C1097Int<>(iUpdate) * len;
  }
};
class Solution {
public:
  int sumCounts(vector<int>& nums) {
    CPOW2LineTree lineTree(nums.size());
    const int iMax = *std::max_element(nums.begin(), nums.end());
    vector<int> vPre(iMax + 1, -1);
    C1097Int<> biRet;
    for (int i = 0; i < nums.size(); i++)
    {
      lineTree.Update( vPre[nums[i]] + 1, i,1);
      auto Query = [&](pair<C1097Int<>, C1097Int<>>& pr) {
        biRet += pr.second;
      };
      lineTree.Query(Query, 0, nums.size());
      vPre[nums[i]] = i;
    }
    return biRet.ToInt();
  }
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& 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 nums ;
{
Solution sln;
nums = { 1,2,1 };
auto res = sln.sumCounts(nums);
Assert(res, 15);
}
{
Solution sln;
nums = { 2,2 };
auto res = sln.sumCounts(nums);
Assert(res, 3);
}
}

旧代码

超时的边缘。

template
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;;
};
template<class TSave,class TRecord,TRecord RecordNull= 0>
class CLineTree
{

public:

CLineTree(int iEleSize)
:m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4),m_vRecord(m_iEleSize * 4,RecordNull)
{
}
void Update( int iLeftIndex, int iRightIndex, TRecord value)
{
  Update(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1,value);
}
template<class TGet>
void Query(const TGet& oGet, int iLeftIndex, int iRightIndex)
{
  Query(oGet, 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
}

private:

virtual void OnUpdateRecord(TRecord& old,const TRecord& newRecord) = 0;
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) = 0;
virtual void OnUpdate(TSave& save, const int& len, const TRecord& iUpdate) = 0;
template
void Query(const TGet& oGet, int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight)
{
if ((iQueryLeft <= iSaveLeft) && (iQueryRight >= iSaveRight))
{
oGet(m_vArr[iNode]);
return;
}
Fresh(iNode, iSaveLeft, iSaveRight);
const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iMid >= iQueryLeft)
{
Query(oGet,iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight);
}
if (iMid + 1 <= iQueryRight)
{
Query(oGet, iNode * 2 + 1, iMid + 1, iSaveRight, iQueryLeft, iQueryRight);
}
}
void Update( int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value)
{
if (iNode >= m_vArr.size())
{
return;
}
if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
{
OnUpdate(m_vArr[iNode], min(iSaveRight, iOpeRight) - max(iSaveLeft, iOpeLeft) + 1, value);
OnUpdateRecord(m_vRecord[iNode], value);
return;
}
Fresh(iNode, iSaveLeft, iSaveRight);
const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iMid >= iOpeLeft)
{
Update( iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
}
if (iMid + 1 <= iOpeRight)
{
Update( iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
}
// 如果有后代，至少两个后代
OnUpdateParent(m_vArr[iNode], m_vArr[iNode * 2] , m_vArr[iNode * 2 + 1]);
}
void Fresh(int iNode, int iDataLeft, int iDataRight)
{
if (RecordNull == m_vRecord[iNode])
{
return;
}
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vRecord[iNode]);
Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_vRecord[iNode]);
m_vRecord[iNode] = RecordNull;
}
const int m_iEleSize;
vector m_vArr;
vector m_vRecord;
};
class CPOW2LineTree : public CLineTree<pair<C1097Int<>, C1097Int<>>,int>
{
public:
typedef pair<C1097Int<>, C1097Int<>> TSave;
typedef int TRecord;
const TRecord RecordNull = 0 ;
using CLineTree::CLineTree;
// 通过 CLineTree 继承
virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
{
old += newRecord;
}
// 通过 CLineTree 继承
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) override
{
par.first = left.first + r.first;
par.second = left.second + r.second;
}
virtual void OnUpdate(TSave& save, const int& len, const TRecord& iUpdate) override
{
save.second += save.first * 2 * iUpdate + C1097Int<>(len) * iUpdate * iUpdate;
save.first += C1097Int<>(iUpdate) * len;
}
};
class Solution {
public:
int sumCounts(vector& nums) {
CPOW2LineTree lineTree(nums.size());
const int iMax = *std::max_element(nums.begin(), nums.end());
vector vPre(iMax + 1, -1);
C1097Int<> biRet;
for (int i = 0; i < nums.size(); i++)
{
lineTree.Update( vPre[nums[i]] + 1, i,1);
auto Query = [&](pair<C1097Int<>, C1097Int<>>& pr) {
biRet += pr.second;
};
lineTree.Query(Query, 0, nums.size());
vPre[nums[i]] = i;
}
return biRet.ToInt();
}
};

2024年4月3号 测试新的封装类

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;;
};
template<class TSave, class TRecord >
class CRangUpdateLineTree 
{
protected:
  virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) = 0;
  virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) = 0;
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};
template<class TSave, class TRecord >
class CVectorRangeUpdateLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
public:
  CVectorRangeUpdateLineTree(int iEleSize,TSave tDefault, TRecord tRecordNull):m_iEleSize(iEleSize)
    ,m_save(iEleSize*4,tDefault), m_record(iEleSize * 4, tRecordNull){
    m_recordNull = tRecordNull;   
  }
  void Update(int iLeftIndex, int iRightIndex, TRecord value)
  {
    Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);
  }
  void Query(int leftIndex, int leftRight) {
    Query(1, 0, m_iEleSize - 1, leftIndex, leftRight);
  }
  //void Init() {
  //  Init(1, 0, m_iEleSize - 1);
  //}
  TSave QueryAll() {
    return m_save[1];
  }
protected:
  //void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
  //{
  //  if (iSaveLeft == iSaveRight) {
  //    this->OnInit(m_save[iNodeNO], iSaveLeft);
  //    return;
  //  }
  //  const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
  //  Init(iNodeNO * 2, iSaveLeft, mid);
  //  Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
  //  this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
  //}
  void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
    if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
      this->OnQuery(m_save[iNodeNO]);
      return;
    }
    if (iSaveLeft == iSaveRight) {//没有子节点
      return;
    }
    Fresh(iNodeNO);
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (mid >= iQueryLeft) {
      Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
    }
    if (mid + 1 <= iQueryRight) {
      Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value)
  {
    if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
    {
      this->OnUpdate(m_save[iNode], iSaveLeft, iSaveRight, value);
      this->OnUpdateRecord(m_record[iNode], value);
      return;
    }
    if (iSaveLeft == iSaveRight) {
      return;//没有子节点
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iOpeLeft)
    {
      Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
    }
    if (iMid + 1 <= iOpeRight)
    {
      Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
    }
    // 如果有后代，至少两个后代
    this->OnUpdateParent(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iSaveRight);
  }
  void Fresh(int iNode, int iDataLeft, int iDataRight)
  {
    if (m_recordNull == m_record[iNode])
    {
      return;
    }
    const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
    Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_record[iNode]);
    Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_record[iNode]);
    m_record[iNode] = m_recordNull;
  }
  vector<TSave> m_save;
  vector<TRecord> m_record;
  TRecord m_recordNull;
  const int m_iEleSize;
};
template<class TSave= pair<C1097Int<>, C1097Int<>>, class TRecord = int >
class CPOW2LineTree : public CVectorRangeUpdateLineTree<TSave, TRecord>
{
public:
  using CVectorRangeUpdateLineTree<TSave, TRecord>::CVectorRangeUpdateLineTree;
protected:
  virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) override
  {
  }
  virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) override
  {
    const int len = iSaveRight - iSaveLeft + 1;
    save.second += save.first * 2 * update + C1097Int<>(len) * update * update;
    save.first += C1097Int<>(update) * len;
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) override
  {
    par.first = left.first + r.first;
    par.second = left.second + r.second;
  }
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
  {
    old += newRecord;
  }
};
class Solution {
public:
  int sumCounts(vector<int>& nums) {
    CPOW2LineTree<> lineTree(nums.size(), { 0,0 }, 0);
    const int iMax = *std::max_element(nums.begin(), nums.end());
    vector<int> vPre(iMax + 1, -1);
    C1097Int<> biRet;
    for (int i = 0; i < nums.size(); i++)
    {
      lineTree.Update(vPre[nums[i]] + 1, i, 1);     
      biRet += lineTree.QueryAll().second;
      vPre[nums[i]] = i;
    }
    return biRet.ToInt();
  }
};


我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

文章标签：
算法
C++
测试技术
机器学习/深度学习
闻缺陷则喜何志丹
目录
相关文章
闻缺陷则喜何志丹
|
1月前
|
机器学习/深度学习 算法 测试技术
【单调栈】3113. 边界元素是最大值的子数组数目
【单调栈】3113. 边界元素是最大值的子数组数目
闻缺陷则喜何志丹
19 0
闻缺陷则喜何志丹
|
1月前
|
测试技术
【动态规划】【组合数学】1866. 恰有 K 根木棍可以看到的排列数目
【动态规划】【组合数学】1866. 恰有 K 根木棍可以看到的排列数目
闻缺陷则喜何志丹
39 0
碳基肥宅
|
1月前
DAY-4 | 力扣 - 求自身以外数组的乘积：区间划分，左右累乘，巧求乘积
该文档是关于LeetCode上的一道题目“Product of Array Except Self”的题解。提供了两种解题方法，一是暴力破解，即计算所有数的乘积后再逐个除以当前元素；二是左右累乘法，通过两次遍历数组分别计算左侧和右侧元素的乘积，避免了除法操作。其中，左右累乘法更优，代码实现中展示了这种方法。
碳基肥宅
24 1
闻缺陷则喜何志丹
|
1月前
|
算法 测试技术 C#
二分查找|前缀和|滑动窗口|2302:统计得分小于 K 的子数组数目
二分查找|前缀和|滑动窗口|2302:统计得分小于 K 的子数组数目
闻缺陷则喜何志丹
31 0
闻缺陷则喜何志丹
|
6月前
|
算法 测试技术 C#
C++ 算法：区间和的个数
C++ 算法：区间和的个数
闻缺陷则喜何志丹
76 0
闻缺陷则喜何志丹
|
6月前
|
算法 测试技术 C#
C++二分查找算法：有序矩阵中的第 k 个最小数组和（二）
C++二分查找算法：有序矩阵中的第 k 个最小数组和
闻缺陷则喜何志丹
36 0
闻缺陷则喜何志丹
|
6月前
|
算法 测试技术 C++
C++二分查找算法：有序矩阵中的第 k 个最小数组和（一）
C++二分查找算法：有序矩阵中的第 k 个最小数组和
闻缺陷则喜何志丹
37 0
小tata鸡米
|
11月前
|
人工智能 算法 BI
贪心算法——区间选点与最大不相交区间数
贪心算法——区间选点与最大不相交区间数
小tata鸡米
50 0
算法码上来
|
C++
【LeetCode 327】区间和的个数
【LeetCode 327】区间和的个数
算法码上来
88 0
zzqwtc
|
人工智能 BI
AcWing 908. 最大不相交区间数量 (区间贪心问题)
笔记
zzqwtc
190 0
AcWing 908. 最大不相交区间数量 (区间贪心问题)