結果

問題 No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント
ユーザー tokusakuraitokusakurai
提出日時 2021-06-11 23:33:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 539 ms / 4,500 ms
コード長 8,655 bytes
コンパイル時間 2,563 ms
コンパイル使用メモリ 222,256 KB
実行使用メモリ 129,528 KB
最終ジャッジ日時 2023-08-21 14:37:18
合計ジャッジ時間 14,719 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 271 ms
65,980 KB
testcase_03 AC 85 ms
34,672 KB
testcase_04 AC 241 ms
126,084 KB
testcase_05 AC 23 ms
10,788 KB
testcase_06 AC 202 ms
63,860 KB
testcase_07 AC 221 ms
129,020 KB
testcase_08 AC 281 ms
66,348 KB
testcase_09 AC 198 ms
35,788 KB
testcase_10 AC 186 ms
125,124 KB
testcase_11 AC 225 ms
125,752 KB
testcase_12 AC 126 ms
18,716 KB
testcase_13 AC 120 ms
125,688 KB
testcase_14 AC 197 ms
33,764 KB
testcase_15 AC 123 ms
129,224 KB
testcase_16 AC 222 ms
67,760 KB
testcase_17 AC 283 ms
124,616 KB
testcase_18 AC 226 ms
128,044 KB
testcase_19 AC 110 ms
34,016 KB
testcase_20 AC 161 ms
126,588 KB
testcase_21 AC 184 ms
64,384 KB
testcase_22 AC 346 ms
129,232 KB
testcase_23 AC 356 ms
129,200 KB
testcase_24 AC 361 ms
129,208 KB
testcase_25 AC 347 ms
129,248 KB
testcase_26 AC 353 ms
129,304 KB
testcase_27 AC 352 ms
129,260 KB
testcase_28 AC 338 ms
129,356 KB
testcase_29 AC 359 ms
129,208 KB
testcase_30 AC 358 ms
129,308 KB
testcase_31 AC 351 ms
129,408 KB
testcase_32 AC 210 ms
129,296 KB
testcase_33 AC 215 ms
129,288 KB
testcase_34 AC 212 ms
129,216 KB
testcase_35 AC 217 ms
129,424 KB
testcase_36 AC 187 ms
129,420 KB
testcase_37 AC 539 ms
129,344 KB
testcase_38 AC 183 ms
129,320 KB
testcase_39 AC 187 ms
129,212 KB
testcase_40 AC 187 ms
129,528 KB
testcase_41 AC 189 ms
129,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define each(e, v) for(auto &e: v)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
//const int MOD = 1000000007;
const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

struct io_setup{
    io_setup(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout << fixed << setprecision(15);
    }
} io_setup;

template<int mod>
struct Mod_Int{
    int x;

    Mod_Int() : x(0) {}

    Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    Mod_Int &operator += (const Mod_Int &p){
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int &operator -= (const Mod_Int &p){
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int &operator *= (const Mod_Int &p){
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    Mod_Int &operator /= (const Mod_Int &p){
        *this *= p.inverse();
        return *this;
    }

    Mod_Int &operator ++ () {return *this += Mod_Int(1);}

    Mod_Int operator ++ (int){
        Mod_Int tmp = *this;
        ++*this;
        return tmp;
    }

    Mod_Int &operator -- () {return *this -= Mod_Int(1);}

    Mod_Int operator -- (int){
        Mod_Int tmp = *this;
        --*this;
        return tmp;
    }

    Mod_Int operator - () const {return Mod_Int(-x);}

    Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}

    Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}

    Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}

    Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}

    bool operator == (const Mod_Int &p) const {return x == p.x;}

    bool operator != (const Mod_Int &p) const {return x != p.x;}

    Mod_Int inverse() const{
        assert(*this != Mod_Int(0));
        return pow(mod-2);
    }

    Mod_Int pow(long long k) const{
        Mod_Int now = *this, ret = 1;
        for(; k > 0; k >>= 1, now *= now){
            if(k&1) ret *= now;
        }
        return ret;
    }

    friend ostream &operator << (ostream &os, const Mod_Int &p){
        return os << p.x;
    }

    friend istream &operator >> (istream &is, Mod_Int &p){
        long long a;
        is >> a;
        p = Mod_Int<mod>(a);
        return is;
    }
};

using mint = Mod_Int<MOD>;

template<typename Monoid, typename Operator_Monoid>
struct Lazy_Segment_Tree{
    using F = function<Monoid(Monoid, Monoid)>;
    using G = function<Monoid(Monoid, Operator_Monoid)>;
    using H = function<Operator_Monoid(Operator_Monoid, Operator_Monoid)>;
    int n, height;
    vector<Monoid> seg;
    vector<Operator_Monoid> lazy;
    const F f;
    const G g;
    const H h;
    const Monoid e1;
    const Operator_Monoid e2;
    
    Lazy_Segment_Tree(const vector<Monoid> &v, const F &f, const G &g, const H &h, const Monoid &e1, const Operator_Monoid &e2)
        : f(f), g(g), h(h), e1(e1), e2(e2){
        int m = v.size();
        n = 1, height = 0;
        while(n < m) n <<= 1, height++;
        seg.assign(2*n, e1), lazy.assign(2*n, e2);
        copy(begin(v), end(v), seg.begin()+n);
        for(int i = n-1; i > 0; i--) seg[i] = f(seg[2*i], seg[2*i+1]);
    }

