#line 1 "main.cpp" #include #include #line 2 "monoid-unionfind.hpp" /** * @file monoid-unionfind.hpp * @brief 可換モノイドを乗せるUnionFind */ #line 2 "unionfind.hpp" /** * @file unionfind.hpp * @brief UnionFind */ #include #include #include /** * @brief 無向グラフに対して「辺の追加」、「2頂点が連結かの判定」をする */ struct UnionFind { protected: int _n; // 負ならサイズ、非負なら親 std::vector parent_or_size; public: UnionFind() : _n(0) {} explicit UnionFind(int n) : _n(n), parent_or_size(n, -1) {} /** * @brief 辺(a,b)を足す * @return 連結したものの代表元 */ int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } /** * @brief 頂点a,bが連結かどうか */ bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } /** * @brief 頂点aの属する連結成分の代表元 */ int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; int x = a; while (parent_or_size[x] >= 0) { x = parent_or_size[x]; } while (parent_or_size[a] >= 0) { int t = parent_or_size[a]; parent_or_size[a] = x; a = t; } return x; } /** * @brief 頂点aの属する連結成分のサイズ */ int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } /** * @brief グラフを連結成分に分け、その情報を返す * @return 「一つの連結成分の頂点番号のリスト」のリスト */ std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } }; #line 9 "monoid-unionfind.hpp" /** * @brief 可換モノイドを乗せるUnionFind * * @tparam S * @tparam Op */ template class MonoidUnionFind : private UnionFind { private: std::vector val; using UnionFind::_n; using UnionFind::parent_or_size; public: inline constexpr static auto op = Op(); explicit MonoidUnionFind(std::vector v) : UnionFind(v.size()), val(v) {} MonoidUnionFind(int n, S e) : UnionFind(n), val(n, e) {} using UnionFind::groups; using UnionFind::leader; using UnionFind::same; using UnionFind::size; int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; val[x] = op(val[x], val[y]); return x; } const S& prod(int a) { return val[leader(a)]; } }; #line 2 "more_functional.hpp" /** * @file more_functional.hpp * @brief 関数オブジェクトを定義する */ #include #include #include #include namespace more_functional { template struct Max { const S operator()(const S& a, const S& b) const { return std::max(a, b); } }; template struct Min { const S operator()(const S& a, const S& b) const { return std::min(a, b); } }; template struct MinMax { const std::pair operator()(const std::pair& a, const std::pair& b) const { return {std::min(a.first, b.first), std::max(a.second, b.second)}; } }; template >* = nullptr> struct Gcd { constexpr S operator()(const S& a, const S& b) const { return std::gcd(a, b); } }; template struct Zero { S operator()() const { return S(0); } }; template struct One { S operator()() const { return S(1); } }; template struct None { S operator()() const { return S{}; } }; template >* = nullptr> struct MaxLimit { constexpr S operator()() const { return std::numeric_limits::max(); } }; template >* = nullptr> struct MinLimit { constexpr S operator()() const { return std::numeric_limits::lowest(); } }; template >* = nullptr> struct MaxMinLimit { constexpr std::pair operator()() const { return {std::numeric_limits::max(), std::numeric_limits::lowest()}; } }; template struct Div { S operator()(const S& a) const { return S(1) / a; } }; } // namespace more_functional #line 6 "main.cpp" using ll = long long; int main() { int D, Q; std::cin >> D >> Q; std::vector> AB(Q); std::set s; for (auto& [A, B] : AB) { std::cin >> A >> B; s.insert(A); s.insert(A - 1); s.insert(B); s.insert(B + 1); } std::vector v(s.begin(), s.end()); std::vector f(s.size()); std::vector> init; for (std::size_t i = 0; i < v.size(); i++) { init.push_back({i, i}); } MonoidUnionFind, more_functional::MinMax> uf(init); ll ans = 0; for (auto [A, B] : AB) { int k = std::lower_bound(v.begin(), v.end(), A) - v.begin(); std::pair p = uf.prod(k); while (v[p.second + 1] <= B) { uf.merge(k, p.second + 1); k = p.second + 1; p = uf.prod(k); } if (f[p.first - 1]) { uf.merge(p.first - 1, p.first); } if (f[p.second + 1]) { uf.merge(p.second, p.second + 1); } f[p.first] = true; f[p.second] = true; p = uf.prod(k); if (ans < v[p.second] - v[p.first] + 1) { ans = v[p.second] - v[p.first] + 1; } std::cout << ans << std::endl; } }