首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐
2025年7月12日 星期六 11:48pm

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

  • 25-02-22 05:21
  • 3742
  • 6381
blog.csdn.net

算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多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

⎧⎩⎨dp[j]=pre[j]dp[j]=pre[j]+1dp[j]=1j<=i1j>i1andj<ij==i{dp[j]=pre[j]j<=i1dp[j]=pre[j]+1j>i1andj<idp[j]=1j==i
⎩ ⎨ ⎧​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();
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191

测试用例

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54

private:
int m_iData = 0;;
};

template
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
void Query(const TGet& oGet, int iLeftIndex, int iRightIndex)
{
	Query(oGet, 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

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, C1097Int<>>,int>
{
public:
typedef pair, 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<>>& 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();
	}

};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览60345 人正在系统学习中
群中有博文配套源码
QQ群名片
注:本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/137001341"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top