map|二分查找|离线查询|LeetCode:2736最大和查询

template<class _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey> 
class COrderValueMap 
{
public:
  void Add (_Kty key, _Ty value)
  {
    if (bOutSmallKey)
    {
      if (bValueDdes)
      {
        AddOutSmall(key, value, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
      }
      else
      {
        AddOutSmall(key, value, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
      }
    }
    else 
    {
      if (bValueDdes)
      {
        AddNotOutSmall(key, value, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
      }
      else
      {
        AddNotOutSmall(key, value, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
      }
    }
  };
  std::map<_Kty, _Ty> m_map;
protected:
  template<class _Pr1, class _Pr2>
  void AddOutSmall(_Kty key, _Ty value, _Pr1 pr1, _Pr2 pr2)
  {
    auto it = m_map.lower_bound(key);
    if ((m_map.end() != it) && pr1(it->second, value))
    {
      return;//被旧值淘汰
    }
    auto ij = it;
    while (it != m_map.begin())
    {
      --it;
      if (pr2(it->second, value))
      {
        it = m_map.erase(it);
      }
    }
    m_map[key] = value;
  }
  template<class _Pr1, class _Pr2>
  void AddNotOutSmall(_Kty key, _Ty value, _Pr1 pr1,_Pr2 pr2 )
  {
    auto it = m_map.upper_bound(key);
    if ((m_map.begin() != it) && pr1(std::prev(it)->second, value))
    {
      return;//被淘汰
    }
    auto ij = it;
    for (; (m_map.end() != ij) && pr2(ij->second, value); ++ij);
    m_map.erase(it, ij);
    m_map[key] = value;
  };
};

class Solution {
public:
  vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
    vector<int> indexs(queries.size());
    iota(indexs.begin(), indexs.end(), 0);
    sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return queries[i1][0] > queries[i2][0]; });
    priority_queue<pair<int, int>> maxHeap;
    for (int i = 0; i < nums1.size(); i++)
    {
      maxHeap.emplace(nums1[i], nums2[i]);
    }
    COrderValueMap<int, int, false, true> ySum;
    vector<int> vRet(queries.size(), -1);
    for (const auto i : indexs)
    {
      while (maxHeap.size() && (maxHeap.top().first >= queries[i][0]))
      {
        ySum.Add(maxHeap.top().second, maxHeap.top().first + maxHeap.top().second);
        maxHeap.pop();
      }
      auto it = ySum.m_map.lower_bound(queries[i][1]);
      if (ySum.m_map.end() != it)
      {
        vRet[i] = it->second;
      }
    }
    return vRet;
  }
};

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]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<int> nums1, nums2;
  vector<vector<int>> queries;
  {
    Solution slu;   
    nums1 = { 4,3,1,2 }, nums2 = { 2,4,9,5 }, queries = { {4,1},{1,3},{2,5} };
    auto res = slu.maximumSumQueries(nums1,nums2,queries);
    Assert(vector<int>{6, 10, 7}, res);
  }
  {
    Solution slu;
    nums1 = { 3,2,5 }, nums2 = { 2,3,4 }, queries = { {4,4},{3,2},{1,1} };
    auto res = slu.maximumSumQueries(nums1, nums2, queries);
    Assert(vector<int>{9, 9, 9}, res);
  }
  {
    Solution slu;
    nums1 = { 2,1 }, nums2 = { 2,3 }, queries = { {3,3} };
    auto res = slu.maximumSumQueries(nums1, nums2, queries);
    Assert(vector<int>{-1}, res);
  }
}