Submission #61745961

---

Source Code Expand

#include <cassert>
#include <algorithm>
#include <vector>

template<typename Idx, typename S, S (*op)(S, S), S (*e)(), typename F, S (*mapping)(F, S, Idx), F (*composition)(F, F), F (*id)()>
struct segtree_lazy_sparse {
  private:
    
    static constexpr S pow_monoid(S a, Idx k) {
        S b = e();
        while (k) {
            if (k & 1) b = op(b, a);
            a = op(a, a);
            k >>= 1;
        }
        return b;
    }

    struct node {
        int h;
        Idx lx, rx, Lx, Rx;
        node *l, *r;
        S val, sum, sum_subtree;
        F lz;
        node(Idx _lx, Idx _rx, S _val) : lx(_lx), rx(_rx), Lx(_lx), Rx(_rx), l(nullptr), r(nullptr), 
            val(_val), sum(pow_monoid(_val, rx - lx)), sum_subtree(sum), lz(id()) {}
        int factor() const { return (l ? l->h : 0) - (r ? r->h : 0); }
    };

    static void update(node *v) {
        v->h = 1;
        v->Lx = v->lx;
        v->Rx = v->rx;
        v->sum_subtree = v->sum;
        if (v->l) {
            v->h = v->l->h + 1;
            v->Lx = v->l->Lx;
            v->sum_subtree = op(v->l->sum_subtree, v->sum_subtree);
        }
        if (v->r) {
            v->h = std::max(v->h, v->r->h + 1);
            v->Rx = v->r->Rx;
            v->sum_subtree = op(v->sum_subtree, v->r->sum_subtree);
        }
    } 

    static void push_down(node *v) {
        if (v->lz != id()) {
            if (v->l) all_apply(v->l, v->lz);
            if (v->r) all_apply(v->r, v->lz);
            v->lz = id();
        }
    }

    static void all_apply(node *v, F lz) {
        v->lz = composition(lz, v->lz);
        v->val = mapping(lz, v->val, 1);
        v->sum = mapping(lz, v->sum, v->rx - v->lx);
        v->sum_subtree = mapping(lz, v->sum_subtree, v->Rx - v->Lx);
    }

    static node *rotate_right(node *v) {
        node *l = v->l;
        v->l = l->r;
        l->r = v;
        update(v);
        update(l);
        return l;
    }
    
    static node *rotate_left(node *v) {
        node *r = v->r;
        v->r = r->l;
        r->l = v;
        update(v);
        update(r);
        return r;
    }

    static node *balance(node *v) {
        int bf = v->factor();
        if (bf == 2) {
            if (v->l->factor() == -1) {
                v->l = rotate_left(v->l);
                update(v);
            }
            return rotate_right(v);
        } else if(bf == -2) {
            if (v->r->factor() == 1) {
                v->r = rotate_right(v->r);
                update(v);
            }
            return rotate_left(v);
        }
        return v;
    }

    static node *insert_leftmost(node *v, node *u) {
        if (!v) return u;
        push_down(v);
        v->l = insert_leftmost(v->l, u);
        update(v);
        return balance(v);
    }

    static node *insert_rightmost(node *v, node *u) {
        if (!v) return u;
        push_down(v);
        v->r = insert_rightmost(v->r, u);
        update(v);
        return balance(v);
    }

    // vと[l, r)が交差する時に使える
    // [v->lx, l), [r, v-rx)を切り取って返す
    static std::pair<node*, node*> split(node *v, Idx l, Idx r) {
        l = std::max(l, v->lx);
        r = std::min(r, v->rx);
        assert(l < r);
        node *a = nullptr, *c = nullptr;
        if (v->lx < l) a = new node(v->lx, l, v->val);
        if (r < v->rx) c = new node(r, v->rx, v->val);
        v->lx = l, v->rx = r;
        v->sum = pow_monoid(v->val, r - l);
        return {a, c};
    }

    node *root;

  public:
    segtree_lazy_sparse(Idx minf, Idx inf) : root(new node(minf, inf, e())) {}

    void set(Idx p, S x) {
        auto dfs = [&](auto &&dfs, node *v) -> node* {
            if (!v || p < v->Lx || v->Rx <= p) return v;
            push_down(v);
            if (p < v->lx) {
                v->l = dfs(dfs, v->l);
            } else if (v->rx <= p) {
                v->r = dfs(dfs, v->r);
            } else {
                auto [a, c] = split(v, p, p + 1);
                if (a) v->l = insert_rightmost(v->l, a);
                if (c) v->r = insert_leftmost(v->r, c);
                v->val = v->sum = x;
            }
            update(v);
            return balance(v);
        };
        root = dfs(dfs, root);
    }

