#line 1 "test/verify/yosupo-area-of-union-of-rectangles.test.cpp" // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/area_of_union_of_rectangles #line 1 "template/template.hpp" #include #if __has_include() #include #endif using namespace std; using int64 = long long; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template istream &operator>>(istream &is, vector &v) { for (T &in : v) is >> in; return is; } template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, Ts... ts) { return vector(ts...))>(a, make_v(ts...)); } template typename enable_if::value == 0>::type fill_v(T &t, const V &v) { t = v; } template typename enable_if::value != 0>::type fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); } template struct FixPoint : F { explicit FixPoint(F &&f) : F(std::forward(f)) {} template decltype(auto) operator()(Args &&...args) const { return F::operator()(*this, std::forward(args)...); } }; template inline decltype(auto) MFP(F &&f) { return FixPoint{std::forward(f)}; } #line 4 "test/verify/yosupo-area-of-union-of-rectangles.test.cpp" template< typename ActedMonoid > struct LazySegmentTree { using S = typename ActedMonoid::S; using F = typename ActedMonoid::F; private: ActedMonoid m; int n{}, sz{}, height{}; vector< S > data; vector< F > lazy; inline void update(int k) { data[k] = m.op(data[2 * k + 0], data[2 * k + 1]); } inline void all_apply(int k, const F &x) { data[k] = m.mapping(data[k], x); if (k < sz) lazy[k] = m.composition(lazy[k], x); } inline void propagate(int k) { if (lazy[k] != m.id()) { all_apply(2 * k + 0, lazy[k]); all_apply(2 * k + 1, lazy[k]); lazy[k] = m.id(); } } public: LazySegmentTree() = default; explicit LazySegmentTree(ActedMonoid m, int n): m(m), n(n) { sz = 1; height = 0; while (sz < n) sz <<= 1, height++; data.assign(2 * sz, m.e()); lazy.assign(2 * sz, m.id()); } explicit LazySegmentTree(ActedMonoid m, const vector< S > &v) : LazySegmentTree(m, v.size()) { build(v); } void build(const vector< S > &v) { assert(n == (int) v.size()); for (int k = 0; k < n; k++) data[k + sz] = v[k]; for (int k = sz - 1; k > 0; k--) update(k); } void set(int k, const S &x) { k += sz; for (int i = height; i > 0; i--) propagate(k >> i); data[k] = x; for (int i = 1; i <= height; i++) update(k >> i); } S get(int k) { k += sz; for (int i = height; i > 0; i--) propagate(k >> i); return data[k]; } S operator[](int k) { return get(k); } S prod(int l, int r) { if (l >= r) return m.e(); l += sz; r += sz; for (int i = height; i > 0; i--) { if (((l >> i) << i) != l) propagate(l >> i); if (((r >> i) << i) != r) propagate((r - 1) >> i); } S L = m.e(), R = m.e(); for (; l < r; l >>= 1, r >>= 1) { if (l & 1) L = m.op(L, data[l++]); if (r & 1) R = m.op(data[--r], R); } return m.op(L, R); } S all_prod() const { return data[1]; } void apply(int k, const F &f) { k += sz; for (int i = height; i > 0; i--) propagate(k >> i); data[k] = m.mapping(data[k], f); for (int i = 1; i <= height; i++) update(k >> i); } void apply(int l, int r, const F &f) { if (l >= r) return; l += sz; r += sz; for (int i = height; i > 0; i--) { if (((l >> i) << i) != l) propagate(l >> i); if (((r >> i) << i) != r) propagate((r - 1) >> i); } { int l2 = l, r2 = r; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); } l = l2, r = r2; } for (int i = 1; i <= height; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template< typename C > int find_first(int l, const C &check) { if (l >= n) return n; l += sz; for (int i = height; i > 0; i--) propagate(l >> i); S sum = m.e(); do { while ((l & 1) == 0) l >>= 1; if (check(m.op(sum, data[l]))) { while (l < sz) { propagate(l); l <<= 1; auto nxt = m.op(sum, data[l]); if (not check(nxt)) { sum = nxt; l++; } } return l + 1 - sz; } sum = m.op(sum, data[l++]); } while ((l & -l) != l); return n; } template< typename C > int find_last(int r, const C &check) { if (r <= 0) return -1; r += sz; for (int i = height; i > 0; i--) propagate((r - 1) >> i); S sum = m.e(); do { r--; while (r > 1 and (r & 1)) r >>= 1; if (check(m.op(data[r], sum))) { while (r < sz) { propagate(r); r = (r << 1) + 1; auto nxt = m.op(data[r], sum); if (not check(nxt)) { sum = nxt; r--; } } return r - sz; } sum = m.op(data[r], sum); } while ((r & -r) != r); return -1; } }; template< typename S2, typename Op, typename E, typename F2, typename Mapping, typename Composition, typename Id > struct LambdaActedMonoid { using S = S2; using F = F2; S op(const S &a, const S &b) const { return _op(a, b); } S e() const { return _e(); } S mapping(const S &x, const F &f) const { return _mapping(x, f); } F composition(const F &f, const F &g) const { return _composition(f, g); } F id() const { return _id(); } LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition, Id _id): _op(_op), _e(_e), _mapping(_mapping), _composition(_composition), _id(_id) {} private: Op _op; E _e; Mapping _mapping; Composition _composition; Id _id; }; template< typename Op, typename E, typename Mapping, typename Composition, typename Id > LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition, Id _id) -> LambdaActedMonoid< decltype(_e()), Op, E, decltype(_id()), Mapping, Composition, Id >; /* struct ActedMonoid { using S = ?; using F = ?; static constexpr S op(const S& a, const S& b) {} static constexpr S e() {} static constexpr F mapping(const S &x, const F &f) {} static constexpr F composition(const F &f, const F &g) {} static constexpr F id() const {} }; */ struct PermutationTree { public: enum NodeType { JOIN_ASC, JOIN_DESC, LEAF, CUT }; struct Node { NodeType type; int l, r; // [l, r) int min_v, max_v; // [min_v, max_v) vector ch; size_t size() const { return r - l; } bool is_join() const { return type == JOIN_ASC or type == JOIN_DESC; }; bool is_leaf() const { return type == LEAF; } bool is_cut() const { return type == CUT; } }; using NP = Node *; PermutationTree() = default; private: static void add_child(NP t, NP c) { t->ch.emplace_back(c); t->l = min(t->l, c->l); t->r = max(t->r, c->r); t->min_v = min(t->min_v, c->min_v); t->max_v = max(t->max_v, c->max_v); } public: static NP build(vector &A) { int n = (int)A.size(); vector desc{-1}; vector asc{-1}; vector st; constexpr int lim = (1 << 30) - 1; auto f = [](int a, int b) { return min(a, b); }; auto e = [&]() { return lim; }; auto g = [](int a, int b) { return a + b; }; auto id = []() { return 0; }; LazySegmentTree seg(LambdaActedMonoid(f, e, g, g, id), vector(n)); for (int i = 0; i < n; i++) { while (~desc.back() and A[i] > A[desc.back()]) { seg.apply(desc[desc.size() - 2] + 1, desc.back() + 1, A[i] - A[desc.back()]); desc.pop_back(); } while (~asc.back() and A[i] < A[asc.back()]) { seg.apply(asc[asc.size() - 2] + 1, asc.back() + 1, A[asc.back()] - A[i]); asc.pop_back(); } desc.emplace_back(i); asc.emplace_back(i); NP t = new Node{LEAF, i, i + 1, A[i], A[i] + 1, {}}; for (;;) { NodeType type = CUT; if (not st.empty()) { if (st.back()->max_v == t->min_v) { type = JOIN_ASC; } else if (t->max_v == st.back()->min_v) { type = JOIN_DESC; } } if (type != CUT) { NP r = st.back(); if (type != r->type) { r = new Node{type, r->l, r->r, r->min_v, r->max_v, {r}}; } add_child(r, t); st.pop_back(); t = r; } else if (seg.prod(0, i + 1 - (int)t->size()) == 0) { t = new Node{CUT, t->l, t->r, t->min_v, t->max_v, {t}}; do { add_child(t, st.back()); st.pop_back(); } while (t->max_v - t->min_v != t->size()); reverse(begin(t->ch), end(t->ch)); } else { break; } } st.emplace_back(t); seg.apply(0, i + 1, -1); } return st[0]; } }; template struct MontgomeryModInt { private: using mint = MontgomeryModInt; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod_; for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod_) % mod_; static_assert(r * mod_ == 1, "invalid, r * mod != 1"); static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0"); u32 x; public: MontgomeryModInt() : x{} {} MontgomeryModInt(const i64 &a) : x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {} static constexpr u32 reduce(const u64 &b) { return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32); } mint &operator+=(const mint &p) { if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod(); return *this; } mint &operator-=(const mint &p) { if (i32(x -= p.x) < 0) x += 2 * mod(); return *this; } mint &operator*=(const mint &p) { x = reduce(u64(x) * p.x); return *this; } mint &operator/=(const mint &p) { *this *= p.inv(); return *this; } mint operator-() const { return mint() - *this; } mint operator+(const mint &p) const { return mint(*this) += p; } mint operator-(const mint &p) const { return mint(*this) -= p; } mint operator*(const mint &p) const { return mint(*this) *= p; } mint operator/(const mint &p) const { return mint(*this) /= p; } bool operator==(const mint &p) const { return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x); } bool operator!=(const mint &p) const { return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x); } u32 val() const { u32 ret = reduce(x); return ret >= mod() ? ret - mod() : ret; } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } mint inv() const { return pow(mod() - 2); } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.val(); } friend istream &operator>>(istream &is, mint &a) { i64 t; is >> t; a = mint(t); return is; } static constexpr u32 mod() { return mod_; } }; template using modint = MontgomeryModInt; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; using mint = modint998244353; int main() { int N, K; cin >> N >> K; vector< int > A(N); cin >> A; for(auto &a: A) --a; using NP = PermutationTree::Node *; auto dp = make_v< mint >(K + 1, N + 1); dp[0][0] = 1; MFP([&](auto rec, NP r) -> void { if(r->is_cut() or r->is_leaf()) { for(int k = 0; k < K; k++) { dp[k + 1][r->r] += dp[k][r->l]; } } vector< mint > sum(K); for(auto &c: r->ch) { rec(c); if(r->is_join()) { for(int k = 0; k < K; k++) { dp[k + 1][c->r] += sum[k]; sum[k] += dp[k][c->l]; } } } })(PermutationTree::build(A)); for(int i = 1; i <= K; i++) { cout << dp[i][N] << "\n"; } }