【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组-阿里云开发者社区

LeetCode629: K 个逆序对数组

逆序对的定义如下：对于数组 nums 的第 i 个和第 j 个元素，如果满足 0 <= i < j < nums.length 且 nums[i] > nums[j]，则其为一个逆序对；否则不是。

给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。由于答案可能很大，只需要返回对 109 + 7 取余的结果。

示例 1：

输入：n = 3, k = 0

输出：1

解释：

只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2：

输入：n = 3, k = 1

输出：2

解释：

数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

提示：

1 <= n <= 1000

0 <= k <= 1000

动态规划

** 空间复杂度**: O(n)

时间复杂度😮(n²)

动态规划的状态表示：pre[i]表示1到j-1的排列中，逆数对数量为i的数量。dp[i]表示1到j的排列中，逆数对的数量。 i 取值范围[0,1000]

动态规划的转移方程: 假定某个1到j-1 的排列，逆数对为x。插入j后，除j外的顺序不边，也就是除j外，不会产生新的逆数对。当然也不会减少逆数对。那如果将j插入到最后，逆序数不变。插入到倒数第一之前，逆数对+1。。。插入到最前面，逆序对+j-1。换过说法：

dp[i] = Sum( i − j , i ] k ^{k}_{(i-j,i]}(i−j,i]kpre[k]。可以利用滑动窗口求和。

动态规划的初始状态: pre[0]=0

动态规划的填表顺序： j 从小到大，i从小到大。

动态规划的返回值:pre[k]

代码

使用到的类库

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;;
};

核心代码

class Solution {
public:
  int kInversePairs(int n, int k) {
    vector<C1097Int<>> pre(1001) ;
    pre[0] = 1;
    for (int j = 2; j <= n; j++)
    {
      vector<C1097Int<>> dp(1001);
      C1097Int<> iSum = 0;
      for (int i = 0; i < pre.size(); i++)
      {
        iSum += pre[i];
        if (i - j >= 0)
        {
          iSum -= pre[i - j];
        }
        dp[i] = iSum;
      }
      pre.swap(dp);
    }
    return pre[k].ToInt();
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  int n,k;
  {
    Solution sln;
    n = 3, k = 0;
    auto res = sln.kInversePairs(n, k);
    Assert(1, res);
  }
  {
    Solution sln;
    n = 3, k = 1;
    auto res = sln.kInversePairs(n, k);
    Assert(2, res);
  }
  {
    Solution sln;
    n = 1000, k = 1000;
    auto res = sln.kInversePairs(n, k);
    Assert(663677020, res);
  }
}

2023年1月版

class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (*dst + iSrc) % s_iMod;
}

static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1)
 {
   *dst = (*dst + iSrc) % s_iMod;
   *dst = (*dst + iSrc1) % s_iMod;
 }
 static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1, const int& iSrc2)
 {
   *dst = (*dst + iSrc) % s_iMod;
   *dst = (*dst + iSrc1) % s_iMod;
   *dst = (*dst + iSrc2) % s_iMod;
 }
 static void SubAssignment(int* dst, const int& iSrc)
 {
   *dst = (s_iMod - iSrc + *dst) % s_iMod;
 }
 static int Add(const int& iAdd1, const int& iAdd2)
 {
   return (iAdd1 + iAdd2) % s_iMod;
 }
 static int Mul(const int& i1, const int& i2)
 {
   return((long long)i1 *i2) % s_iMod;
 }

private:
static const int s_iMod = 1000000007;
};
class Solution {
public:
int kInversePairs(int n, int k) {
vector preDp(k + 1);
preDp[0] = 1;
for (int i = 2; i <= n; i++)
{
vector dp(k+1 );
for (int j = 0; j < dp.size(); j++)
{
if (j < preDp.size())
{
CBigMath::AddAssignment(&dp[j], preDp[j]);
}
if (j > 0)
{
CBigMath::AddAssignment(&dp[j], dp[j - 1]);
}
if ( j - i >= 0)
{
int iMod = 1000000007;
CBigMath::AddAssignment(&dp[j], iMod - preDp[j - i]);
}
}
preDp.swap(dp);
}
return k >= preDp.size() ? 0 : preDp[k];
}
};

2023年6月

