#include <iostream>
#include <vector>
#include <algorithm> // std::max()
using Type = int;
Type Op(Type l, Type r) // std::min または std::max
{
return std::max(l, r);
}
Type E() // モノイドの単位元
{
return 0;
}
// 遅延伝播セグメント木 (RMQ & RUQ)
class LazySegTree
{
public:
LazySegTree() = default;
// ツリーの初期化
explicit LazySegTree(size_t size)
{
// size 以上である 2 のべき乗数を求めて m_size に代入する
while (m_size < size)
{
m_size *= 2;
}
m_nodes.resize((m_size * 2 - 1), E());
m_lazyNodes.resize((m_size * 2 - 1), E());
}
// ツリーの初期化
explicit LazySegTree(const std::vector<Type>& values)
: LazySegTree(values.size())
{
for (size_t i = 0; i < values.size(); ++i)
{
m_nodes[m_size - 1 + i] = values[i];
}
for (int i = static_cast<int>(m_size) - 2; i >= 0; --i)
{
update(i);
}
}
// クエリ対象区間 [begin, end) を value に更新する
void update(size_t begin, size_t end, Type value)
{
// update(クエリ対象区間, value, 0, 全区間);
update(begin, end, value, 0, 0, m_size);
}
// 区間クエリ（対象区間 [begin, end) におけるクエリ結果を求める）
Type query(size_t begin, size_t end)
{
// rangeMax(クエリ対象区間, 0, 全区間);
return query(begin, end, 0, 0, m_size);
}
private:
void update(size_t ni)
{
m_nodes[ni] = Op(m_nodes[ni * 2 + 1], m_nodes[ni * 2 + 2]);
}
// 更新
void update(size_t begin, size_t end, Type value, size_t ni, size_t nBegin, size_t nEnd)
{
propagate(ni);
// クエリ対象区間が管理区間と無関係なら
if ((nEnd <= begin) || (end <= nBegin))
{
return; // 何もしない
}
// 管理区間のすべてがクエリ対象区間に含まれていれば
if ((begin <= nBegin) && (nEnd <= end))
{
// 現在のノードの遅延評価の値に value をセット
m_lazyNodes[ni] = value;
propagate(ni);
return;
}
// update(クエリ対象区間, value, 子ノード(左) のインデックス, 子ノード(左) の管理区間)
update(begin, end, value, (ni * 2 + 1), nBegin, (nBegin + nEnd) / 2);
// update(クエリ対象区間, value, 子ノード(右) のインデックス, 子ノード(右) の管理区間)
update(begin, end, value, (ni * 2 + 2), (nBegin + nEnd) / 2, nEnd);
// 現在のノードの計算済みの値を、子ノード (左, 右) の計算済みの値をもとに更新
m_nodes[ni] = Op(m_nodes[ni * 2 + 1], m_nodes[ni * 2 + 2]);
}
// クエリ対象区間 [begin, end) におけるクエリ結果を求める.
// ni: 確認するノードのインデックス. そのノードの管理区間は [nBegin, nEnd)
Type query(size_t begin, size_t end, size_t ni, size_t nBegin, size_t nEnd)
{
// クエリ対象区間が管理区間と無関係なら
if ((nEnd <= begin) || (end <= nBegin))
{
return E(); // 空の値を返す
}
propagate(ni);
// 管理区間のすべてがクエリ対象区間に含まれていれば
if ((begin <= nBegin) && (nEnd <= end))
{
return m_nodes[ni];
}
// query(クエリ対象区間, 子ノード(左) のインデックス, 子ノード(左) の管理区間)
const Type lc = query(begin, end, (ni * 2 + 1), nBegin, (nBegin + nEnd) / 2);
// query(クエリ対象区間, 子ノード(右) のインデックス, 子ノード(右) の管理区間)
const Type rc = query(begin, end, (ni * 2 + 2), (nBegin + nEnd) / 2, nEnd);
return Op(lc, rc);
}
// 伝播
void propagate(size_t ni)
{
// ノード ni が評価済みかチェックする
if (m_lazyNodes[ni] == E())
{
return; // 未評価なら何もしない
}
// 評価された場合、評価済みの値をノードに適用し、子ノードに伝播する
if ((ni * 2 + 1) < m_nodes.size())
{
m_lazyNodes[ni * 2 + 1] = m_lazyNodes[ni];
m_lazyNodes[ni * 2 + 2] = m_lazyNodes[ni];
}
m_nodes[ni] = m_lazyNodes[ni];
m_lazyNodes[ni] = E();
}
private:
// 葉の数
size_t m_size = 1;
// 計算済みの値の配列
std::vector<int> m_nodes;
// 遅延評価の値の配列
std::vector<int> m_lazyNodes;
};
int main()
{
// W 個の正方形のマス, N 個のレンガ
int W, N;
std::cin >> W >> N;
LazySegTree st(W);
// それぞれのレンガについて
for (int i = 0; i < N; ++i)
{
// 左から L 番目 ～ R 番目を覆う
int L, R;
std::cin >> L >> R;
// 区間を [L, R) で表現する
// 1 番目 ～ 3 番目の場合 [0, 3)
--L;
// クエリ対象区間の現在の高さ
const int oldH = st.query(L, R);
// クエリ対象区間の新しい高さ (+1)
const int newH = (oldH + 1);
// クエリ対象区間の高さを更新する
st.update(L, R, newH);
// 高さを出力
std::cout << newH << '\n';
}
}自作の遅延伝播セグメント木ではなく、AC Library に実装されている遅延伝播セグメント木 atcoder::lazysegtree を使った解法です。
#include <iostream>
#include <algorithm> // std::max()
#include <atcoder/lazysegtree.hpp> // atcoder::lazy_segtree
int Op(int a, int b)
{
return std::max(a, b);
}
int E()
{
return 0;
}
int Mapping(int f, int x)
{
return (f == 0 ? x : f);
}
int Composition(int f, int g)
{
return (f == 0 ? g : f);
}
int Id()
{
return 0;
}
int main()
{
// W 個の正方形のマス, N 個のレンガ
int W, N;
std::cin >> W >> N;
// 遅延評価セグメント木
atcoder::lazy_segtree<int, Op, E, int, Mapping, Composition, Id> segTree{ W };
// それぞれのレンガについて
for (int i = 0; i < N; ++i)
{
// 左から L 番目 ～ R 番目を覆う
int L, R;
std::cin >> L >> R;
// 区間をを [L, R) で表現する
// 1 番目 ～ 3 番目の場合 [0, 3)
--L;
// クエリ対象区間の現在の高さ
const int oldH = segTree.prod(L, R);
// クエリ対象区間の新しい高さ (+1)
const int newH = (oldH + 1);
// クエリ対象区間の高さを更新する
segTree.apply(L, R, newH);
// 高さを出力
std::cout << newH << '\n';
}
}座標圧縮による解法で、小課題 1, 2 を解けます。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort(), std::unique(), std::lower_bound(), std::max_element()
#include <iterator> // std::distance()
int main()
{
// W 個の正方形のマス, N 個のレンガ
int W, N;
std::cin >> W >> N;
// レンガの開始座標を記録する配列
std::vector<int> Ls(N);
// レンガの終端座標を記録する配列
std::vector<int> Rs(N);
// それぞれのレンガについて
for (int i = 0; i < N; ++i)
{
// 左から L 番目 ～ R 番目を覆う
int L, R;
std::cin >> L >> R;
// 区間を記録する
// 1 番目 ～ 3 番目の場合 [0, 3)
Ls[i] = (L - 1);
Rs[i] = R;
}
////////////////////////////////
//
// 座標圧縮
//
// 登場する座標を記録, ソート, 重複排除する
std::vector<int> coordinates;
for (int i = 0; i < N; ++i)
{
coordinates.push_back(Ls[i]);
coordinates.push_back(Rs[i]);
}
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()), coordinates.end());
for (int i = 0; i < N; ++i)
{
// 元の座標をマッピング後のインデックスに置き換える
Ls[i] = static_cast<int>(std::distance(coordinates.begin(), std::lower_bound(coordinates.begin(), coordinates.end(), Ls[i])));
Rs[i] = static_cast<int>(std::distance(coordinates.begin(), std::lower_bound(coordinates.begin(), coordinates.end(), Rs[i])));
}
//
////////////////////////////////
// 各区間の現在の高さ
// 区間数は (coordinates.size() - 1)
std::vector<int> h(coordinates.size() - 1);
for (int i = 0; i < N; ++i)
{
// レンガを積む区間 [itLeft, itRight)
const auto itLeft = (h.begin() + Ls[i]);
const auto itRight = (h.begin() + Rs[i]);
// クエリ対象区間の現在の高さ
const int oldH = *std::max_element(itLeft, itRight);
// クエリ対象区間の新しい高さ (+1)
const int newH = (oldH + 1);
// クエリ対象区間の高さを更新する
std::fill(itLeft, itRight, newH);
// 高さを出力
std::cout << newH << '\n';
}
}