【数位dp】【动态规划】【KMP】1397. 找到所有好字符串-阿里云开发者社区

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

LeetCode1397. 找到所有好字符串

给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回好字符串的数目。

好字符串的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。

由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：n = 2, s1 = “aa”, s2 = “da”, evil = “b”

输出：51

解释：总共有 25 个以 ‘a’ 开头的好字符串：“aa”，“ac”，“ad”，…，“az”。还有 25 个以 ‘c’ 开头的好字符串：“ca”，“cc”，“cd”，…，“cz”。最后，还有一个以 ‘d’ 开头的好字符串：“da”。

示例 2：

输入：n = 8, s1 = “leetcode”, s2 = “leetgoes”, evil = “leet”

输出：0

解释：所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 “leet” 开头。所以没有好字符串。

示例 3：

输入：n = 2, s1 = “gx”, s2 = “gz”, evil = “x”

输出：2

提示：

s1.length == n

s2.length == n

s1 <= s2

1 <= n <= 500

1 <= evil.length <= 50

所有字符串都只包含小写英文字母。

动态规划

直接利用封装好的数位模版，自定义状态枚举串的后缀和evi的前缀最长部分。

之前的长度len，如果当前位相同，len+1。

否则，比较最长的前缀，类似KMP。

代码

核心代码

class KMP
{
public:
  virtual int Find(const string& s, const string& t)
  {
    CalLen(t);
    m_vSameLen.assign(s.length(), 0);
    for (int i1 = 0, j = 0; i1 < s.length(); )
    {
      for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
      //i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
      m_vSameLen[i1] = j;
      //t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
      if (0 == j)
      {
        i1++;
        continue;
      }
      const int i2 = i1 + j;
      j = m_vLen[j - 1];
      i1 = i2 - j;//i2不变
    }
    for (int i = 0; i < m_vSameLen.size(); i++)
    {//多余代码是为了增加可测试性
      if (t.length() == m_vSameLen[i])
      {
        return i;
      }
    }
    return -1;
  }
  vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性
  static vector<int> Next(const string& s)
  {
    const int len = s.length();
    vector<int> vNext(len, -1);
    for (int i = 1; i < len; i++)
    {
      int next = vNext[i - 1];
      while ((-1 != next) && (s[next + 1] != s[i]))
      {
        next = vNext[next];
      }
      vNext[i] = next + (s[next + 1] == s[i]);
    }
    return vNext;
  }
protected:
  void CalLen(const string& str)
  {
    m_vLen.resize(str.length());
    for (int i = 1; i < str.length(); i++)
    {
      int next = m_vLen[i - 1];
      while (str[next] != str[i])
      {
        if (0 == next)
        {
          break;
        }
        next = m_vLen[0];
      }
      m_vLen[i] = next + (str[next] == str[i]);
    }
  }
  int m_c;
  vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀 
};
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 ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:
  CLowUperr(int iResutlCount) :m_iResutlCount(iResutlCount)
  {
  }
  void Init(const ELE* pLower, const ELE* pHigh, int iNum)
  {
    m_vPre.assign(4, vector<ResultType>(m_iResutlCount));
    if (iNum <= 0)
    {
      return;
    }
    InitPre(pLower, pHigh);
    iNum--;
    while (iNum--)
    {
      pLower++;
      pHigh++;
      vector<vector<ResultType>> dp(4, vector<ResultType>(m_iResutlCount));
      OnInitDP(dp);
      //处理非边界
      for (auto tmp = minEle; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[0], tmp);
      }
      //处理下边界
      OnEnumOtherBit(dp[1], m_vPre[1], *pLower);
      for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[1], tmp);
      }
      //处理上边界
      OnEnumOtherBit(dp[2], m_vPre[2], *pHigh);
      for (auto tmp = minEle; tmp < *pHigh; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[2], tmp);
      }
      //处理上下边界
      if (*pLower == *pHigh)
      {
        OnEnumOtherBit(dp[3], m_vPre[3], *pLower);
      }
      else
      {
        OnEnumOtherBit(dp[1], m_vPre[3], *pLower);
        for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)
        {
          OnEnumOtherBit(dp[0], m_vPre[3], tmp);
        }
        OnEnumOtherBit(dp[2], m_vPre[3], *pHigh);
      }
      m_vPre.swap(dp);
    }
  }
  /*ResultType Total(int iMinIndex, int iMaxIndex)
  {
    ResultType ret;
    for (int status = 0; status < 4; status++)
    {
      for (int index = iMinIndex; index <= iMaxIndex; index++)
      {
        ret += m_vPre[status][index];
      }
    }
    return ret;
  }*/