using namespace std;
template
void OutToConsoleInner(const vector& vec,const string& strSep = " ")
{
for (int i = 0; i < vec.size(); i++)
{
if (0 != i%25)
{
std::cout << strSep.c_str();
}
std::cout << setw(3) << setfill(’ ') << vec[i];
if (0 == (i+1) % 25)
{
std::cout << std::endl;
}
else if (0 == (i + 1) % 5)
{
std::cout << strSep.c_str();
}
}
}
class CConsole
{
public :

template<class T>
static void Out(const vector<T>& vec, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
  OutToConsoleInner(vec, strColSep);
  std::cout << strRowSep.c_str();
}
template<class T>
static void Out(const vector<vector<T>>& matrix, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
  for (int i = 0; i < matrix.size(); i++)
  {
    OutToConsoleInner(matrix[i], strColSep);
    std::cout << strRowSep.c_str();
  }
}
template<class T>
static void Out(const std::map<T, std::vector<int> >& mTopPointToPoints, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
  for (auto kv : mTopPointToPoints)
  {
    std::cout << kv.first << ":";
    OutToConsoleInner(kv.second, strColSep);
    std::cout << strRowSep.c_str();
  }
}
static void Out(const  std::string& t, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
  std::cout << t.c_str() << strColSep.c_str();
}
template<class T  >
static void Out(const T& t, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
  std::cout << t << strColSep.c_str();
}

};
void GenetateSum(vector& sums, const vector& nums)
{
sums.push_back(0);
for (int i = 0; i < nums.size(); i++)
{
sums.push_back(nums[i] + sums[i]);
}
}
//[iBegin，iEnd]之和
long long Total(int iBegin,int iEnd)
{
return (long long)(iBegin + iEnd)*(iEnd - iBegin + 1) / 2;
}
class CLadderhlp
{
public:
CLadderhlp( int ladders)
{
m_uLadderNum = ladders;
}
void AddNeedBick(int iNeedBick)
{
if (0 == m_uLadderNum)
{
return;
}
if (m_ladders.size() < m_uLadderNum)
{
m_ladders.push(iNeedBick);
m_iEaqualBicks += iNeedBick;
return;
}
int iTop = m_ladders.top();
if (iTop >= iNeedBick)
{
return;
}
m_iEaqualBicks -= iTop;
m_iEaqualBicks += iNeedBick;
m_ladders.pop();
m_ladders.push(iNeedBick);
}
std::priority_queue m_ladders;
unsigned int m_uLadderNum;
long long m_iEaqualBicks = 0;
};
struct CPeo
{
CPeo(string strName, CPeo* pParent=nullptr)
{
m_strName = strName;
m_pParent = pParent;
}
string m_strName;
vector m_childs;
CPeo* m_pParent = nullptr;
};
class CNeighborTable
{
public:
void Init(const vector& edges)
{

}
 vector<vector<int>> m_vTable;

};
//通过 x &= (x-1)实现
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}
int bitcount(unsigned long long x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}
class CRange
{
public:
template
CRange(const T& v)
{
m_iBegin = 0;
m_iEnd = v.size();
}
bool In(int iIndex)
{
return (iIndex >= m_iBegin) && (iIndex < m_iEnd);
}
const int End()
{
return m_iEnd;
}
protected:
int m_iBegin;
int m_iEnd;
};
template
class CTrie
{
public:
CTrie() :m_vPChilds(iTypeNum)
{

}
 template<class IT>
 void Add(IT begin, IT end)
 {
   CTrie<iTypeNum, cBegin> * pNode = this;
   for (; begin != end; ++begin)
   {
     pNode = pNode->AddChar(*begin).get();
   }
 }
 template<class IT>
 bool Search(IT begin, IT end)
 {
   if (begin == end)
   {
     return true;
   }
   if ('.' == *begin)
   {
     for (auto& ptr : m_vPChilds)
     {
       if (!ptr)
       {
         continue;
       }
       if (ptr->Search(begin + 1, end))
       {
         return true;
       }
     }
   }
   auto ptr = GetChild(*begin);
   if (nullptr == ptr)
   {
     return false;
   }
   return ptr->Search(begin + 1, end);
 }

protected:
std::shared_ptr AddChar(char ch)
{
if ((ch < cBegin) || (ch >= cBegin + iTypeNum))
{
return nullptr;
}
const int index = ch - cBegin;
auto ptr = m_vPChilds[index];
if (!ptr)
{
m_vPChilds[index] = std::make_shared>();
}
return m_vPChilds[index];
}
std::shared_ptr GetChild(char ch)const
{
if ((ch < cBegin) || (ch >= cBegin + iTypeNum))
{
return nullptr;
}
return m_vPChilds[ch - cBegin];
}
std::vector m_vPChilds;
};
class CWords
{
public:
void Add(const string& word)
{
m_strStrs.insert(word);
}
bool Search(const string& word)
{
return Search(m_strStrs.begin(), m_strStrs.end(), 0, word.length(), word);
}
protected:
bool Search(std::set::const_iterator begin, std::set::const_iterator end, int iStrBegin, int iStrEnd, const string& str)
{
int i = iStrBegin;
for (; (i < iStrEnd) && (str[i] != ‘.’); i++);
auto it = std::equal_range(begin, end, str, [&iStrBegin, &i](const string& s, const string& sFind)
{
return s.substr(iStrBegin, i - iStrBegin) < sFind.substr(iStrBegin, i - iStrBegin);
});
if (i == iStrBegin)
{
it.first = begin;
it.second = end;
}
if (it.first == it.second)
{
return false;
}
if (i == iStrEnd)
{
return true;
}
if (i + 1 == iStrEnd)
{
return true;
}
string tmp = str;
for (char ch = ‘a’; ch <= ‘z’; ch++)
{
tmp[i] = ch;
auto ij = std::equal_range(it.first, it.second, tmp, [&ch, &i](const string& s, const string& sFind)
{
return s[i] < sFind[i];
});
if (ij.first == ij.second)
{
continue;
}

if (Search(ij.first, ij.second, i + 1, iStrEnd, str))
     {
       return true;
     }
   }
   return false;
 }
 std::set<string> m_strStrs;

};
class WordDictionary {
public:
WordDictionary() {
for (int i = 0; i < 26; i++)
{
m_str[i] = std::make_unique();
}
}

void addWord(string word) {
   m_str[word.length()]->Add(word);
 }
 bool search(string word) {
   return m_str[word.length()]->Search(word);
 }
 std::unique_ptr<CWords> m_str[26];

};
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( int 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
int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}
template
int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}
template
int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int(iData)).ToInt();
return iRet;
}
template
int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int(iData)).ToInt();
return iData;
}
template
void MinSelf(T* seft, const T& other)
{
*seft = min(*seft, other);
}
template
void MaxSelf(T* seft, const T& other)
{
*seft = max(*seft, other);
}
int GetNotRepeateNum(int len, int iHasSel)
{
if (0 == len)
{
return 1;
}
if ((0 == iHasSel) && (1 == len))
{
return 10;
}
int iRet = 1;
if (iHasSel > 0)
{
for (int tmp = 10 - iHasSel; (tmp >= 2)&& len ; tmp–,len–)
{
iRet *= tmp;
}
}
else
{
iRet *= 9;
len–;
for (int tmp=9; (tmp>=2)&&len; len–,tmp–)
{
iRet *= tmp;
}
}
return iRet;
}
int GCD(int n1, int n2)
{
int t1 = min(n1, n2);
int t2 = max(n1, n2);
if (0 == t1)
{
return t2;
}
return GCD(t2%t1, t1);
}
void CreateMaskVector(vector& v,const int* const p,int n )
{
const int iMaxMaskNum = 1 << n;
v.resize(iMaxMaskNum);
for (int i = 0; i < n; i++)
{
v[1 << i] = p[i];
}
for (int mask = 1; mask < iMaxMaskNum ; mask++)
{
const int iSubMask = mask&(-mask);
v[mask] = v[iSubMask] + v[mask-iSubMask];
}
}
class CMaxLineTree
{
public:
CMaxLineTree(int iArrSize) :m_iArrSize(iArrSize), m_vData(iArrSize * 4)
{

}
 //iIndex 从0开始
 void Modify( int iIndex, int iValue)
 {
   Modify(1, 1, m_iArrSize, iIndex + 1, iValue);
 }
 //iNeedQueryLeft iNeedQueryRight 从0开始
 int Query(const int iNeedQueryLeft, const int iNeedQueryRight)
 {
   return Query(1, 1, m_iArrSize, iNeedQueryLeft + 1, iNeedQueryRight + 1);
 }

protected:
int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight)
{
if ((iNeedQueryLeft <= iRecordLeft) && (iNeedQueryRight >= iRecordRight))
{
return m_vData[iTreeNodeIndex];
}
const int iMid = (iRecordLeft + iRecordRight) / 2;
int iRet = 0;
if (iNeedQueryLeft <= iMid)
{
iRet = Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight);
}
if (iNeedQueryRight > iMid)
{
iRet = max(iRet, Query(iTreeNodeIndex * 2 + 1, iMid + 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight));
}
return iRet;
}
void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue)
{
if (iLeft == iRight)
{
m_vData[iTreeNodeIndex] = max(m_vData[iTreeNodeIndex],iValue);
return;
}
const int iMid = (iLeft + iRight) / 2;
if (iIndex <= iMid)
{
Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue);
}
else
{
Modify(iTreeNodeIndex * 2 + 1, iMid + 1, iRight, iIndex, iValue);
}
m_vData[iTreeNodeIndex] = max(m_vData[iTreeNodeIndex * 2], m_vData[iTreeNodeIndex * 2 + 1]);
}
const int m_iArrSize;
std::vector m_vData;
};
class CMaxLineTreeMap
{
public:
CMaxLineTreeMap(int iArrSize) :m_iArrSize(iArrSize)
{

}
 //iIndex 从0开始
 void Modify(int iIndex, int iValue)
 {
   Modify(1, 1, m_iArrSize, iIndex + 1, iValue);
 }
 //iNeedQueryLeft iNeedQueryRight 从0开始
 int Query(const int iNeedQueryLeft, const int iNeedQueryRight)
 {
   return Query(1, 1, m_iArrSize, iNeedQueryLeft + 1, iNeedQueryRight + 1);
 }

protected:
int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight)
{
if ((iNeedQueryLeft <= iRecordLeft) && (iNeedQueryRight >= iRecordRight))
{
return m_mData[iTreeNodeIndex];
}
const int iMid = (iRecordLeft + iRecordRight) / 2;
int iRet = 0;
if (iNeedQueryLeft <= iMid)
{
iRet = Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight);
}
if (iNeedQueryRight > iMid)
{
iRet = max(iRet, Query(iTreeNodeIndex * 2 + 1, iMid + 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight));
}
return iRet;
}
void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue)
{
if (iLeft == iRight)
{
m_mData[iTreeNodeIndex] = max(m_mData[iTreeNodeIndex], iValue);
return;
}
const int iMid = (iLeft + iRight) / 2;
if (iIndex <= iMid)
{
Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue);
}
else
{
Modify(iTreeNodeIndex * 2 + 1, iMid + 1, iRight, iIndex, iValue);
}
m_mData[iTreeNodeIndex] = max(m_mData[iTreeNodeIndex * 2], m_mData[iTreeNodeIndex * 2 + 1]);
}
const int m_iArrSize;
std::unordered_map m_mData;
};
template
class CSumLineTree
{
public:
CSumLineTree(int iEleSize) :m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4), m_vChildAdd(m_iEleSize * 4)
{

}
 void Add(int iLeftIndex, int iRightIndex, int iValue)
 {
   Add(1, 1, m_iEleSize, iLeftIndex+1, iRightIndex+1, iValue);
 }
 T Query(int iLeftIndex, int iRightIndex)
 {
   return Query(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
 }

private:
T Query(int iNode, int iDataLeft, int iDataRight, int iOpeLeft, int iOpeRight)
{
if ((iOpeLeft <= iDataLeft) && (iOpeRight >= iDataRight))
{
return m_vArr[iNode];
}
Fresh(iNode, iDataLeft, iDataRight);
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
T ret(0);
if (iMid >= iOpeLeft)
{
ret += Query(iNode * 2, iDataLeft, iMid, iOpeLeft, iOpeRight);
}
if (iMid + 1 <= iOpeRight)
{
ret += Query(iNode * 2 + 1, iMid + 1, iDataRight, iOpeLeft, iOpeRight);
}
return ret;
}
/* 暴力解法
void Add(int iNode, int iDataLeft, int iDataRight, int iOpeLeft, int iOpeRight, int iValue)
{
m_vArr[iNode] += T(iValue)*(min(iDataRight, iOpeRight) - max(iDataLeft, iOpeLeft)+1);
if (iDataLeft == iDataRight)
{
return;
}
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
if (iMid >= iOpeLeft)
{
Add(iNode * 2, iDataLeft, iMid, iOpeLeft, iOpeRight, iValue);
}
if (iMid + 1 <= iOpeRight)
{
Add(iNode * 2 + 1, iMid + 1, iDataRight, iOpeLeft, iOpeRight, iValue);
}
}
/
void Fresh(int iNode, int iDataLeft, int iDataRight)
{
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
if (m_vChildAdd[iNode] != 0)
{
Add(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vChildAdd[iNode]);
Add(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_vChildAdd[iNode]);
m_vChildAdd[iNode] = 0;
}
}
//懒惰法
void Add(int iNode, int iDataLeft, int iDataRight, int iOpeLeft, int iOpeRight, int iValue)
{
m_vArr[iNode] += T(iValue)(min(iDataRight, iOpeRight) - max(iDataLeft, iOpeLeft) + 1);
if ((iOpeLeft <= iDataLeft) && (iOpeRight >= iDataRight))
{
m_vChildAdd[iNode] += T(iValue);
return;
}

Fresh(iNode,iDataLeft,iDataRight);
   const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
   if (iMid >= iOpeLeft)
   {
     Add(iNode * 2, iDataLeft, iMid, iOpeLeft, iOpeRight, iValue);
   }
   if (iMid + 1 <= iOpeRight)
   {
     Add(iNode * 2 + 1, iMid + 1, iDataRight, iOpeLeft, iOpeRight, iValue);
   }
 }
 const int m_iEleSize;
 vector<T> m_vArr;
 vector<int> m_vChildAdd;

};
template
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize+1)
{

}
 void Add(int index, T value)
 {
   index++;
   while (index < m_vData.size())
   {
     m_vData[index] += value;
     index += index&(-index);
   }
 }
 T Sum(int index)
 {
   index++;
   T ret = 0;
   while (index )
   {
     ret += m_vData[index];
     index -= index&(-index);
   }
   return ret;
 }
 T Get(int index)
 {
   return Sum(index) - Sum(index - 1);
 }

private:
vector m_vData;
};
//iCodeNum 必须大于等于可能的字符数
template
class CHashStr {
public:
CHashStr(string s, int iCodeNum, int iCodeBegin = 1, char chBegin = ‘a’) {
m_c = s.length();
m_vP.resize(m_c + 1);
m_vP[0] = 1;
m_vHash.resize(m_c + 1);
for (int i = 0; i < m_c; i++)
{
const int P = iCodeBegin + iCodeNum;
m_vHash[i + 1] = m_vHash[i] * P + s[i] - chBegin + iCodeBegin;
m_vP[i + 1] = m_vP[i] * P;
}
}
int GetHash(int left, int right)
{
return ( m_vHash[right + 1] - m_vHash[left] * m_vP[right - left + 1]).ToInt();
}
inline int GetHash(int right)
{
return m_vHash[right + 1].ToInt();
}
int m_c;
vector m_vP;
vector m_vHash;
};
template
class C2HashStr
{
public:
C2HashStr(string s) {
m_pHash1 = std::make_unique>(s, 26);
m_pHash2 = std::make_unique < CHashStr>(s, 27, 0);
}

long long GetHash(int left, int right)
 {
   return (long long)m_pHash1->GetHash(left, right)*(MOD2 + 1) + m_pHash2->GetHash(left, right);
 }
 long long GetHash( int right)
 {
   return (long long)m_pHash1->GetHash( right)*(MOD2 + 1) + m_pHash2->GetHash( right);
 }

private:
std::unique_ptr> m_pHash1;
std::unique_ptr m_pHash2;
};
template
class CDynaHashStr {
public:
CDynaHashStr(int iCodeNum, int iCodeBegin = 1, char chBegin = ‘a’) :m_iUnit(iCodeNum + iCodeBegin), m_iP(1), m_iBegin(iCodeBegin - chBegin)
{

}
 inline void push_back(const char& ch)
 {
  const int iNum = ch + m_iBegin;
  m_iHash *= m_iUnit;
  m_iHash += iNum;
  m_iP *= m_iUnit;
 }
 inline void push_front(const char& ch)
 {
   const int iNum = ch + m_iBegin;
   m_iHash +=  m_iP*iNum;
   m_iP *= m_iUnit;
 }
 inline int GetHash() const
 {
   return m_iHash;
 }
 const int m_iUnit;
 const int m_iBegin;
 C1097Int<MOD> m_iHash;
 C1097Int<MOD> m_iP;

};
template
class C2DynaHashStr {
public:
C2DynaHashStr(int iCodeNum, int iCodeBegin = 1, char chBegin = ‘a’)
{
m_pHash1 = new CDynaHashStr<>(iCodeNum, iCodeBegin, chBegin);
m_pHash2 = new CDynaHashStr(iCodeNum, iCodeBegin, chBegin);
}
~C2DynaHashStr()
{
delete m_pHash1;
delete m_pHash2;
}
inline void push_back(const char& ch)
{
m_pHash1->push_back(ch);
m_pHash2->push_back(ch);
}
inline void push_front(const char& ch)
{
m_pHash1->push_front(ch);
m_pHash2->push_front(ch);
}
long long Hash()const
{
return (long long)MOD2m_pHash1->m_iHash.ToInt() + m_pHash2->m_iHash.ToInt();
}
bool operator==(const C2DynaHashStr& other) const
{
return (m_pHash1->m_iHash.ToInt() == other.m_pHash1->m_iHash.ToInt()) && (m_pHash2->m_iHash.ToInt() == other.m_pHash2->m_iHash.ToInt());
}
CDynaHashStr<> m_pHash1;
CDynaHashStr* m_pHash2 ;
};
namespace NSort
{
template
bool SortVecVec(const vector& v1, const vector& v2)
{
return v1[ArrIndex] < v2[ArrIndex];
};
}
namespace NCmp
{
template
bool Less(const std::pair& p, Class1 iData)
{
return p.first < iData;
}

template<class Class1>
 bool  Greater(const std::pair<Class1, int>& p, Class1 iData)
 {
   return p.first > iData;
 }
template<class _Ty1,class _Ty2>
class CLessPair
{
public:
  bool operator()(const std::pair<_Ty1, _Ty2>& p1, const std::pair<_Ty1, _Ty2>& p2)const
  {
    return p1.first < p2.first;
  }
};
template<class _Ty1, class _Ty2>
class CGreatePair
{
public:
  bool operator()(const std::pair<_Ty1, _Ty2>& p1, const std::pair<_Ty1, _Ty2>& p2)const
  {
    return p1.first > p2.first;
  }
};

}
class CIndexVector
{
public:
template
CIndexVector(vector& data)
{
for (int i = 0; i < data.size(); i++)
{
m_indexs.emplace_back(i);
}
std::sort(m_indexs.begin(), m_indexs.end(), [data](const int& i1, const int& i2)
{
return data[i1] < data[i2];
});
}
int GetIndex(int index)
{
return m_indexs[index];
}
private:
vector m_indexs;
};
class CMedian
{
public:
void AddNum(int iNum)
{
m_queTopMin.emplace(iNum);
MakeNumValid();
MakeSmallBig();
}
void Remove(int iNum)
{
if (m_queTopMax.size() && (iNum <= m_queTopMax.top()))
{
m_setTopMaxDel.insert(iNum);
}
else
{
m_setTopMinDel.insert(iNum);
}

PopIsTopIsDel(m_queTopMin, m_setTopMinDel);
  PopIsTopIsDel(m_queTopMax, m_setTopMaxDel);
  MakeNumValid();
  MakeSmallBig();
}
double Median()
{
  const int iMaxNum = m_queTopMin.size() - m_setTopMinDel.size();
  const int iMinNum = m_queTopMax.size() - m_setTopMaxDel.size();
  if (iMaxNum > iMinNum)
  {
    return m_queTopMin.top();
  }
  return ((double)m_queTopMin.top() + m_queTopMax.top())/2.0;
}
template<class T>
void PopIsTopIsDel(T& que, std::unordered_multiset<int>& setTopMaxDel)
{
  while (que.size() && (setTopMaxDel.count(que.top())))
  {
    setTopMaxDel.erase(setTopMaxDel.find(que.top()));
    que.pop();
  }
}
void MakeNumValid()
{
  const int iMaxNum = m_queTopMin.size() - m_setTopMinDel.size();
  const int iMinNum = m_queTopMax.size() - m_setTopMaxDel.size();
  //确保两个队的数量
  if (iMaxNum > iMinNum + 1)
  {
    int tmp = m_queTopMin.top();
    m_queTopMin.pop();
    m_queTopMax.emplace(tmp);
    PopIsTopIsDel(m_queTopMin, m_setTopMinDel);
  }
  if (iMinNum > iMaxNum)
  {
    int tmp = m_queTopMax.top();
    m_queTopMax.pop();
    m_queTopMin.push(tmp);
    PopIsTopIsDel(m_queTopMax, m_setTopMaxDel);
  }
}
void MakeSmallBig()
{
  if (m_queTopMin.empty() || m_queTopMax.empty())
  {
    return;
  }
  while (m_queTopMin.top() < m_queTopMax.top())
  {
    const int iOldTopMin = m_queTopMin.top();
    const int iOldTopMax = m_queTopMax.top();
    m_queTopMin.pop();
    m_queTopMax.pop();
    m_queTopMin.emplace(iOldTopMax);
    m_queTopMax.emplace(iOldTopMin);
    PopIsTopIsDel(m_queTopMin, m_setTopMinDel);
    PopIsTopIsDel(m_queTopMax, m_setTopMaxDel);
  }
}
std::priority_queue<int> m_queTopMax;
std::priority_queue<int, vector<int>, greater<int>> m_queTopMin;
std::unordered_multiset<int> m_setTopMaxDel, m_setTopMinDel;

};
template
class CDistanceGrid
{
public:
CDistanceGrid(const vector& grid) :m_grid(grid), m_r(grid.size()), m_c(grid[0].size())
{

}
//单源路径 D 算法 ,时间复杂度:r*c*log(r*c)
inline int Dis(int r1, int c1, int r2, int c2)
{ 
  vector<vector<int>> vDis(iMaxRow, vector<int>(iMaxCol, INT_MAX));
  auto Add = [&vDis, this](std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>>& queCur, int iDis, int r, int c)
  {
    const int iRowColMask = iMaxCol * r + c;
    if (iDis >= vDis[r][c])
    {
      return;
    }
    queCur.emplace(iDis,iRowColMask);
    vDis[r][c] = iDis;
  };
  auto Move = [&](std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>>& queCur, int iDis, int r, int c)
  {
    if ((r < 0) || (r >= m_r))
    {
      return;
    }
    if ((c < 0) || (c >= m_c))
    {
      return;
    }
    if (m_grid[r][c] < 1)
    {
      return;
    }
    Add(queCur,iDis, r, c);
  };
  std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>> que;    
  Add(que,0,r1, c1);
  while (que.size())
  {
    const int iDis = que.top().first;
    const int iStart = que.top().second;
    que.pop();
    const int r = iStart / iMaxCol;
    const int c = iStart % iMaxCol;
    if ((r == r2) && (c == c2))
    {
      return iDis;
    }
    if (iDis > vDis[r][c])
    {
      continue;
    }
    Move(que, iDis + 1, r + 1, c);
    Move(que, iDis + 1, r - 1, c);
    Move(que, iDis + 1, r, c + 1);
    Move(que, iDis + 1, r, c - 1);
  }
  return -1;
}

private:
virtual bool IsCanMoveStatue(int r, int c)
{
return m_grid[r][c] >= 1;
}
const int m_r;
const int m_c;
const vector& m_grid;
};
class CBFSGridDist
{
public:
CBFSGridDist(const vector& bCanVisit, int r, int c) :m_bCanVisit(bCanVisit), m_r(m_bCanVisit.size()), m_c(m_bCanVisit[0].size())
{
m_vDis.assign(m_r, vector(m_c,INT_MAX/2));
Dist(r, c);
}
bool Vilid(const int r,const int c )
{
if ((r < 0) || (r >= m_r))
{
return false;
}
if ((c < 0) || (c >= m_c))
{
return false;
}
return true;
}
const vector& Dis()const
{
return m_vDis;
}
const vector& m_bCanVisit;
private:
//INT_MAX/2 表示无法到达
void Dist(int r, int c)
{
m_vDis.assign(m_r, vector(m_c, INT_MAX / 2));
vector vHasDo(m_r, vector(m_c));
std::queue> que;
auto Add = [&](const int& r, const int& c, const int& iDis)
{
if (!Vilid(r, c))
{
return;
}
if (vHasDo[r][c])
{
return;
}
if (!m_bCanVisit[r][c])
{
vHasDo[r][c] = true;
return;
}
if (iDis >= m_vDis[r][c])
{
return;
}

que.emplace(r, c);
    m_vDis[r][c] = iDis;
    vHasDo[r][c] = true;
  };
  Add(r, c, 0);
  while (que.size())
  {
    const int r = que.front().first;
    const int c = que.front().second;
    que.pop();
    const int iDis = m_vDis[r][c];
    Add(r + 1, c, iDis + 1);
    Add(r - 1, c, iDis + 1);
    Add(r, c + 1, iDis + 1);
    Add(r, c - 1, iDis + 1);
  }
}
vector<vector<int>> m_vDis;
const int m_r;
const int m_c;

};
class C2BNumTrieNode
{
public:
C2BNumTrieNode()
{
m_childs[0] = m_childs[1] = nullptr;
}
bool GetNot0Child(bool bFirstRight)
{
auto ptr = m_childs[bFirstRight];
if (ptr && (ptr->m_iNum >0))
{
return bFirstRight;
}
return !bFirstRight;
}
int m_iNum = 0;
C2BNumTrieNode* m_childs[2];
};
template
class C2BNumTrie
{
public:
C2BNumTrie()
{
m_pRoot = new C2BNumTrieNode();
}
void Add(int iNum)
{
m_setHas.emplace(iNum);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveNum - 1; i >= 0; i–)
{
p->m_iNum++;
bool bRight = iNum & (1 << i);
if (nullptr == p->m_childs[bRight])
{
p->m_childs[bRight] = new C2BNumTrieNode();
}
p = p->m_childs[bRight];
}
p->m_iNum++;
}
void Del(int iNum)
{
auto it = m_setHas.find(iNum);
if (m_setHas.end() == it)
{
return;
}
m_setHas.erase(it);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveNum - 1; i >= 0; i–)
{
p->m_iNum–;
bool bRight = iNum & (1 << i);
p = p->m_childs[bRight];
}
p->m_iNum–;
}
int MaxXor(int iNum)
{
C2BNumTrieNode* p = m_pRoot;
int iRet = 0;
for (int i = iLeveNum - 1; i >= 0; i–)
{
bool bRight = !(iNum & (1 << i));
bool bSel = p->GetNot0Child(bRight);
p = p->m_childs[bSel];
if (bSel == bRight)
{
iRet |= (1 << i);
}
}
return iRet;
}
C2BNumTrieNode* m_pRoot;
std::unordered_multiset m_setHas;
};
struct SValueItem
{
SValueItem()
{

}
SValueItem(int iValue)
{
  m_iCoefficient = iValue;
}
SValueItem operator*(const SValueItem& o)const
{
  SValueItem ret(m_iCoefficient*o.m_iCoefficient);
  int i = 0, j = 0;
  while ((i < m_vVars.size()) && (j < o.m_vVars.size()))
  {
    if (m_vVars[i] < o.m_vVars[j])
    {
      ret.m_vVars.emplace_back(m_vVars[i]);
      i++;
    }
    else
    {
      ret.m_vVars.emplace_back(o.m_vVars[j]);
      j++;
    }
  }
  ret.m_vVars.insert(ret.m_vVars.end(), m_vVars.begin()+i, m_vVars.end());
  ret.m_vVars.insert(ret.m_vVars.end(), o.m_vVars.begin()+j, o.m_vVars.end());
  return ret;
}
bool operator<(const SValueItem& o)const
{
  if (m_vVars.size() == o.m_vVars.size())
  {
    return m_vVars < o.m_vVars;
  }
  return m_vVars.size() > o.m_vVars.size();
}
vector<std::string> m_vVars;
int m_iCoefficient=1;//系数、倍率
std::string ToString()const
{
  std::ostringstream os;
  os << m_iCoefficient ;
  for (const auto&s : m_vVars)
  {
    os << "*" << s;
  }
  return os.str();
}

};
struct SValue
{
SValue()
{

}
SValue(int iValue)
{
  SValueItem item;
  item.m_iCoefficient = iValue;
  m_items.emplace(item);
}
SValue(std::string strName)
{
  SValueItem item;
  item.m_vVars.emplace_back(strName);
  m_items.emplace(item);
}
SValue operator-(const SValue& o)const
{
  SValue ret;
  ret.m_items = m_items;
  for (auto it : o.m_items)
  {
    ret -= it;
  }
  return ret;
}
SValue operator+(const SValue& o)const
{
  SValue ret;
  ret.m_items = m_items;
  for (auto it : o.m_items)
  {
    ret += it;
  }     
  return ret;
}
SValue operator*(const SValue& o)const
{
  SValue ret;
  for (const auto it : m_items)
  {
    for (const auto ij : o.m_items)
    {
      ret += it*ij;
    }
  }
  return ret;
}
SValue& operator+=(const SValueItem& item)
{
  auto it = m_items.find(item);
  if (m_items.end() == it)
  {
    m_items.emplace(item);
  }
  else
  {
    auto tmp = *it;
    tmp.m_iCoefficient += item.m_iCoefficient;
    m_items.erase(it);
    m_items.emplace(tmp);
  }
  return *this;
}
SValue& operator-=(const SValueItem& item)
{
  auto it = m_items.find(item);
  if (m_items.end() == it)
  {
    auto tmp = item;
    tmp.m_iCoefficient *= -1;
    m_items.emplace(tmp);
  }
  else
  {
    auto tmp = *it;
    tmp.m_iCoefficient -= item.m_iCoefficient;
    m_items.erase(it);
    m_items.emplace(tmp);
  }
  return *this;
}
vector<std::string> ToStrings()const
{
  vector<std::string> vRet;
  for (const auto& item : m_items)
  {
    if (0 == item.m_iCoefficient)
    {
      continue;
    }
    vRet.emplace_back(item.ToString());
  }
  return vRet;
}
std::set<SValueItem> m_items;

};
class CDelIndexs
{
public:
CDelIndexs()
{

}
CDelIndexs(int iSize)
{
  Init(iSize);
}
void Init(int iSize)
{
  m_bDels.assign(iSize, false);
  m_vNext.resize(iSize);
  for (int i = 0; i < iSize; i++)
  {
    m_vNext[i] = i + 1;
  }
}
void Del(int index)
{
  if ((index < 0) || (index >= m_vNext.size()))
  {
    return;
  }
  if (m_bDels[index])
  {
    return;
  }
  m_bDels[index] = true;
}
void SetCur(int index)
{
  if (index < 0)
  {
    m_iCur = m_vNext.size();
  }
  else
  {
    m_iCur = FreshCur(index);
  }
}
int NextIndex()
{
  if (m_iCur >= m_vNext.size())
  {
    return -1;
  }
  auto ret = m_iCur;
  SetCur(m_vNext[m_iCur]);
  return ret;
}

private:
int FreshCur(int index)
{
if (index >= m_vNext.size())
{
return m_vNext.size();
}
if (!m_bDels[index])
{
return index;
}

return m_vNext[index] = FreshCur(m_vNext[index]);
}
int m_iCur = 0;
vector<bool> m_bDels;
vector<int> m_vNext;

};
class CUnionFind
{
public:
CUnionFind(int iSize) :m_vConnetNO(iSize), m_vConnectSize(iSize, 1)
{
for (int i = 0; i < iSize; i++)
{
m_vConnetNO[i] = i;
}
m_iConnetSize = iSize;
}
int GetConnectNO(int iNode)
{
int& iConnectNO = m_vConnetNO[iNode];
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectNO(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectNO(iNode1);
const int iConnectNO2 = GetConnectNO(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return ;
}
m_iConnetSize–;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}
int GetAConnectSizeByNode(int iNode)
{
return m_vConnectSize[GetConnectNO(iNode)];
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectNO(iNode1) == GetConnectNO(iNode2);
}
int ConnetSize()const
{
return m_iConnetSize;
}
private:
void UnionConnect(int iFrom, int iTo)
{
m_vConnectSize[iTo] += m_vConnectSize[iFrom];
m_vConnetNO[iFrom] = iTo;
}
vector m_vConnetNO;//各点所在联通区域的编号,本联通区域任意一点的索引，为了增加可理解性，用最小索引
vector m_vConnectSize;//各联通区域点数量
int m_iConnetSize;
};
class CUnionFindMST
{
public:
CUnionFindMST(const int iNodeSize) :m_uf(iNodeSize)
{

}
void AddEdge(const int iNode1, const int iNode2, int iWeight)
{
  if (m_uf.IsConnect(iNode1, iNode2))
  {
    return;
  }
  m_iMST += iWeight;
  m_uf.Union(iNode1, iNode2);
}
void AddEdge(const vector<int>& v )
{
  AddEdge(v[0], v[1], v[2]);
}
int MST()
{
  if (m_uf.ConnetSize() > 1)
  {
    return -1;
  }
  return m_iMST;
}

private:
int m_iMST = 0;
CUnionFind m_uf;
};
class CNearestMST
{
public:
CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize)
{

}
void Init(const vector<vector<int>>& edges)
{
  for (const auto& v : edges)
  {
    Add(v);
  }
}
void Add(const vector<int>& v )
{
  m_vNeiTable[v[0]].emplace_back(v[1], v[2]);
  m_vNeiTable[v[1]].emplace_back(v[0], v[2]);
}
int MST(int start)
{
  int next = start;
  while ((next = AddNode(next)) >= 0);
  return m_iMST;
}
int MST(int iNode1, int iNode2,int iWeight)
{
  m_bDo[iNode1] = true;
  for (const auto& it : m_vNeiTable[iNode1])
  {
    if (m_bDo[it.first])
    {
      continue;
    }
    m_vDis[it.first] = min(m_vDis[it.first],(long long) it.second);
  }
  m_iMST = iWeight;
  int next = iNode2;
  while ((next = AddNode(next)) >= 0);
  return m_iMST;
}

private:
int AddNode(int iCur)
{
m_bDo[iCur] = true;
for (const auto& it : m_vNeiTable[iCur])
{
if (m_bDo[it.first])
{
continue;
}
m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
}

int iMinIndex = -1;
  for (int i = 0; i < m_vDis.size(); i++)
  {
    if (m_bDo[i])
    {
      continue;
    }
    if ((-1 == iMinIndex) || (m_vDis[i] < m_vDis[iMinIndex]))
    {
      iMinIndex =i;   
    }
  }
  if ( -1 != iMinIndex)
  {
    if (INT_MAX == m_vDis[iMinIndex])
    {
      m_iMST = -1;
      return -1;
    }
    m_iMST += m_vDis[iMinIndex];
  }
  return iMinIndex;
}
vector<bool> m_bDo;
vector<long long> m_vDis;
vector < vector<std::pair<int, int>>> m_vNeiTable;
long long m_iMST = 0;

};
typedef pair PAIRLLI;
class CDis
{
public:
static void Dis(vector& vDis, int start, const vector>>& vNeiB)
{
std::priority_queue minHeap;
minHeap.emplace(0, start);
while (minHeap.size())
{
const long long llDist = minHeap.top().first;
const int iCur = minHeap.top().second;
minHeap.pop();
if (-1 != vDis[iCur])
{
continue;
}
vDis[iCur] = llDist;
for (const auto& it : vNeiB[iCur])
{
minHeap.emplace(llDist + it.second, it.first);
}
}

};
class CNearestDis
{
public:
CNearestDis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre)
{

}
void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
{
  m_vDis.assign(m_iSize, -1);
  m_vPre.assign(m_iSize, -1);
  vector<bool> vDo(m_iSize);//点是否已处理
  auto AddNode = [&](int iNode)
  {
    //const int iPreNode = m_vPre[iNode];
    long long llPreDis = m_vDis[iNode];
    vDo[iNode] = true;
    for (const auto& it : vNeiB[iNode])
    {
      if (vDo[it.first])
      {
        continue;
      }
      if ((-1 == m_vDis[it.first]) || (it.second + llPreDis < m_vDis[it.first]))
      {
        m_vDis[it.first] = it.second + llPreDis;
        m_vPre[it.first] = iNode;
      }       
    }
    long long llMinDis = LLONG_MAX;
    int iMinIndex = -1;
    for (int i = 0; i < m_vDis.size(); i++)
    {
      if (vDo[i])
      {
        continue;
      }
      if (-1 == m_vDis[i])
      {
        continue;
      }
      if (m_vDis[i] < llMinDis)
      {
        iMinIndex = i;
        llMinDis = m_vDis[i];
      }
    }
    return (LLONG_MAX == llMinDis) ? -1 : iMinIndex;
  };
  int next = start;
  m_vDis[start] = 0;
  while (-1 != (next= AddNode(next)));
}
void Cal(const int start, vector<vector<int>>& edges)
{
  vector<vector<pair<int, int>>> vNeiB(m_iSize);
  for (int i = 0; i < edges.size(); i++)
  {
    const auto& v = edges[i];
    vNeiB[v[0]].emplace_back(v[1], v[2]);
    vNeiB[v[1]].emplace_back(v[0], v[2]);
  }
  Cal(start, vNeiB);
}
const vector<long long>& DIS;
const vector<int>& PRE;

private:
const int m_iSize;
vector m_vDis;//各点到起点的最短距离
vector m_vPre;//最短路径的前一点
};
class CNeiBo2
{
public:
CNeiBo2(int n, vector& edges, bool bDirect)
{
m_vNeiB.resize(n);
for (const auto& v : edges)
{
m_vNeiB[v[0]].emplace_back(v[1]);
if (!bDirect)
{
m_vNeiB[v[1]].emplace_back(v[0]);
}
}
}
vector m_vNeiB;
};
struct SDecimal
{
SDecimal(int iNum=0, int iDeno = 1)
{
m_iNum = iNum;
m_iDeno = iDeno;
int iGCD = GCD(abs(m_iNum), abs(m_iDeno));
m_iNum /= iGCD;
m_iDeno /= iGCD;
if (m_iDeno < 0)
{
m_iDeno = -m_iDeno;
m_iNum = -m_iNum;
}
}
SDecimal operator*(const SDecimal& o)const
{
return SDecimal(m_iNumo.m_iNum, m_iDenoo.m_iDeno);
}
SDecimal operator/(const SDecimal& o)const
{
return SDecimal(m_iNumo.m_iDeno, m_iDenoo.m_iNum);
}
SDecimal operator+(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDenoo.m_iDeno / iGCD;
return SDecimal(m_iNum(iDeno / m_iDeno) + o.m_iNum*(iDeno / o.m_iDeno), iDeno);
}
SDecimal operator-(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDenoo.m_iDeno / iGCD;
return SDecimal(m_iNum(iDeno / m_iDeno) - o.m_iNum*(iDeno / o.m_iDeno), iDeno);
}
bool operator==(const SDecimal& o)const
{
return (m_iNum == o.m_iNum) && (m_iDeno == o.m_iDeno);
}
bool operator<(const SDecimal& o)const
{
auto tmp = *this - o;
return tmp.m_iNum < 0;
}
int m_iNum=0;//分子
int m_iDeno=1;//分母
};
struct point{
double x, y;
point(double i, double j) :x(i), y(j){}
};
//算两点距离
double dist(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2)(x1 - x2) + (y1 - y2)(y1 - y2));
}
//计算圆心
point CircleCenter(point& a, point& b, int r){
//算中点
point mid((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
//AB距离的一半
double d = dist(a.x, a.y, mid.x, mid.y);
//计算h
double h = sqrt(rr - dd);
//计算垂线
point ba(b.x - a.x, b.y - a.y);
point hd(-ba.y, ba.x);
double len = sqrt(hd.xhd.x + hd.yhd.y);
hd.x /= len, hd.y /= len;
hd.x *= h, hd.y *= h;
return point(hd.x + mid.x, hd.y + mid.y);
}
class C01LineTree
{
public:
C01LineTree(const vector& nums) :m_iEleSize(nums.size())
{
m_arr.resize(m_iEleSize * 4);
Init(nums,1, 1, m_iEleSize);
m_vNeedFreshChilds.assign(m_iEleSize * 4, false);
}
void Rotato(int iLeftZeroIndex,int iRightZeroIndex )
{
int iRotatoLeft = iLeftZeroIndex + 1;
int iRotatoRight = iRightZeroIndex + 1;
Rotato(1, 1, m_iEleSize, iRotatoLeft, iRotatoRight);
}
int Query()
{
return m_arr[1];
}
private:
void Rotato(int iSaveIndex, int iDataBegin, int iDataEnd, int iRotatoLeft, int iRotatoRight)
{
if ((iRotatoLeft <= iDataBegin) && (iRotatoRight >= iDataEnd))
{//整个范围需要更新
RotatoSelf(iSaveIndex, iDataBegin, iDataEnd);
return;
}

int iMid = iDataBegin + (iDataEnd - iDataBegin) / 2;
  if (m_vNeedFreshChilds[iSaveIndex])
  {
    RotatoSelf(iSaveIndex * 2, iDataBegin, iMid);
    RotatoSelf(iSaveIndex * 2 + 1, iMid + 1, iDataEnd);
    m_vNeedFreshChilds[iSaveIndex] = false;
  } 
  if (iMid >= iRotatoLeft)
  {
    Rotato(iSaveIndex * 2, iDataBegin, iMid, iRotatoLeft, iRotatoRight);
  }
  if (iMid + 1 <= iRotatoRight)
  {
    Rotato(iSaveIndex * 2 + 1, iMid + 1, iDataEnd, iRotatoLeft, iRotatoRight);
  }
  m_arr[iSaveIndex] = m_arr[iSaveIndex * 2] + m_arr[iSaveIndex * 2 + 1];
}
void RotatoSelf(int iSaveIndex, int iDataBegin, int iDataEnd)
{
  //总数量 - 翻转后0(翻转前1）的数量
  m_arr[iSaveIndex] = (iDataEnd - iDataBegin + 1) - m_arr[iSaveIndex];
  //懒惰法，标记本节点的子孙节点没更新
  m_vNeedFreshChilds[iSaveIndex] = !m_vNeedFreshChilds[iSaveIndex];
}
void Init(const vector<int>& nums, int iSaveIndex,int iDataBegin, int iDataEnd)
{
  if (iDataBegin == iDataEnd)
  {
    m_arr[iSaveIndex] = nums[iDataBegin - 1];
    return;
  }
  int iMid = iDataBegin + (iDataEnd - iDataBegin) / 2;
  Init(nums, iSaveIndex * 2  , iDataBegin, iMid);
  Init(nums, iSaveIndex * 2 + 1, iMid + 1, iDataEnd);
  m_arr[iSaveIndex] = m_arr[iSaveIndex * 2] + m_arr[iSaveIndex * 2 + 1];
}
const int m_iEleSize;
vector<int> m_arr;
vector<bool> m_vNeedFreshChilds;

};
/*
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode(int x, int iLeft) : val(x), left(new TreeNode(iLeft)), right(nullptr) {}
TreeNode(int x, int iLeft, int iRghit) : val(x), left(new TreeNode(iLeft)), right(new TreeNode(iRghit)) {}
};
namespace NTree
{
TreeNode* Init(const vector& nums, int iNull = 10000)
{
if (0 == nums.size())
{
return nullptr;
}
vector ptrs(nums.size() + 1), ptrParent(1);
for (int i = 0; i < nums.size(); i++)
{
if (iNull == nums[i])
{
continue;
}
const int iNO = i + 1;
ptrs[iNO] = new TreeNode(nums[i]);
ptrParent.emplace_back(ptrs[iNO]);
if (1 == iNO)
{
continue;
}
if (iNO & 1)
{//奇数是右支
ptrParent[iNO / 2]->right = ptrs[iNO];
}
else
{
ptrParent[iNO / 2]->left = ptrs[iNO];
}
}
return ptrs[1];
}
}
*/
class Solution {
public:
int kInversePairs(int n, int k) {
//n为1时，只有一种情况：逆序0
vector> pre = { C1097Int<>(1) };
for (int i = 2; i <= n; i++)
{
const int iNewLen = min(k + 1, (int)pre.size() + i);
vector> dp(iNewLen);
C1097Int<> iSum = 0;
for (int j = 0; j < iNewLen; j++)
{
if (j < pre.size())
{
iSum += pre[j];
}
const int iDelIndex = j - i;
if (iDelIndex >= 0)
{
iSum -= pre[iDelIndex];
}
dp[j] = iSum;
}
pre.swap(dp);
}
return (k < pre.size()) ? pre[k].ToInt() : 0;
}
};

扩展阅读

视频课程

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

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

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

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

+17**

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

【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组

LeetCode629: K 个逆序对数组

动态规划

代码

使用到的类库

核心代码

测试用例

2023年1月版

2023年6月

扩展阅读

视频课程

相关

测试环境

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组

LeetCode629: K 个逆序对数组

动态规划

代码

使用到的类库

核心代码

2023年1月版

2023年6月

扩展阅读

视频课程

相关

测试环境

热门文章

最新文章

相关课程

相关电子书

相关实验场景