2D Decreasing Sequence
コードについての説明
ここで $2$ 次元単調減少列とは $\{ (x_1, y_1), (x_2, y_2), ... , (x_n, y_n) \}$ ($x_i < x_{i+1}$ かつ $y_i > y_{i+1}$)
というような $2$ 次元座標平面上の点の列を意味する.
本実装では $2$ 次元単調減少列 $S$ で $(x_k, y_k) \not \in S$ となるような点については矩形領域 $(-\inf, x_k) \times (-\inf, y_k)$ 内に $S$ 内の要素を少なくとも $１$ つ含むようなもの(下側階段)
を保持している.
(関数)
$insert(val)$ : 点 $val (\in \mathbb{R}^2)$ を追加する. 実際に下側階段に組み込まれたか(true / false)を返す.
時間計算量: insert ならし $\O (\log n)$
コード
template<typename T> class LIS2D
{
private:
using ptt = pair<T,T>;
set<ptt> st;
public:
//実際に追加されたかどうかを返す
bool insert(pair<T,T> val){
bool in = false;
auto it = st.lower_bound(val);
if(it != st.end()){
if(*it == val) return in;
in = (it->second >= val.second);
}
if(in){
while(it != st.end() && it->second >= val.second){
it = st.erase(it);
}
}else{
if(it != st.begin()){
it--;
in = (it->second > val.second);
}else{
in = true;
}
}
if(in) st.insert(val);
return in;
}
void print(){
for(auto& val : st){
cout << "{" << val.first << "," << val.second << "}" << " ";
}
cout << "\n";
}
};
verify 用の問題
AOJ : Railway Connection 提出コード(非想定解)