【二分查找】【键值皆有序】1840最高建筑高度

template<class _Kty, class _Ty, bool bValueAsc, bool bOutSmallKey>
class COrderValueMap
{
public:
  void Add(_Kty key, _Ty value)
  {
    if (bOutSmallKey)
    {
      if (bValueAsc)
      {
        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 (bValueAsc)
      {
        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);
      }
      else
      {
        break;
      }
    }
    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;
  };
};
template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  int maxBuilding(int n, vector<vector<int>>& restrictions) {
    multimap<int, int> mMaxHeightToIndex;
    for (const auto& v : restrictions)
    {
      mMaxHeightToIndex.emplace(v[1], v[0]);
    }
    mMaxHeightToIndex.emplace(0, 1);
    mMaxHeightToIndex.emplace(1000'000'000, n);
    COrderValueMap<int,int,false,false> mLeft;
    COrderValueMap<int, int, true, true> mRight;
    map<int, int> mHeight;
    int iRet = 0;
    for (const auto [maxHeight, index] : mMaxHeightToIndex)
    {
      mHeight[index] = maxHeight;
      auto it1 = mLeft.m_map.lower_bound(index);
      if (mLeft.m_map.begin() != it1)
      {
        MinSelf(&mHeight[index], (--it1)->second + (index - 1));
      }
      auto it2 = mRight.m_map.lower_bound(index);
      if (mRight.m_map.end() != it2)
      {
        MinSelf(&mHeight[index], it2->second + (n - index ));
      }
      MaxSelf(&iRet, mHeight[index]);
      mLeft.Add(index, mHeight[index] - (index - 1));
      mRight.Add(index, mHeight[index] - (n - index));
    }
    for (auto it = mHeight.begin(); it != mHeight.end(); ++it )
    {
      auto itNext = std::next(it);
      if (mHeight.end() == itNext)
      {
        continue;
      }
      int iMidCnt = itNext->first - it->first  - 1;
      const int iMin = min(it->second, itNext->second);
      const int iMax = max(it->second, itNext->second);
      const int iAdd = (iMidCnt - (iMax - iMin) + 1) / 2;
      MaxSelf(&iRet, iMax + iAdd);
    }
    return iRet;
  }
};

template<class T,class T2>
void Assert(const T& t1, const T2& 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;
  vector<vector<int>> restrictions;
  {
    Solution sln;
    n = 5, restrictions = { {2,1},{4,1} };
    auto res = sln.maxBuilding(n, restrictions);
    Assert(2, res);
  }
  {
    Solution sln;
    n = 6, restrictions = {};
    auto res = sln.maxBuilding(n, restrictions);
    Assert(5, res);
  }
  {
    Solution sln;
    n = 10, restrictions = { {5,3},{2,5},{7,4},{10,3} };
    auto res = sln.maxBuilding(n, restrictions);
    Assert(5, res);
  }
}