protected:
  const int m_iResutlCount;
  void InitPre(const ELE* const pLower, const ELE* const pHigh)
  {
    for (ELE cur = *pLower; cur <= *pHigh; cur++)
    {
      int iStatus = 0;
      if (*pLower == cur)
      {
        iStatus = *pLower == *pHigh ? 3 : 1;
      }
      else if (*pHigh == cur)
      {
        iStatus = 2;
      }
      OnEnumFirstBit(m_vPre[iStatus], cur);
    }
  }
  virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) = 0;
  virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) = 0;
  virtual void OnInitDP(vector<vector<ResultType>>& dp)
  {
  }
  vector<vector<ResultType>> m_vPre;
};
class CCharLowerUper : public CLowUperr<char, C1097Int<>, 'a', 'z'>
{
public:
  CCharLowerUper(string evil):CLowUperr(evil.length())
  {
    m_evil = evil;
    m_vNext = KMP::Next(evil);
  }
  C1097Int<> Total()
  {
    return Total(0, m_iResutlCount - 1);
  }
  C1097Int<> Total(int iMinIndex, int iMaxIndex)
  {
    C1097Int<> ret = 0;
    for (int index = iMinIndex; index <= iMaxIndex; index++)
    {
      C1097Int<> cur = 0;
      for (int status = 0; status < 4; status++)
      {
        cur += m_vPre[status][index];
      }
      ret += cur;
    }
    return ret;
  }
protected:
  virtual void OnEnumFirstBit(vector< C1097Int<>>& vPre, const char curValue)
  {   
    const int mask = curValue == m_evil.front();
    if (mask < m_iResutlCount)
    {
      vPre[mask] += C1097Int<>(1);
    }
  }
  virtual void OnEnumOtherBit(vector< C1097Int<>>& dp, const vector< C1097Int<>>& vPre, char curValue)
  {
    for (int i = 0; i < m_iResutlCount; i++)
    {
      int next = i - 1;
      for (; (-1 != next) && (m_evil[next + 1] != curValue); next = m_vNext[next]);
      const int iNewLen = next + 1 + (m_evil[next + 1] == curValue);
      if (iNewLen < m_iResutlCount)
      {
        dp[iNewLen] += vPre[i];
      }
    }   
  }
  string m_evil;
  vector<int> m_vNext;
};
class Solution {
public:
  int findGoodStrings(int n, string s1, string s2, string evil) {
    C1097Int<> biRet = 0;
    const int len1 = s1.length();
    const int len2 = s2.length();
    if (len1 == len2)
    {
      CCharLowerUper lu(evil);
      lu.Init(s1.c_str(),s2.c_str(), len1);
      return lu.Total().ToInt();
    }
    {
      CCharLowerUper lu(evil);
      lu.Init(s1.c_str(), string(len1, 'z').c_str(), len1);
      biRet += lu.Total();
    }
    for (int i = len1+1; i < len2; i++)
    {
      CCharLowerUper lu(evil);
      lu.Init(string(i, 'a').c_str(), string(i, 'z').c_str(), i);
      biRet += lu.Total();
    }
    CCharLowerUper lu(evil);
    lu.Init(string(len2, 'a').c_str(), s2.c_str(), len2);
    biRet += lu.Total();
    return biRet.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;
  string s1, s2,  evil;
  {
    Solution sln;
    n = 2, s1 = "aa", s2 = "da", evil = "b";
    auto res = sln.findGoodStrings(n, s1, s2, evil);
    Assert(51, res);
  }
  {
    Solution sln;
    n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet";
    auto res = sln.findGoodStrings(n, s1, s2, evil);
    Assert(0, res);
  }
  {
    Solution sln;
    n = 2, s1 = "gx", s2 = "gz", evil = "x";
    auto res = sln.findGoodStrings(n, s1, s2, evil);
    Assert(2, res);
  }
  {
    Solution sln;
    n = 93, s1 = "kazxkmmctdgtrplfggliycskmbfzjkrsthahcrxaaylpdykqfyejwteexytvxgjrbviconioomfpznawsseisfcpfkuvx", 
      s2 = "lajtokckoizywvirjhccouuhjkkshdtzchzmiccujzpeqzcvfekdqjgrbkzrwfnfwhyvzrrrakiausbleeimmthaqqouh", evil = "kpvphwnkrtxuiuhb";
    auto res = sln.findGoodStrings(n, s1, s2, evil);
    Assert(982374807, res);
  }
}

2023年1月15

class C1097Int

{

public:

C1097Int(int iData = 0) :m_iData(iData)

{

}

C1097Int operator+(const C1097Int& o)const

{

return C1097Int((m_iData + o.m_iData) % s_iMod);

}

C1097Int& operator+=(const C1097Int& o)

{

m_iData = (m_iData + o.m_iData) % s_iMod;

return this;
}
C1097Int operator(const C1097Int& o)const

{

return((long long)m_iData o.m_iData) % s_iMod;
}
C1097Int& operator=(const C1097Int& o)

{

m_iData =((long long)m_iData *o.m_iData) % s_iMod;

return *this;

}

int ToInt()const

{

return m_iData;

}

private:

int m_iData = 0;;

static const int s_iMod = 1000000007;

};

int operator+(int iData, const C1097Int& int1097)

{

int iRet = int1097.operator+(C1097Int(iData)).ToInt();

return iRet;

}

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;

}