    S get(Idx p) {
        node *v = root;
        while (v) {
            push_down(v);
            if (p < v->lx) {
                v = v->l;
            } else if (v->rx <= p) {
                v = v->r;
            } else {
                return v->val;
            }
        }
    }

    void apply(Idx l, Idx r, F lz) {
        auto dfs = [&](auto &&dfs, node *v) -> node* {
            if (!v || r <= v->Lx || v->Rx <= l) return v;
            if (l <= v->Lx && v->Rx <= r) {
                all_apply(v, lz);
                return v;
            }
            push_down(v);
            v->l = dfs(dfs, v->l);
            v->r = dfs(dfs, v->r);
            Idx L = std::max(l, v->lx), R = std::min(r, v->rx);
            if (L < R) {
                if (L != v->lx || R != v->rx) {
                    auto [a, c] = split(v, l, r);
                    if (a) v->l = insert_rightmost(v->l, a);
                    if (c) v->r = insert_leftmost(v->r, c);
                }
                v->val = mapping(lz, v->val, 1);
                v->sum = mapping(lz, v->sum, v->rx - v->lx);
            }
            update(v);
            return balance(v);
        };
        root = dfs(dfs, root);
    }

    S all_prod() {
        return (root ? root->sum_subtree : e());
    }

    S prod(Idx l, Idx r) {
        auto dfs = [&](auto &&dfs, node *v) -> S {
            if (!v || r <= v->Lx || v->Rx <= l) return e();
            if (l <= v->Lx && v->Rx <= r) return v->sum_subtree;
            push_down(v);
            S mid = e();
            Idx L = std::max(l, v->lx), R = std::min(r, v->rx);
            if (L < R) {
                if (l <= v->lx && v->rx <= r) mid = v->sum;
                else mid = pow_monoid(v->val, R - L);
            }
            return op(dfs(dfs, v->l), op(mid, dfs(dfs, v->r)));
        };
        return dfs(dfs, root);
    }

    template<typename G>
    Idx max_right(Idx l, G g) {
        assert(g(e()));
        S lsum = e();
        auto dfs = [&](auto &&dfs, node *v) -> void {
            if (!v) return;
            if (v->Lx == l && g(op(lsum, v->sum_subtree))) {
                l = v->Rx;
                lsum = op(lsum, v->sum_subtree);
                return;
            }
            push_down(v);
            if (v->rx <= l) {
                dfs(dfs, v->r);
                return;
            }
            if (l < v->lx) dfs(dfs, v->l);
            if (l < v->lx) return;
            S x = (v->lx == l ? v->sum : pow_monoid(v->val, v->rx - l));
            if (g(op(lsum, x))) {
                l = v->rx;
                lsum = op(lsum, x);
            } else {
                Idx len = 1;
                std::vector<S> p2{v->val};
                while (len < v->rx - l) {
                    S s = p2.back();
                    p2.push_back(op(s, s));
                    len *= 2;
                }
                for (int i = (int)p2.size() - 1; i >= 0; i--) {
                    len = Idx(1) << i;
                    if ((v->rx - l) >= len && g(op(lsum, p2[i]))) {
                        l += len;
                        lsum = op(lsum, p2[i]);
                    }
                }
                return;
            }
            dfs(dfs, v->r);
        };
        return dfs(dfs, root);
    }

    template<typename G>
    Idx min_left(Idx r, G g) {
        assert(g(e()));
        S rsum = e();
        auto dfs = [&](auto &&dfs, node *v) -> void {
            if (!v) return;
            if (v->Rx == r && g(op(v->sum_subtree, rsum))) {
                r = v->Lx;
                rsum = op(v->sum_subtree, rsum);
                return;
            }
            push_down(v);
            if (v->lx >= r) {
                dfs(dfs, v->l);
                return;
            }
            if (r > v->rx) dfs(dfs, v->r);
            if (r > v->rx) return;
            S x = (v->rx == r ? v->sum : pow_monoid(v->val, r - v->lx));

            if (g(op(x, rsum))) {
                r = v->lx;
                rsum = op(x, rsum);
            } else {
                Idx len = 1;
                std::vector<S> p2{v->val};
                while (len < r - v->lx) {
                    S s = p2.back();
                    p2.push_back(op(s, s));
                    len *= 2;
                }
                for (int i = (int)p2.size() - 1; i >= 0; i--) {
                    len = Idx(1) << i;
                    if ((r - v->lx) >= len && op(p2[i], rsum)) {
                        r -= len;
                        rsum = op(p2[i], rsum);
                    }
                }
                return;
            }
            dfs(dfs, v->l);
        };
        return dfs(dfs, root);
    }
};




