結果

問題 No.3452 Divide Permutation
コンテスト
ユーザー 👑 potato167
提出日時 2026-02-18 03:36:59
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 7,257 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,810 ms
コンパイル使用メモリ 234,456 KB
実行使用メモリ 27,776 KB
最終ジャッジ日時 2026-02-20 20:55:18
合計ジャッジ時間 19,116 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 WA * 12 TLE * 1 -- * 52
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
#include <atcoder/modint>
using mint = atcoder::modint998244353;

// ローリングハッシュの base
int base = 10;

#include <atcoder/segtree>
struct F{
    mint v = 0;
    mint b = 1;
};
F op(F l, F r){
    l.v *= r.b;
    l.v += r.v;
    l.b *= r.b;
    return l;
}
F e(){
    return F{};
}

// 今回の base = 10 は、
// 998244353 の原始根
bool f(F x){
    return x.b == 1;
}

int op_max(int a, int b){
    return max(a, b);
}
int e_max(){
    return -1;
}
int target;
bool g(int x){
    return x < target;
}

int op_min(int a, int b){
    return min(a, b);
}
int e_min(){
    return (1 << 30);
}
bool h(int x){
    return target <= x;
}

vector<mint> solve(vector<int> p){
    int N = p.size();
    // p 自体の hash
    atcoder::segtree<F, op, e> p_hash(N);
    rep(i, 0, N) p_hash.set(i, {p[i], base}), p[i]--;
    vector<int> inv(N);
    rep(i, 0, N) inv[p[i]] = i;

    // p の max の列
    atcoder::segtree<int, op_max, e_max> p_max(p);
    // p の min の列
    atcoder::segtree<int, op_min, e_min> p_min(p);
    // 区間であって、先頭より小さいものの最小値
    atcoder::segtree<int, op_min, e_min> cut_min(N);

    // スペシャル mex というのを定義する。
    // 区間 [l, r) のスペシャル mex というのは、
    // p[l] 以上かつ、先頭である最小の数を m としたとき
    // l < i < r かつ m < p[i] を満たす最小の index i
    // これが存在しないとき、-1 とする
    atcoder::segtree<int, op_max, e_max> mex(N);

    // 答えの hash
    atcoder::segtree<F, op, e> ans_seg(N);


    // 分割した順列を、その並び順で並べる
    atcoder::segtree<F, op, e> perm_seg(N);


    // スペシャル mex を計算する。
    auto sp_mex = [&](int ind) -> void {
        int m = ans_seg.max_right<f>(p[ind] + 1);
        int r = perm_seg.max_right<f>(ind + 1);
        target = m;
        int nr = p_max.max_right<g>(ind);

        if (nr < r) mex.set(p[ind], nr);
        else mex.set(p[ind], -1);
    };

    // ある区間の cut_min を計算する
    auto calc_cut_min = [&](int ind) -> int {
        int r = perm_seg.max_right<f>(ind + 1);
        auto res = p_min.prod(ind + 1, r);
        if (p[ind] < res) return -1;
        else return res;
    };

    auto set_calc_min = [&](int ind) -> void {
        auto tmp = calc_cut_min(ind);
        if (tmp != -1){
            cut_min.set(tmp, tmp);
        }
    };

    auto seg_set = [&](int l, int r) -> void {
        // cerr << "seg set " << l << " " << r << endl;
        perm_seg.set(l, p_hash.prod(l, r));
        ans_seg.set(p[l], perm_seg.get(l));
    };

    seg_set(0, N);

    // 答えを変更する。
    // cut(i) で、i の直前で切る
    auto cut = [&](int i) -> bool {
        if (perm_seg.get(i).b == 1){
            int a = perm_seg.min_left<f>(i) - 1;
            int c = perm_seg.max_right<f>(i + 1);
            // cut min を除く
            {
                int tmp = calc_cut_min(a);
                if (tmp != -1){
                    cut_min.set(tmp, e_min());
                }
            }

            seg_set(a, i);
            seg_set(i, c);
            // スペシャル mex を計算させる
            // 計算対象は、a, i はもちろん
            // p[i] の一個前も必須
            sp_mex(a);
            sp_mex(i);
            {
                int tmp = ans_seg.min_left<f>(p[i]);
                if (tmp) sp_mex(inv[tmp - 1]);
            }
            // cut min を求める
            set_calc_min(a);
            set_calc_min(i);
            return true;
        }
        return false;
    };

    // 実際の返り値
    vector<mint> res(N);
    // res の何番目まで埋めたか
    int ind = 0;
    res[0] = ans_seg.all_prod().v;
    ind = 1;
    // n <- 先頭に持っていきたい値
    rep(n, 0, N){
        if (n == 0){
            if (p[0]){
                cut(inv[0]);
                res[ind] = ans_seg.all_prod().v;
                ind++;
            }
            continue;
        }
        // n - 1 まで並んでいる。
        // n を次の番にできるか？

        // n - 1, n の順で並んでいたら、何もしなくていい
        if (p[0] != n && inv[n - 1] + 1 == inv[n]) continue;

        //やるべきことは？
        // n - 1 の後ろを切る
        int back_cut = 0;
        if (p[N - 1] != n - 1 && perm_seg.get(inv[n - 1] + 1).b == 1){
            back_cut = 1;
        }
        // n の前を切る
        int front_cut = 0;
        if (perm_seg.get(inv[n]).b == 1) front_cut = 1;
        if (back_cut + front_cut == 0) continue;

        // 適当に切る必要がある
        if (back_cut + front_cut == 2){
            // 切るべき場所を探す

            int tmp = ans_seg.min_left<f>(n) - 1;
            int T = 5;
            while (true){
                if (tmp > cut_min.all_prod() || tmp == N) break;
                T--;
                if (T == 0){
                    tmp = N;
                    break;
                }
                int nx = ans_seg.max_right<f>(tmp + 1);
                int id = inv[tmp] + 1;
                bool ok = false;
                while (id != N && perm_seg.get(id).b == 1){
                    if (nx < p[id]){
                        ok = true;
                        break;
                    }
                    id++;
                }
                if (ok) break;
                tmp = nx;
            }

            // 先頭より小さいの消し
            if (tmp > cut_min.all_prod()){
                tmp = cut_min.all_prod();
                int m = inv[tmp];
                int l = perm_seg.min_left<f>(m) - 1;
                int r = perm_seg.max_right<f>(m);
                // [l, r) -> [l, m), [m, r)
                seg_set(l, m);
                seg_set(m, r);
                res[ind++] = ans_seg.all_prod().v;
                seg_set(l, r);
                seg_set(m, m);
            }
                // 切る場所がなかったらそのまま
            else if (tmp == N){
                res[ind] = res[ind - 1];
                ind++;
            }
            else{
                int l = inv[tmp];
                int r = perm_seg.max_right<f>(l + 1);
                int m = mex.get(tmp);
                // [l, r) -> [l, m), [m, r)
                seg_set(l, m);
                seg_set(m, r);
                res[ind++] = ans_seg.all_prod().v;
                seg_set(l, r);
                seg_set(m, m);
            }
        }

        if (back_cut) cut(inv[n - 1] + 1);
        if (front_cut) cut(inv[n]);
        res[ind] = ans_seg.all_prod().v;
        ind++;
    }
    while (ind != N) res[ind] = res[ind - 1], ind++;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--){
        int N;
        cin >> N;
        vector<int> p(N);
        rep(i, 0, N){
            cin >> p[i];
        }
        auto ans = solve(p);
        rep(i, 0, N){
            cout << ans[i].val() << (i + 1 == N ? "\n" : " ");
        }
    }
}
0