class Solution {

public:

int findGoodStrings(int n, string s1, string s2, string evil) {

//next[j]表示evil 前j+1个字符，最长相等前后缀，如果某个字符串的尾部j+1个字符和evil的前 j+1 个字符相等，则…尾部next[j]和…next[j]个字符相等

vector next(evil.length(),-1);

for (int i = 1, j = -1; i < next.size(); i++)

{

while ((j>=0) && (evil[i] != evil[j+1]))

{

j = next[j];

}

if (evil[i] == evil[j+1 ])

{

j++;

}

next[i] = j;

}

vector<vector> pre;

pre.assign(4, vector(evil.length() + 1));

pre[3][0] = 1;

for (int i = 0; i < s1.length(); i++ )

{

vector<vector> dp(4, vector(evil.length() + 1));

const char& charLow = s1[i];

const char& charUp = s2[i];

const bool bEqualRange = charLow == charUp;

for (int j = 0; j < evil.length(); j++)

{

for (char chCur = ‘a’; chCur <= ‘z’; chCur++)

{

int iNewEndLen = j;

while (iNewEndLen && (evil[iNewEndLen ] != chCur))

{

iNewEndLen = next[iNewEndLen-1]+1;

}

if (evil[iNewEndLen] == chCur)

{

iNewEndLen++;

}

dp[0][iNewEndLen] += pre[0][j];

//前一个字符卡下限

if (chCur > charLow)

{

dp[0][iNewEndLen] += pre[1][j];

}

else if (charLow == chCur)

{

dp[1][iNewEndLen] += pre[1][j];

}

//前一个字符卡上限

if (chCur < charUp)

{

dp[0][iNewEndLen] += pre[2][j];

}

else if (charUp == chCur)

{

dp[2][iNewEndLen] += pre[2][j];

}

//前一个字符串卡上下限

if ((charUp > chCur) && (charLow < chCur))

{

dp[0][iNewEndLen] += pre[3][j];

}

else if (bEqualRange)

{

if (charUp == chCur)

{

dp[3][iNewEndLen] += pre[3][j];

}

else

{

if (charUp == chCur)

{

dp[2][iNewEndLen] += pre[3][j];

}

if (charLow == chCur)

{

dp[1][iNewEndLen] += pre[3][j];

}

pre.swap(dp);

}

C1097Int sum;

for (int i = 0; i < 4; i++)

{

sum += std::accumulate(pre[i].begin(), pre[i].end() - 1, C1097Int());

}

return sum.ToInt();

}

};

2023年1月第二版

class C1097Int

{

public:

C1097Int(int iData = 0) :m_iData(iData)

{

}
 C1097Int  operator+(const C1097Int& o)const
 {
   return C1097Int((m_iData + o.m_iData) % s_iMod);
 }
 C1097Int&  operator+=(const C1097Int& o)
 {
   m_iData = (m_iData + o.m_iData) % s_iMod;
   return *this;
 }
 C1097Int  operator*(const C1097Int& o)const
 {
   return((long long)m_iData *o.m_iData) % s_iMod;
 }
 C1097Int&  operator*=(const C1097Int& o)
 {
  m_iData =((long long)m_iData *o.m_iData) % s_iMod;
   return *this;
 }
 int ToInt()const
 {
   return m_iData;
 }

private:

int m_iData = 0;;

static const int s_iMod = 1000000007;

};

int operator+(int iData, const C1097Int& int1097)

{

int iRet = int1097.operator+(C1097Int(iData)).ToInt();

return iRet;

}

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;

}

class Solution {

public:

int findGoodStrings(int n, string s1, string s2, string evil) {

//next[j]表示evil 前j+1个字符，最长相等前后缀，前后缀不能是本身

//如果某个字符串的尾部j+1个字符和evil的前 j+1 个字符相等，则…尾部next[j]和…next[j]个字符相等

vector next(evil.length());

for (int i = 1, j = 0; i < next.size(); i++)

{

while ( j && (evil[i] != evil[j]))

{

j = next[j-1];

}

if (evil[i] == evil[j])

{

j++;

}

next[i] = j;

}

vector<vector> pre;

pre.assign(4, vector(evil.length() + 1));

pre[3][0] = 1;

for (int i = 0; i < s1.length(); i++ )

{

vector<vector> dp(4, vector(evil.length() + 1));

const char& charLow = s1[i];

const char& charUp = s2[i];

const bool bEqualRange = charLow == charUp;

for (int j = 0; j < evil.length(); j++)

{

for (char chCur = ‘a’; chCur <= ‘z’; chCur++)

{

int iNewEndLen = j;

while (iNewEndLen && (evil[iNewEndLen ] != chCur))

{

iNewEndLen = next[iNewEndLen-1];

}

if (evil[iNewEndLen] == chCur)

{

iNewEndLen++;

}

dp[0][iNewEndLen] += pre[0][j];

//前一个字符卡下限

if (chCur > charLow)

{

dp[0][iNewEndLen] += pre[1][j];

}

else if (charLow == chCur)

{

dp[1][iNewEndLen] += pre[1][j];

}

//前一个字符卡上限

if (chCur < charUp)

{

dp[0][iNewEndLen] += pre[2][j];

}

else if (charUp == chCur)

{

dp[2][iNewEndLen] += pre[2][j];

}

//前一个字符串卡上下限

if ((charUp > chCur) && (charLow < chCur))

{

dp[0][iNewEndLen] += pre[3][j];

}

else if (bEqualRange)

{

if (charUp == chCur)

{

dp[3][iNewEndLen] += pre[3][j];

}

else

{

if (charUp == chCur)

{

dp[2][iNewEndLen] += pre[3][j];

}

if (charLow == chCur)

{

dp[1][iNewEndLen] += pre[3][j];

}

pre.swap(dp);

}

C1097Int sum;

for (int i = 0; i < 4; i++)

{

sum += std::accumulate(pre[i].begin(), pre[i].end() - 1, C1097Int());

}

return sum.ToInt();

}

};

2023年9月

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 ELE>
static void Out(const vector<ELE>& vec, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
  OutToConsoleInner(vec, strColSep);
  std::cout << strRowSep.c_str();
}
template<class ELE>
static void Out(const vector<vector<ELE>>& 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 ELE>
static void Out(const std::map<ELE, 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 ELE  >
static void Out(const ELE& 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<int, vector, std::greater > 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<CPeo*> m_childs;

CPeo* m_pParent = nullptr;

};

//通过 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 ELE& 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 TData, TData defData,int iTypeNum = 26, char cBegin = ‘a’>

class CTrie

{

public:

CTrie()

{

}
template<class IT>
CTrie* Add(IT begin, IT end)
{
  CTrie* pNode = this;
  for (; begin != end; ++begin)
  {
    pNode = pNode->AddChar(*begin);
  }
  return pNode;
}
template<class IT>
CTrie* Search(IT begin, IT end)
{
  if (begin == end)
  {
    return this;
  }
  if ('.' == *begin)
  {
    for (auto& ptr : m_vPChilds)
    {
      if (!ptr)
      {
        continue;
      }
      auto pSearch = ptr->Search(begin + 1, end);
      if (pSearch)
      {
        return pSearch;
      }
    }
    return nullptr;
  }
  auto ptr = GetChild(*begin);
  if (nullptr == ptr)
  {
    return nullptr;
  }
  return ptr->Search(begin + 1, end);
}
TData m_data = defData;
CTrie* 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] = new CTrie();
  }
  return m_vPChilds[index];
}
CTrie* GetChild(char ch)const
{
  if ((ch < cBegin) || (ch >= cBegin + iTypeNum))
  {
    return nullptr;
  }
  return m_vPChilds[ch - cBegin];
}

protected:

CTrie* m_vPChilds[iTypeNum] = { nullptr };

};

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(ELE* seft, const ELE& other)

{

*seft = min(*seft, other);

}

template

void MaxSelf(ELE* seft, const ELE& 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);
}
//返回第一个大于等于iMax的节点索引，没有大于等于iMax，则返回-1
int GetFirstMaxIndex(int iMax)
{
  int iNO = 1;
  if (m_vData[1] < iMax)
  {
    return -1;
  }
  int left = 1, r = m_iArrSize;
  while (r > left)
  {
    const int mid = (left + r) / 2;
    if (m_vData[iNO * 2] < iMax)
    {
      iNO = iNO * 2 + 1;
      left = mid + 1;
    }
    else
    {
      iNO *= 2;
      r = mid;
    }
  }
  return r - 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] = 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] = 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<int, int> 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);
}
ELE Query(int iLeftIndex, int iRightIndex)
{
  return Query(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
}

private:

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

ELE 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] += ELE(iValue) * (min(iDataRight, iOpeRight) - max(iDataLeft, iOpeLeft) + 1);

if ((iOpeLeft <= iDataLeft) && (iOpeRight >= iDataRight))

{

m_vChildAdd[iNode] += ELE(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<ELE> m_vArr;
vector<int> m_vChildAdd;

};

template

class CTreeArr

{

public:

CTreeArr(int iSize) :m_vData(iSize + 1)

{

}
void Add(int index, ELE value)
{
  index++;
  while (index < m_vData.size())
  {
    m_vData[index] += value;
    index += index & (-index);
  }
}
ELE Sum(int index)
{
  index++;
  ELE ret = 0;
  while (index)
  {
    ret += m_vData[index];
    index -= index & (-index);
  }
  return ret;
}
ELE 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;

}

//iMinValue将被编码为0,iMaxValue被编码为iMaxValue-iMinValue。

CHashStr(const int* data,int len, int iMinValue = 0, int iMaxValue = 9 ) {

m_c = len;

m_vP.resize(m_c + 1);

m_vP[0] = 1;

m_vHash.resize(m_c + 1);

const int P = iMaxValue - iMinValue + 1;

for (int i = 0; i < m_c; i++)

{

const int iCurCode = data[i] - iMinValue;

assert((iCurCode >= 0) && (iCurCode < P));

m_vHash[i + 1] = m_vHash[i] * P + iCurCode;

m_vP[i + 1] = m_vP[i] * P;

}

//包括left right

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 GetHashExincludeRight(int left, int right)

{

return (m_vHash[right ] - m_vHash[left] * m_vP[right - left ]).ToInt();

}

inline int GetHashExincludeRight(int right)

{

return m_vHash[right].ToInt();

}

int m_c;

vector<C1097Int> m_vP;

vector<C1097Int> m_vHash;

};

template

class C2HashStr

{

public:

C2HashStr(string s) {

m_pHash1 = std::make_unique<CHashStr<>>(s, 26);

m_pHash2 = std::make_unique < CHashStr>(s, 27, 0);

}

C2HashStr(const int* data, int len, int iMinValue = 0, int iMaxValue = 9)

{

m_pHash1 = std::make_unique<CHashStr<>>(data, len, iMinValue, iMaxValue);

m_pHash2 = std::make_unique < CHashStr>(data, len, iMinValue, iMaxValue);

}

//包括left right

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

}

//包括Left，不包括Right

long long GetHashExincludeRight(int left, int right)

{

return (long long)m_pHash1->GetHashExincludeRight(left, right) * (MOD2 + 1) + m_pHash2->GetHashExincludeRight(left, right);

}

long long GetHashExincludeRight(int right)

{

return (long long)m_pHash1->GetHashExincludeRight(right) * (MOD2 + 1) + m_pHash2->GetHashExincludeRight(right);

}

private:

std::unique_ptr<CHashStr<>> m_pHash1;

std::unique_ptr<CHashStr> 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)MOD2 * m_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];

};