#include <type_traits>
#include <iostream>








// @param m `1 <= m`
constexpr long long safe_mod(long long x, long long m){
  x %= m;
  if (x < 0) x += m;
  return x;
}

// x^n mod m
// @param n `0 <= n`
// @param m `1 <= m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

constexpr __uint128_t pow_mod64_constexpr(__int128_t x, __uint128_t n, unsigned long long m) {
    if (m == 1) return 0;
    __uint128_t r = 1;
    if (x >= m) x %= m;
    if (x < 0) x += m;
    while (n) {
        if (n & 1) r = (r * x) % m;
        x = (x * x) % m;
        n >>= 1;
    }
    return r;
}



constexpr bool miller_rabin32_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) { 
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}

template<int n>
constexpr bool miller_rabin32 = miller_rabin32_constexpr(n);



#include <cmath>
#include <tuple>

// -10^18 <= _a, _b <= 10^18
long long gcd(long long _a, long long _b) {
    long long a = abs(_a), b = abs(_b);
    if (a == 0) return b;
    if (b == 0) return a;
    int shift = __builtin_ctzll(a | b);
    a >>= __builtin_ctzll(a);
    do{
        b >>= __builtin_ctzll(b);
        if(a > b) std::swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

// 最大でa*b
// -10^18 <= a, b <= 10^18
// a, bは負でもいいが非負の値を返す
__int128_t lcm(long long a, long long b) {
    a = abs(a), b = abs(b);
    long long g = gcd(a, b);
    if (!g) return 0;
    return __int128_t(a) * b / g;
}

// {x, y, gcd(a, b)} s.t. ax + by = gcd(a, b)
// g >= 0
std::tuple<long long, long long, long long> extgcd(long long a, long long b) {
    long long x, y;
    for (long long u = y = 1, v = x = 0; a;) {
        long long q = b / a;
        std::swap(x -= q * u, u);
        std::swap(y -= q * v, v);
        std::swap(b -= q * a, a);
    }
    // x + k * (b / g), y - k * (a / g) も条件を満たす(kは任意の整数)
    return {x, y, b};
}

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;
    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}



template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct modint32_static {
    using mint = modint32_static;
  public:
    static constexpr int mod() { return m; }
    
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }
  
    modint32_static(): _v(0) {}
    
    template <class T>
    modint32_static(T v) { 
        long long x = v % (long long)umod();
        if (x < 0) x += umod();
        _v = x;
    }

    unsigned int val() const { return _v; }
    
    mint& operator ++ () {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator -- () {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator ++ (int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator -- (int) {
        mint result = *this;
        --*this;
        return result;
    }
    mint& operator += (const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator -= (const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator *= (const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator /= (const mint& rhs) { return *this = *this * rhs.inv(); }
    mint operator + () const { return *this; }
    mint operator - () const { return mint() - *this; }
    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }
    friend mint operator + (const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
    friend mint operator - (const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
    friend mint operator * (const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
    friend mint operator / (const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
    friend bool operator == (const mint& lhs, const mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const mint& lhs, const mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = miller_rabin32<m>;
};

template<int m>
std::ostream &operator<<(std::ostream &dest, const modint32_static<m> &a) {
    dest << a.val();
    return dest;
}

using modint998244353 = modint32_static<998244353>;
using modint1000000007 = modint32_static<1000000007>;



using mint = modint998244353;

using S = mint;
using F = std::pair<int, mint>;
using Idx = int;

S op(S x, S y) {
    return x + y;
}
S e() {
    return 0;
}

S mapping(F x, S y, Idx len) {
    if (x.first != -1) y = (mint)x.first * len;
    return y + x.second * len;
}

F composition(F x, F y) {
    if (x.first != -1) return x;
    return {y.first, y.second + x.second};
}

F id() {
    return {-1, mint(0)};
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }
    Idx inf = 1000000009;
    segtree_lazy_sparse<Idx, S, op, e, F, mapping, composition, id> seg(0, inf);
    for (int i = 0; i < N; i++) {
        mint sum = (!i ? mint(1) : seg.all_prod());
        sum *= -1;
        seg.apply(A[i] + 1, inf, {0, 0});
        seg.apply(1, A[i] + 1, {-1, sum});
    }
    mint ans = seg.all_prod();
    if (N & 1) ans = -ans;
    std::cout << ans.val() << '\n';
}

Submission Info

Judge Result