class MajorityChecker {
 public:
 MajorityChecker(vector& arr) {
 m_arr = arr;
 m_c = arr.size();
 m_len = sqrt(m_c);
 const int iMax = *std::max_element(arr.begin(),arr.end());
 m_vValueIndexs.resize(iMax+1);
 for (int i = 0 ; i < m_c ;i++)
 {
 const auto& n = arr[i];
 m_vValueIndexs[n].emplace_back(i);
 } 
 for (int i = 0; i <= iMax; i++)
 {
 if (m_vValueIndexs[i].size() >= m_len)
 {
 m_vMoreValues.emplace_back(i);
 }
 } 
 }
 int query(int left, int right, int threshold) {
 if (threshold >= m_len)
 {
 for (const auto n : m_vMoreValues)
 {
 //[0,left)的数量
 auto it1 = std::lower_bound(m_vValueIndexs[n].begin(), m_vValueIndexs[n].end(), left);
 //[0,right+1)的数量
 auto it2 = std::lower_bound(m_vValueIndexs[n].begin(), m_vValueIndexs[n].end(), right+1);
 if (it2 - it1 >= threshold)
 {
 return n;
 }
 }
 return -1;
 }
 std::unordered_map<int, int> mValueNum;
 for (int i = left; i <= right; i++)
 {
 mValueNum[m_arr[i]]++;
 }
 for (const auto it : mValueNum)
 {
 if (it.second >= threshold)
 {
 return it.first;
 }
 }
 return -1;
 }
 vector m_arr;
 vector<vector> m_vValueIndexs;
 vector m_vMoreValues;
 int m_c;
 int m_len;
 };

template
 void Assert(const T& t1, const T& t2)
 {
 assert(t1 == t2);
 }template
 void Assert(const vector& v1, const vector& v2)
 {
 if (v1.size() != v2.size())
 {
 assert(false);
 return;
 }
 for (int i = 0; i < v1.size(); i++)
 {
 Assert(v1[i], v2[i]);
 }
 }int main()
 {
 vector nums = { 1, 1, 2, 2, 1, 1 };
 MajorityChecker majorityChecker(nums);
 int res = majorityChecker.query(0, 5, 4); // 返回 1
 assert(1 , res);
 majorityChecker.query(0, 3, 3); // 返回 -1
 assert(-1, res);
 majorityChecker.query(2, 3, 2); // 返回 2
 assert(2, res);//CConsole::Out(res);}

class MajorityChecker {
 public:
 MajorityChecker(vector& arr) :m_iNumRange(sqrt(arr.size()) * 2), m_c(arr.size()), m_arr(arr)
 {
 Init(arr);
 }
 void Init(const vector& arr)
 {
 std::unordered_map<int, int> mValueNums;
 for (const auto& a : arr)
 {
 mValueNums[a]++;
 }
 for (const auto& it : mValueNums)
 {
 if (it.second <= m_iNumRange)
 {
 continue;
 }
 m_vValues.emplace_back(it.first);
 m_vValueIndexs.emplace_back();
 m_vValueIndexs.back().emplace_back(0);
 for (int i = 0; i < m_c; i++)
 {
 int iSame = arr[i] == it.first;
 m_vValueIndexs.back().emplace_back(iSame + m_vValueIndexs.back().back());
 }
 }
 }
 int query(int left, int right, int threshold) {
 const int len = right - left + 1;
 //直接读取缓存
 if (threshold > m_iNumRange)
 {
 for (int i = 0; i < m_vValueIndexs.size(); i++)
 {
 const int iNum = m_vValueIndexs[i][right + 1] - m_vValueIndexs[i][left];
 if (iNum >= threshold)
 {
 return m_vValues[i];
 }
 }
 return -1;
 }
 //暴力遍历
 int iValue = -1, iNum = 0;
 for (int i = left; i <= right; i++)
 {
 if (m_arr[i] == iValue)
 {
 iNum++;
 }
 else
 {
 if (0 == iNum)
 {
 iValue = m_arr[i];
 iNum = 1;
 }
 else
 {
 iNum–;
 }
 }
 }
 iNum = 0;
 for (int i = left; i <= right; i++)
 {
 if (m_arr[i] == iValue)
 {
 iNum++;
 }
 }
 return (iNum >= threshold) ? iValue : -1;
 }
 //缓存各数值的前缀和
 std::vector m_vValues;//m_vValues[i]对应 m_vValueIndexs[i]的值
 vector<vector> m_vValueIndexs;
 vector m_arr;
 const int m_c;
 const int m_iNumRange = 1;//众数的数量小于等于m_iNumRange,直接遍历
 };