template<class T >
void ShellSort(vector<T>& v)
{
  T tMax = *std::max_element(v.begin(), v.end());
  T exp = 1;
  while (tMax >= exp)
  {
    int vNums[10] = { 0 };
    for (const auto& n : v)
    {
      vNums[n / exp % 10]++;
    }
    int indexs[10] = { 0 };
    for (int i = 1; i < 10; i++)
    {
      indexs[i] = vNums[i - 1] + indexs[i-1];
    }
    vector<T> tmp(v.size());
    for (const auto& n : v)
    {
      const int cur = n / exp % 10;
      tmp[indexs[cur]] = n;
      indexs[cur]++;
    }
    v.swap(tmp);
    exp *= 10;
  }
}
template<class T,class _Pr = less<T> >
void MergeSort(vector<T>& v, const vector<T>& v1, const vector<T>& v2)
{
  int i1 = 0, i2 = 0;
  while ((i1 < v1.size()) && (i2 < v2.size()))
  {
    if (std::less()(v1[i1], v2[i2]))
    {
      v.emplace_back(v1[i1++]);
    }
    else
    {
      v.emplace_back(v2[i2++]);
    }
  }
  while (i1 < v1.size())
  {
    v.emplace_back(v1[i1++]);
  }
  while (i2 < v2.size())
  {
    v.emplace_back(v2[i2++]);
  }
}

}

