算法可以发掘本质，如：
一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二，有无限多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]=1j<=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∑rdp[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();
}
};
