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

2024-04-13 07:44
文章标签 数组 元素 更新 ii 不同 区间 线段 数目 平方和 2916

本文主要是介绍【线段树】【区间更新】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是最大值
{ d p [ j ] = p r e [ j ] j < = i 1 d p [ j ] = p r e [ j ] + 1 j > i 1 a n d j < i d p [ j ] = 1 j = = i \begin{cases} dp[j] = pre[j] && j <= i1 \\ dp[j] = pre[j]+1 && j> i1 \quad and j < i \\ dp[j] =1 && j == i \\ \end{cases} ⎩ ⎨ ⎧​dp[j]=pre[j]dp[j]=pre[j]+1dp[j]=1​​j<=i1j>i1andj<ij==i​
可以精简掉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
s u m = ∑ x : l r d p [ x ] s u m 2 = ∑ x : l r ( d p [ x ] ) 2 sum =\Large \sum_{x:l}^r dp[x] \quad sum2 = \sum_{x:l}^r (dp[x])^2 sum=x:l∑r​dp[x]sum2=x:l∑r​(dp[x])2
( d p [ l ] + 1 ) 2 + ( d p [ l + 1 ] + 1 ) 2 ⋯ ( d p [ r − 1 ] + 1 ) 2 + ( d p [ r ] + 1 ) 2 = d p [ l ] 2 + 2 d p [ l ] + 1 ⋯ = s u m 2 + s u m × 2 + ( r − l + 1 ) (dp[l]+1)^2 + (dp[l+1]+1)^2 \cdots (dp[r-1]+1)^2 + (dp[r]+1)^2 \\ =dp[l]^2 + 2dp[l]+1 \cdots \\ = sum2 + sum\times2+ (r-l+1) (dp[l]+1)2+(dp[l+1]+1)2⋯(dp[r−1]+1)2+(dp[r]+1)2=dp[l]2+2dp[l]+1⋯=sum2+sum×2+(r−l+1)

子节点刷新父节点

由于深度优先，函数的最后，子孙节点都已经更新完毕。通过两个孩子，更新当前节点。
当前节点全部属于更新区域，就结束不更新子孙节点，否则是否复杂度就不是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();}};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/899541。

相关文章

Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
java脚本使用不同版本jdk的说明介绍

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.
阅读更多...
在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中，<trim>元素用于动态地添加SQL语句的一部分，例如SET或W
阅读更多...
Redis缓存问题与缓存更新机制详解

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1
阅读更多...
Linux Mint Xia 22.1重磅发布: 重要更新一览

Linux Mint Xia 22.1重磅发布: 重要更新一览

《LinuxMintXia22.1重磅发布:重要更新一览》Beta版LinuxMint“Xia”22.1发布，新版本基于Ubuntu24.04，内核版本为Linux6.8，这... linux Mint 22.1「Xia」正式发布啦！这次更新带来了诸多优化和改进，进一步巩固了 Mint 在 Linux 桌面
阅读更多...
SpringCloud配置动态更新原理解析

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
Ubuntu 24.04 LTS怎么关闭 Ubuntu Pro 更新提示弹窗?

Ubuntu 24.04 LTS怎么关闭 Ubuntu Pro 更新提示弹窗?

《Ubuntu24.04LTS怎么关闭UbuntuPro更新提示弹窗?》Ubuntu每次开机都会弹窗提示安全更新，设置里最多只能取消自动下载，自动更新，但无法做到直接让自动更新的弹窗不出现，... 如果你正在使用 Ubuntu 24.04 LTS，可能会注意到——在使用「软件更新器」或运行 APT 命令时，
阅读更多...
vue如何监听对象或者数组某个属性的变化详解

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2