#1106090 (C++23) No.3208 Parse AND OR Affection

提出ソース
結果

問題	No.3208 Parse AND OR Affection
コンテスト
ユーザー	横山緑
提出日時	2025-07-20 12:34:54
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	453 ms / 5,000 ms
コード長	12,252 bytes
コンパイル時間	3,754 ms
コンパイル使用メモリ	297,360 KB
実行使用メモリ	33,184 KB
最終ジャッジ日時	2025-07-20 12:35:04
合計ジャッジ時間	10,474 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 20
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 2 "template.hpp"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.hpp>
#else
template <class T>
concept Streamable = requires(ostream os, T &x) { os << x; };
template <class mint>
concept is_modint = requires(mint &x) {
    { x.val() } -> std::convertible_to<int>;
};
#define debug(...)
#endif
template <Streamable T> void print_one(const T &value) { cout << value; }
template <is_modint T> void print_one(const T &value) { cout << value.val(); }
void print() { cout << '\n'; }
template <class T, class... Ts> void print(const T &a, const Ts &...b) {
    print_one(a);
    ((cout << ' ', print_one(b)), ...);
    cout << '\n';
}
template <ranges::range Iterable>
    requires(!Streamable<Iterable>)
void print(const Iterable &v) {
    for(auto it = v.begin(); it != v.end(); ++it) {
        if(it != v.begin())
            cout << " ";
        print_one(*it);
    }
    cout << '\n';
}
using vi = vector<int>;
using vii = vector<vector<int>>;
using pii = pair<int, int>;
using ll = long long;
using vl = vector<ll>;
using vll = vector<vl>;
using pll = pair<ll, ll>;
#define all(v) begin(v), end(v)
template <class T> void UNIQUE(T &v) {
    ranges::sort(v);
    v.erase(unique(all(v)), end(v));
}
template <typename T> inline bool chmax(T &a, T b) {
    return ((a < b) ? (a = b, true) : (false));
}
template <typename T> inline bool chmin(T &a, T b) {
    return ((a > b) ? (a = b, true) : (false));
}
// https://trap.jp/post/1224/
template <class... T> constexpr auto min(T... a) {
    return min(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> constexpr auto max(T... a) {
    return max(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> void input(T &...a) { (cin >> ... >> a); }
template <class T> void input(vector<T> &a) {
    for(T &x : a)
        cin >> x;
}
#define INT(...)                                                               \
    int __VA_ARGS__;                                                           \
    input(__VA_ARGS__)
#define LL(...)                                                                \
    long long __VA_ARGS__;                                                     \
    input(__VA_ARGS__)
#define STR(...)                                                               \
    string __VA_ARGS__;                                                        \
    input(__VA_ARGS__)
#define REP1_0(n, c) REP1_1(n, c)
#define REP1_1(n, c)                                                           \
    for(ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(n); REP_COUNTER_##c++)
#define REP1(n) REP1_0(n, __COUNTER__)
#define REP2(i, a) for(ll i = 0; i < (ll)(a); i++)
#define REP3(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++)
#define REP4(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c))
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
ll inf = 3e18;
vl dx = {1, -1, 0, 0};
vl dy = {0, 0, 1, -1};
template <class T> constexpr T floor(T x, T y) noexcept {
    return x / y - ((x ^ y) < 0 and x % y);
}
template <class T> constexpr T ceil(T x, T y) noexcept {
    return x / y + ((x ^ y) >= 0 and x % y);
}
// yの符号に関わらず非負で定義 \bmod:texコマンド
template <class T> constexpr T bmod(T x, T y) noexcept {
    T m = x % y;
    return (m < 0) ? m + (y > 0 ? y : -y) : m;
}
template <std::signed_integral T> constexpr int bit_width(T x) noexcept {
    return std::bit_width((uint64_t)x);
}
template <std::signed_integral T> constexpr int popcount(T x) noexcept {
    return std::popcount((uint64_t)x);
}
constexpr bool kth_bit(auto n, auto k) { return (n >> k) & 1; }
#line 3 "data-structure/lazy-segtree.hpp"
// template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
//           F (*composition)(F, F), F (*id)()>
template <class S, auto op, S (*e)(), class F, auto mapping, auto composition,
          auto id>
//   composition(f,g)(x) = f∘g(x) = f(g(x))
// aclと同じ、maspyさん記事と逆
struct lazy_segtree {
    int n;
    vector<S> v;
    vector<F> vf;
    explicit lazy_segtree(int n)
        : n(n), v(vector<S>(2 * n, e())), vf(vector<F>(2 * n, id())) {};
    explicit lazy_segtree(const vector<S> &v_)
        : n(v_.size()), v(2 * n, e()), vf(2 * n, id()) {
        for(int i = 0; i < n; ++i)
            v[i + n] = v_[i];
        for(int i = n - 1; i > 0; --i)
            v[i] = op(v[i << 1], v[i << 1 | 1]);
    }
    void apply(int l, int r, F f) {
        l += n;
        r += n;
        int l0 = l / (l & -l);
        int r0 = r / (r & -r) - 1;
        propagate_above(l0);
        propagate_above(r0);
        while(l < r) {
            if(l & 1) {
                apply_at(l, f);
                l++;
            }
            if(r & 1) {
                r--;
                apply_at(r, f);
            }
            l >>= 1;
            r >>= 1;
        }
        recul_above(l0);
        recul_above(r0);
    }
    S get(int x) {
        x += n;
        int maxi = (int)bit_width((unsigned)x) - 1;
        for(int i = maxi; i > 0; --i)
            propagate_at(x >> i);
        return v[x];
    }
    void set(int x, S s) {
        x += n;
        propagate_above(x);
        v[x] = s;
        recul_above(x);
    }
    S prod(int l, int r) {
        l += n;
        r += n;
        int l0 = l / (l & -l);
        int r0 = r / (r & -r) - 1;
        propagate_above(l0);
        propagate_above(r0);
        S sl = e(), sr = e();
        while(l < r) {
            if(l & 1) {
                sl = op(sl, v[l]);
                l++;
            }
            if(r & 1) {
                r--;
                sr = op(v[r], sr);
            }
            l >>= 1;
            r >>= 1;
        }
        return op(sl, sr);
    }
    S all_prod_commute() {
        // 可換なモノイド専用
        // 2冪にすれば非可換でも良さそう
        return v[1];
    }

  private:
    void apply_at(int x, F f) {
        v[x] = mapping(f, v[x]);
        if(x < n)
            vf[x] = composition(f, vf[x]);
    }
    void propagate_at(int x) {
        apply_at(x << 1, vf[x]);
        apply_at(x << 1 | 1, vf[x]);
        vf[x] = id();
    }
    void propagate_above(int x) {
        int maxi = (int)bit_width((unsigned)x) - 1;
        for(int i = maxi; i > 0; --i) {
            propagate_at(x >> i);
        }
        return;
    }
    void recul_above(int x) {
        while(x > 1) {
            x >>= 1;
            v[x] = op(v[x << 1], v[x << 1 | 1]);
        }
    }
};
#line 3 "math/matrix.hpp"
template <class T> struct Matrix {
    int height, width;
    vector<T> A;
    Matrix() = default;
    Matrix(int n, int m) : height(n), width(m), A(n * m, T(0)) {}
    Matrix(int n) : Matrix(n, n) {}
    Matrix(vector<vector<T>> A_) : height(A_.size()), width(A_[0].size()) {
        A.reserve(height * width);
        for(auto &&row : A_ | views::join)
            A.emplace_back(row);
    }
    inline const T &operator()(int i, int j) const { return A[i * width + j]; }
    inline T &operator()(int i, int j) { return A[i * width + j]; }
    void show() const {
        for(int i = 0; i < height; ++i) {
            for(int j = 0; j < width; ++j) {
                if constexpr(is_arithmetic_v<T>) {
                    cout << (*this)(i, j) << " \n"[j + 1 == width];
                } else {
                    // atcoder::modint用
                    cout << (*this)(i, j).val() << " \n"[j + 1 == width];
                }
            }
        }
    }

    Matrix &operator+=(const Matrix &B) {
        assert(height == B.height && width == B.width);
        for(int i = 0; i < height * width; ++i)
            A[i] += B.A[i];
        return *this;
    }
    Matrix &operator-=(const Matrix &B) {
        assert(height == B.height && width == B.width);
        for(int i = 0; i < height * width; ++i)
            A[i] -= B.A[i];
        return *this;
    }
    Matrix &operator*=(const Matrix &B) {
        assert(width == B.height);
        // (height,width)*(B.height,B.width) -> (height,B.width)
        Matrix<T> res(height, B.width);
        for(int i = 0; i < height; ++i) {
            for(int k = 0; k < width; ++k) {
                for(int j = 0; j < B.width; ++j) {
                    res(i, j) += (*this)(i, k) * B(k, j);
                }
            }
        }
        swap(*this, res);
        return *this;
    }
    Matrix &operator^=(size_t k) {
        assert(height == width);
        Matrix<T> res(height);
        for(int i = 0; i < height; ++i)
            res(i, i) = T(1);
        while(k) {
            if(k & 1) {
                res *= (*this);
            }
            (*this) *= (*this);
            k >>= 1;
        }
        swap(res, *this);
        return *this;
    }
    [[nodiscard]] Matrix pow(size_t k) const {
        auto res(*this);
        res ^= k;
        return res;
    }
    [[nodiscard]] Matrix operator+(const Matrix &B) const {
        return Matrix(*this) += B;
    }
    [[nodiscard]] Matrix operator-(const Matrix &B) const {
        return Matrix(*this) -= B;
    }
    [[nodiscard]] Matrix operator*(const Matrix &B) const {
        return Matrix(*this) *= B;
    }
};
#line 4 "/home/y_midori/cp/test.cpp"
struct S {
    ll t{}, f{}, rt{}, rf{};
};
S op(S a, S b) { return S(a.t + b.t, a.f + b.f, a.rt + b.rt, a.rf + b.rf); }
S e() { return S(); }
struct F {
    // A = [[a00,a01],[a10,a11]],  B = [[b00,b01],[b10,b11]]
    ll a00, a01, a10, a11;
    ll b00, b01, b10, b11;
};
S mapping(const F &f, const S &s) {
    S res;
    // new rt, rf
    res.rt = f.a00 * s.rt + f.a01 * s.rf;
    res.rf = f.a10 * s.rt + f.a11 * s.rf;
    // new t, f
    res.t = s.t + f.b00 * s.rt + f.b01 * s.rf;
    res.f = s.f + f.b10 * s.rt + f.b11 * s.rf;
    return res;
}

F cmp(const F &g, const F &f) {
    F h;
    // h.A = g.A * f.A
    h.a00 = g.a00 * f.a00 + g.a01 * f.a10;
    h.a01 = g.a00 * f.a01 + g.a01 * f.a11;
    h.a10 = g.a10 * f.a00 + g.a11 * f.a10;
    h.a11 = g.a10 * f.a01 + g.a11 * f.a11;
    // h.B = g.B * f.A + f.B
    h.b00 = g.b00 * f.a00 + g.b01 * f.a10 + f.b00;
    h.b01 = g.b00 * f.a01 + g.b01 * f.a11 + f.b01;
    h.b10 = g.b10 * f.a00 + g.b11 * f.a10 + f.b10;
    h.b11 = g.b10 * f.a01 + g.b11 * f.a11 + f.b11;
    return h;
}

F id() { return F{1, 0, 0, 1, 0, 0, 0, 0}; }
static const F OP_F = {0, 0, 1, 1, 0, 0, 1, 1};
static const F OP_plusT = {1, 1, 0, 0, 1, 1, 0, 0};
static const F OP_xorT = {0, 1, 1, 0, 0, 1, 1, 0};
static const F OP_id = {1, 0, 0, 1, 1, 0, 0, 1};
void solve() {
    INT(n, q);
    STR(s);
    n = ceil(n, 2);
    vi l(q), r(q), ord(q);
    rep(i, q) {
        input(l[i], r[i]);
        l[i] /= 2;
        r[i] = ceil(r[i], 2);
        ord[i] = i;
    }
    ranges::sort(ord, {}, [&](int i) { return r[i]; });
    vl ans(q);
    lazy_segtree<S, op, e, F, mapping, cmp, id> seg([&] {
        vector<S> v(n);
        rep(i, n) {
            bool flag = s[2 * i] == 'T';
            v[i] = S(flag, !flag, flag, !flag);
        }
        return v;
    }());

    int cur_r = 1;
    for(auto i : ord) {
        while(r[i] > cur_r) {
            char c1 = s[2 * cur_r - 1];
            char c2 = s[2 * cur_r];
            const F *opF = &OP_id;
            if(c1 == '*' && c2 == 'F') {
                opF = &OP_F;
            } else if(c1 == '+' && c2 == 'T') {
                opF = &OP_plusT;
            } else if(c1 == '^' && c2 == 'T') {
                opF = &OP_xorT;
            }
            // [0, cur_r) の範囲に一括で適用
            seg.apply(0, cur_r, *opF);
            cur_r++;
        }
        ans[i] = seg.prod(l[i], r[i]).t;
        // #ifdef LOCAL
        //         debug(i, l[i], r[i], cur_r);
        //         rep(j, n) cout << seg.get(j).t << " \n"[j + 1 == n];
        //         rep(j, n) cout << seg.get(j).f << " \n"[j + 1 == n];
        //         rep(j, n) cout << seg.get(j).rt << " \n"[j + 1 == n];
        //         rep(j, n) cout << seg.get(j).rf << " \n"[j + 1 == n];
        // #endif
    }
    rep(i, q) { print(ans[i]); }
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    rep(t) solve();
}
yukicoder

結果

ソースコード