namespace NCmp

{

template

bool Less(const std::pair<Class1, int>& 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 ELE>
void PopIsTopIsDel(ELE& 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<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<vector>& m_grid;

};

class CBFSGridDist

{

public:

CBFSGridDist(const vector<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<vector>& Dis()const

{

return m_vDis;

}

const vector<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<vector> vHasDo(m_r, vector(m_c));

std::queue<std::pair<int, int>> 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_vNodeToRegion(iSize)

{

for (int i = 0; i < iSize; i++)

{

m_vNodeToRegion[i] = i;

}

m_iConnetRegionCount = iSize;

}

int GetConnectRegionIndex(int iNode)

{

int& iConnectNO = m_vNodeToRegion[iNode];

if (iNode == iConnectNO)

{

return iNode;

}

return iConnectNO = GetConnectRegionIndex(iConnectNO);

}

void Union(int iNode1, int iNode2)

{

const int iConnectNO1 = GetConnectRegionIndex(iNode1);

const int iConnectNO2 = GetConnectRegionIndex(iNode2);

if (iConnectNO1 == iConnectNO2)

{

return;

}

m_iConnetRegionCount–;

if (iConnectNO1 > iConnectNO2)

{

UnionConnect(iConnectNO1, iConnectNO2);

}

else

{

UnionConnect(iConnectNO2, iConnectNO1);

}

bool IsConnect(int iNode1, int iNode2)
{
  return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
  return m_iConnetRegionCount;
}
vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
{
  const int iNodeSize = m_vNodeToRegion.size();
  vector<int> vRet(iNodeSize);
  for (int i = 0; i < iNodeSize; i++)
  {
    vRet[GetConnectRegionIndex(i)]++;
  }
  return vRet;
}

private:

void UnionConnect(int iFrom, int iTo)

{

m_vNodeToRegion[iFrom] = iTo;

}

vector m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引

int m_iConnetRegionCount;

};

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.GetConnetRegionCount() > 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<long long, int> PAIRLLI;

class CDis

{

public:

static void Dis(vector& vDis, int start, const vector<vector<pair<int, int>>>& vNeiB)

{

std::priority_queue<PAIRLLI, vector, greater> 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<vector>& edges, bool bDirect,int iBase=0)

{

m_vNeiB.resize(n);

for (const auto& v : edges)

{

m_vNeiB[v[0]- iBase].emplace_back(v[1]- iBase);

if (!bDirect)

{

m_vNeiB[v[1]- iBase].emplace_back(v[0]- iBase);

}

vector<vector> m_vNeiB;

};

class CNeiBo3

{

public:

CNeiBo3(int n, vector<vector>& edges, bool bDirect, int iBase = 0)

{

m_vNeiB.resize(n);

for (const auto& v : edges)

{

m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase,v[2]);

if (!bDirect)

{

m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase,v[2]);

}

vector<vector<std::pair<int,int>>> 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_iNum * o.m_iNum, m_iDeno * o.m_iDeno);

}

SDecimal operator/(const SDecimal& o)const

{

return SDecimal(m_iNum * o.m_iDeno, m_iDeno * o.m_iNum);

}

SDecimal operator+(const SDecimal& o)const

{

const int iGCD = GCD(m_iDeno, o.m_iDeno);

const int iDeno = m_iDeno * o.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_iDeno * o.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(r * r - d * d);

//计算垂线

point ba(b.x - a.x, b.y - a.y);

point hd(-ba.y, ba.x);

double len = sqrt(hd.x * hd.x + hd.y * hd.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;

};

template<class ELE, class ResultType, ELE minEle, ELE maxEle>

class CLowUperr

{

public:

CLowUperr(int iResutlCount)

{

m_iResutlCount = iResutlCount;

m_vPre.assign(4, vector(iResutlCount));

}

void Init(const ELE* pLower, const ELE* pHigh, int iNum)

{

if (iNum <= 0)

{

return;

}

InitPre(pLower, pHigh);

iNum–;

while (iNum–)

{

pLower++;

pHigh++;

vector<vector> dp(4, vector(m_iResutlCount));

OnInitDP(dp);

//处理非边界

for (auto tmp = minEle; tmp <= maxEle; tmp++)

{

OnDo(dp[0], m_vPre[0], tmp);

}

//处理下边界

OnDo(dp[1], m_vPre[1], *pLower);

for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)

{

OnDo(dp[0], m_vPre[1], tmp );

}

//处理上边界

OnDo(dp[2], m_vPre[2], *pHigh );

for (auto tmp = minEle; tmp < *pHigh; tmp++)

{

OnDo(dp[0], m_vPre[2], tmp );

}

//处理上下边界

if (*pLower == *pHigh)

{

OnDo(dp[3], m_vPre[3], *pLower);

}

else

{

OnDo(dp[1], m_vPre[3], *pLower );

for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)

{

OnDo(dp[0], m_vPre[3], tmp );

}

OnDo(dp[2], m_vPre[3], *pHigh );

}

m_vPre.swap(dp);

}

ResultType Total(int iMinIndex, int iMaxIndex)

{

ResultType ret;

for (int status = 0; status < 4; status++)

{

for (int index = iMinIndex; index <= iMaxIndex; index++)

{

ret += m_vPre[status][index];

}

return ret;

}

protected:

int m_iResutlCount;
void InitPre(const ELE* const pLower, const ELE* const pHigh)
{
  for (ELE cur = *pLower; cur <= *pHigh; cur++)
  {
    int iStatus = 0;
    if (*pLower == cur)
    {
      iStatus = *pLower == *pHigh ? 3 : 1;
    }
    else if (*pHigh == cur)
    {
      iStatus = 2;
    }
    OnInitFirstEle(m_vPre[iStatus], cur);
  }
}
virtual void OnDo(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE cur) = 0;
virtual void OnInitFirstEle(vector<ResultType>& vPre,const ELE curValue)
{
  int curIndex = curValue - minEle;
  if (curIndex < m_iResutlCount)
  {
    vPre[curIndex] = 1;
  }
}
virtual void OnInitDP(vector<vector<ResultType>>& dp)
{
}
vector<vector<ResultType>> m_vPre;

};

//马拉车计算回文回文

class CPalindrome

{

public:

//vOddHalfLen[i]表示以s[i]为中心，且长度为奇数的最长回文的半长，包括s[i]

//比如：“aba” vOddHalfLen[1]为2 “abba” vEvenHalfLen[1]为2

static void CalHalfLen(vector& vOddHalfLen, vector& vEvenHalfLen, const string& s)

{

vector v;

for (const auto& ch : s)

{

v.emplace_back(ch);

v.emplace_back(‘*’);

}

v.pop_back();

const int len = v.size();
  vector<int> vHalfLen(len);
  int center = -1, r = -1;
  //center是对称中心,r是其右边界（闭）
  for (int i = 0; i < len; i++)
  {
    int tmp = 1;
    if (i <= r)
    {
      int pre = center - (i - center);
      tmp = min(vHalfLen[pre], r - i + 1);
    }
    for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);
    vHalfLen[i] = --tmp;
    const int iNewR = i + tmp - 1;
    if (iNewR > r)
    {
      r = iNewR;
      center = i;
    }
  }
  vOddHalfLen.resize(s.length());
  vEvenHalfLen.resize(s.length());
  for (int i = 0; i < len; i++)
  {
    if (i & 1)
    {
      vEvenHalfLen[i / 2] = vHalfLen[i] / 2;
    }
    else
    {
      vOddHalfLen[i / 2] = (vHalfLen[i] + 1) / 2;
    }
  }
}
//vOddLen[i]表示以i开始，奇数长度 最长回文
//vEvenLen[i]表示以i开始，偶数长度 最长回文
static void  CalLen(vector<int>& vOddLen, vector<int>& vEvenLen, const string& s)
{
  vector<char> v;
  for (const auto& ch : s)
  {
    v.emplace_back(ch);
    v.emplace_back('*');
  }
  v.pop_back();
  const int len = v.size();
  vector<int> vHalfLen(len);
  int center = -1, r = -1;
  //center是对称中心,r是其右边界（闭）
  for (int i = 0; i < len; i++)
  {
    int tmp = 1;
    if (i <= r)
    {
      int pre = center - (i - center);
      tmp = min(vHalfLen[pre], r - i + 1);
    }
    for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);
    vHalfLen[i] = --tmp;
    const int iNewR = i + tmp - 1;
    if (iNewR > r)
    {
      r = iNewR;
      center = i;
    }
  }
  vOddLen.resize(s.length());
  vEvenLen.resize(s.length());
  for (int i = 0; i < len; i++)
  {
    const int iHalfLen = (i & 1) ? (vHalfLen[i] / 2) : ((vHalfLen[i] + 1) / 2);
    const int left = i / 2 - iHalfLen + 1;
    if (i & 1)
    {
      vEvenLen[left] = vHalfLen[i] / 2*2;
    }
    else
    {
      vOddLen[left] = (vHalfLen[i] + 1) / 2*2-1;
    }
  }
}

};

//使用实例

//vector vOddHalfLen, vEvenHalfLen;

//CPalindrome::Do(vOddHalfLen, vEvenHalfLen, s);

class CKMP

{

public:

static vector Next(const string& s)

{

const int len = s.length();

vector vNext(len, -1);

for (int i = 1; i < len; i++)

{

int next = vNext[i - 1];

while ((-1 != next) && (s[next + 1] != s[i]))

{

next = vNext[next];

}

vNext[i] = next + (s[next + 1] == s[i]);

}

return vNext;

}

};

template

class CMergeSortIndex

{

public:

CMergeSortIndex(const vector& nums) :m_nums(nums)

{

m_c = nums.size();

m_vIndexs.resize(nums.size());

iota(m_vIndexs.begin(), m_vIndexs.end(), 0);

}

void SortIndex(int left, int right)

{

if (right - left <= 1)

{

return;

}

const int mid = left + (right - left) / 2;

SortIndex(left, mid);

SortIndex(mid, right);

OnSortLeftRightEnd(left, mid, right);

//nums的[left,mid) 和[mid,right)分别排序

m_vSortIndexs.clear();

int i1 = left, i2 = mid;

while ((i1 < mid) && (i2 < right))

{

if (m_nums[m_vIndexs[i1]] > m_nums[m_vIndexs[i2]])

{

m_vSortIndexs.emplace_back(m_vIndexs[i2++]);

}

else

{

m_vSortIndexs.emplace_back(m_vIndexs[i1]);

OnAdd1(i1++, i2, left, mid, right);

}

while (i1 < mid)

{

m_vSortIndexs.emplace_back(m_vIndexs[i1]);

OnAdd1(i1++, i2, left, mid, right);

}

while (i2 < right)

{

m_vSortIndexs.emplace_back(m_vIndexs[i2++]);

}

for (int i = 0; i < m_vSortIndexs.size(); i++)

{

m_vIndexs[i + left] = m_vSortIndexs[i];

}

vector Sort()

{

SortIndex(0, m_c);

vector vRet(m_c);

for (int i = 0; i < m_c; i++)

{

vRet[i] = m_nums[m_vIndexs[i]];

}

return vRet;

}

protected:

virtual void OnSortLeftRightEnd(int left, int mid, int right)

{

}
virtual void OnAdd1(int i1, int i2, int left, int mid, int right)
{
}
int m_c;
const vector<T>& m_nums;
vector<int> m_vIndexs;
vector<int> m_vSortIndexs;

};

template<class T = int, class _Pr = std::less >

class CTopK

{

public:

CTopK(int k) :m_iMinNum(k)

{

}
void Do(vector<T>& m_v, T* begin, int num)
{
  for (; num; begin++, num--)
  {
    while (m_v.size() && _Pr()(*begin, m_v.back()) && (m_iMinNum - m_v.size() + 1 <= num))
    {
      m_v.pop_back();
    }
    if (m_v.size() < m_iMinNum)
    {
      m_v.push_back(*begin);
    }
  }
}

protected:

const int m_iMinNum;

};

class CUnionFindDirect

{

public:

CUnionFindDirect(int iSize)

{

m_vRoot.resize(iSize);

iota(m_vRoot.begin(), m_vRoot.end(), 0);

}

void Connect(bool& bConflic, bool& bCyc, int iFrom, int iTo)

{

bConflic = bCyc = false;

if (iFrom != m_vRoot[iFrom])

{

bConflic = true;

}

Fresh(iTo);
  if (m_vRoot[iTo] == iFrom)
  {
    bCyc = true;
  }
  if (bConflic || bCyc)
  {
    return;
  }
  m_vRoot[iFrom] = m_vRoot[iTo];
}

private:

int Fresh(int iNode)

{

if (m_vRoot[iNode] == iNode)

{

return iNode;

}

return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);

}

vector m_vRoot;

};

#define MACRO_BEGIN_END(n) n.begin(),n.end()

#define MacroTopSort(que,vNeiBo)

while (que.size())

{

const int cur = que.front();

que.pop();

for (const auto& next : vNeiBo[cur])

{

vDeg[next]–;

if (1 == vDeg[next])

{

}

#define Macro2DBFS(queRowCol,m_r,m_c)

queue<pair<int, int>> queRowCol;

vector<vector> vDis(m_r, vector(m_c, -1));

while (queRowCol.size())

{

const auto [r, c] = queRowCol.front();

queRowCol.pop();

auto Move = [&vDis, &queRowCol, this](int r, int c, int iDis)

{

if ((r < 0) || (r >= m_r))

{

return;

}

if ((c < 0) || (c >= m_c))

{

return;

}

if (-1 != vDis[r][c])

{

return;

}

vDis[r][c] = iDis;

queRowCol.emplace(r, c);

};

const int iDis = vDis[r][c] + 1;

Move(r + 1, c, iDis);

Move(r - 1, c, iDis);

Move(r, c + 1, iDis);

Move(r, c - 1, iDis);

}

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<TreeNode*> 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 CGoodString : public CLowUperr<char, C1097Int<>, ‘a’, ‘z’>

{

public:

CGoodString(string evil):CLowUperr<char, C1097Int<>, ‘a’, ‘z’>(evil.size())

{

m_c = evil.size();

m_strEvil = evil;

m_vMaxLen.assign(m_c, 0);

for (int i = 1; i < m_c; i++)

{

int iPreSameLen = m_vMaxLen[i-1];

while (evil[iPreSameLen] != evil[i])

{

if (0 == iPreSameLen)

{

break;

}

iPreSameLen = m_vMaxLen[iPreSameLen-1];

}

m_vMaxLen[i] = iPreSameLen+(evil[iPreSameLen] == evil[i]);

}

protected:

void OnDo(vector<C1097Int<>>& dp, const vector<C1097Int<>>& vPre, char cur)override

{

for (int i = 0; i < m_c; i++)

{

if (0 == vPre[i].ToInt())

{

continue;

}

int preSameLen = i;

while (m_strEvil[preSameLen] != cur)

{

if (0 == preSameLen)

{

break;

}

preSameLen = m_vMaxLen[preSameLen - 1];

}

const int curSameLen = preSameLen + (m_strEvil[preSameLen] == cur);

if (curSameLen == m_c)

{

continue;

}

dp[curSameLen] += vPre[i];

}

void OnInitFirstEle(vector<C1097Int<>>& vPre, const char curValue)override

{

int iSameLen = m_strEvil[0] == curValue;

if (iSameLen < m_c)

{

vPre[iSameLen] += 1;

}

string m_strEvil;

vector m_vMaxLen;//m_vNext[i] 记录 evil[0]到evil[i] 的最长公共前后缀

int m_c;

};

class Solution {

public:

int findGoodStrings(int n, string s1, string s2, string evil) {

CGoodString gs(evil);

gs.Init(s1.data(), s2.data(), s1.length());

return gs.Total(0, evil.size() - 1).ToInt();

}

int m_c;

};

【数位dp】【动态规划】【KMP】1397. 找到所有好字符串

作者推荐

本文涉及知识点

LeetCode1397. 找到所有好字符串

动态规划

代码

核心代码

测试用例

2023年1月15

2023年1月第二版

2023年9月

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数位dp】【动态规划】【KMP】1397. 找到所有好字符串

作者推荐

本文涉及知识点

LeetCode1397. 找到所有好字符串

动态规划

代码

核心代码

测试用例

2023年1月15

2023年1月 第二版

2023年9月

热门文章

最新文章

相关电子书

2023年1月第二版