【线段树】【区间更新】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。

相关文章

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
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
2. c#从不同cs的文件调用函数

2. c#从不同cs的文件调用函数

1.文件目录如下： 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
hdu1689(线段树成段更新)

hdu1689(线段树成段更新)

两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401

uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401

题意是求在base进制下的 n！的结果有几位数，末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零，以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是： 1. n阶位数：直接 lg（n！）就是得数的位数。 2. n阶末尾0的个数：由于2 * 5 将会在得数中以0的形式存在，所以计算2或者计算5，由于因子中出现5必然出现2，所以直接一
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2