    inline Monoid reflect(int i) const{
        return (lazy[i] == e2? seg[i] : g(seg[i], lazy[i]));
    }

    inline void recalc(int i){
        while(i >>= 1) seg[i] = f(reflect(2*i), reflect(2*i+1));
    }

    inline void eval(int i){
        if(i < n && lazy[i] != e2){
            lazy[2*i] = h(lazy[2*i] ,lazy[i]);
            lazy[2*i+1] = h(lazy[2*i+1], lazy[i]);
            seg[i] = reflect(i), lazy[i] = e2;
        }
    }

    inline void thrust(int i){
        for(int j = height; j > 0; j--) eval(i>>j);
    }
    
    void apply(int l, int r, const Operator_Monoid &x){
        l = max(l, 0), r = min(r, n);
        if(l >= r) return;
        l += n, r += n;
        thrust(l), thrust(r-1);
        int a = l, b = r;
        while(l < r){
            if(l&1) lazy[l] = h(lazy[l], x), l++;
            if(r&1) r--, lazy[r] = h(lazy[r], x); 
            l >>= 1, r >>= 1;
        }
        recalc(a), recalc(b-1);
    }
    
    Monoid query(int l, int r){
        l = max(l, 0), r = min(r, n);
        if(l >= r) return e1;
        l += n, r += n;
        thrust(l), thrust(r-1);
        Monoid L = e1, R = e1;
        while(l < r){
            if(l&1) L = f(L, reflect(l++));
            if(r&1) R = f(reflect(--r), R);
            l >>= 1, r >>= 1;
        }
        return f(L, R);
    }

    Monoid operator [] (int i) {return query(i, i+1);}

    template<typename C>
    int find_subtree(int i, const C &check, const Monoid &x, Monoid &M, bool type){
        while(i < n){
            eval(i);
            Monoid nxt = type? f(reflect(2*i+type), M) : f(M, reflect(2*i+type));
            if(check(nxt, x)) i = 2*i+type;
            else M = nxt, i = 2*i+(type^1);
        }
        return i-n;
    }
 
    template<typename C>
    int find_first(int l, const C &check, const Monoid &x){
        Monoid L = e1;
        int a = l+n, b = n+n;
        thrust(a);
        while(a < b){
            if(a&1){
                Monoid nxt = f(L, reflect(a));
                if(check(nxt, x)) return find_subtree(a, check, x, L, false);
                L = nxt, a++;
            }
            a >>= 1, b >>= 1;
        }
        return n;
    }
 
    template<typename C>
    int find_last(int r, const C &check, const Monoid &x){
        Monoid R = e1;
        int a = n, b = r+n;
        thrust(b-1);
        while(a < b){
            if(b&1 || a == 1){
                Monoid nxt = f(reflect(--b), R);
                if(check(nxt, x)) return find_subtree(b, check, x, R, true);
                R = nxt;
            }
            a >>= 1, b >>= 1;
        }
        return -1;
    }
};

int main(){
    int N; cin >> N;

    vector<vector<pll>> a(5, vector<pll>(N, pll(1, 1)));
    rep(i, N){
        ll x; cin >> x;
        rep(j, 4){
            a[j+1][i].first = (a[j][i].first*x)%MOD;
        }
    }

    auto f = [](pll a, pll b) {return pll((a.first+b.first)%MOD, a.second+b.second);};
    auto g = [](pll a, ll b) {return (b == -1? a : pll(b*a.second%MOD, a.second));};
    auto h = [](ll a, ll b) {return (b == -1? a : b);};

    vector<Lazy_Segment_Tree<pll, ll>> bit;
    rep(i, 5) bit.eb(a[i], f, g, h, pll(0, 0), -1);

    int Q; cin >> Q;

    while(Q--){
        int t, u, v, w; cin >> t >> u >> v >> w;
        if(u > v) swap(u, v);
        
        bool flag = !(u < w && w < v); 
        if(flag) v--;
        else u--;

        //cout << u << ' ' << v << ' ' << flag << '\n';
        //cout << bit[0].query(0, N).first << '\n';

        vector<mint> b(5, 0);
        rep(i, 5){
            b[i] = bit[i].query(u, v).first;
            if(flag) b[i] = -b[i]+bit[i].query(0, N).first;
        }

        mint L = b[0].inverse();
        mint M = b[1]*L;

        //rep(i, 5) cout << b[i] << ' '; cout << '\n';

        if(t == 0){
            vector<ll> c(5, 1);
            ll x; cin >> x;
            rep(i, 4){
                c[i+1] = (c[i]*x)%MOD;
            }

            if(!flag){
                rep(i, 5){
                    bit[i].apply(u, v, c[i]);
                }
            }
            else{
                rep(i, 5){
                    bit[i].apply(0, u, c[i]);
                    bit[i].apply(v, N, c[i]);
                }
            }
            continue;
        }
        
        mint ans = 0;

        if(t == 1){
            ans -= M*b[0];
            ans += b[1];
        }
        if(t == 2){
            ans += M*M*b[0];
            ans -= M*2*b[1];
            ans += b[2];
        }
        if(t == 3){
            ans -= M*M*M*b[0];
            ans += M*M*3*b[1];
            ans -= M*3*b[2];
            ans += b[3];
        }
        if(t == 4){
            ans += M*M*M*M*b[0];
            ans -= M*M*M*4*b[1];
            ans += M*M*6*b[2];
            ans -= M*4*b[3];
            ans += b[4];
        }

        cout << ans*L << '\n';
    }
}
0