結果

問題 No.3452 Divide Permutation
コンテスト
ユーザー lzm0107
提出日時 2026-02-25 22:25:10
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 5,905 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,795 ms
コンパイル使用メモリ 349,604 KB
実行使用メモリ 39,564 KB
最終ジャッジ日時 2026-02-25 22:26:01
合計ジャッジ時間 43,597 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45 RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// Author: lzm0107

#include <bits/stdc++.h>

using namespace std;

constexpr int kMod = 998'244'353, kInf32 = 0x3f3f3f3f;

constexpr int kMaxN = 200'000;

int pw10[kMaxN * 2 + 10];

struct Info0 {
    int min_val, max_val, hash_val, len;
    Info0() : min_val(kInf32), max_val(~kInf32), hash_val(0), len(0) {}
    Info0(int _min_val, int _max_val, int _hash_val, int _len) : min_val(_min_val), max_val(_max_val), hash_val(_hash_val), len(_len) {}
    Info0 operator+(Info0 rhs) const {
        return {
            min(min_val, rhs.min_val),
            max(max_val, rhs.max_val),
            (int)(((long long)hash_val * pw10[rhs.len] + rhs.hash_val) % kMod),
            len + rhs.len};
    }
    Info0 &operator+=(Info0 rhs) {
        return *this = *this + rhs;
    }
};

struct Info1 {
    Info0 d;
    int min_head, max_head;
    bool chance;
    Info1() : d(), min_head(kInf32), max_head(~kInf32), chance(false) {}
    Info1(Info0 _d, int x) : d(_d), min_head(x), max_head(x), chance(_d.min_val < x) {}
    Info1(Info0 _d, int _min_head, int _max_head, bool _chance) : d(_d), min_head(_min_head), max_head(_max_head), chance(_chance) {}
    Info1 operator+(Info1 rhs) const {
        return {
            d + rhs.d,
            min(min_head, rhs.min_head),
            max(max_head, rhs.max_head),
            chance || rhs.chance || max_head > rhs.d.min_val || d.max_val > rhs.min_head};
    }
    Info1 &operator+=(Info1 rhs) {
        return *this = *this + rhs;
    }
};

struct SegmentTree0 {
    Info0 d[(4 << __lg(kMaxN + 1)) + 10];
    int pn;
    void Build(int *arr, int n) {
        pn = 2 << (31 ^ __builtin_clz(n + 1));
        for (int i = 1; i < pn * 2; i++) {
            d[i] = Info0();
        }
        for (int i = 1; i <= n; i++) {
            d[i + pn] = {arr[i], arr[i], arr[i], 1};
        }
        for (int i = pn - 1; i >= 1; i--) {
            d[i] = d[i << 1] + d[i << 1 | 1];
        }
    }
    Info0 Query(int l, int r) {
        Info0 res_l, res_r;
        for (l += pn - 1, r += pn + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (l & 1 ^ 1) {
                res_l += d[l ^ 1];
            }
            if (r & 1) {
                res_r = d[r ^ 1] + res_r;
            }
        }
        return res_l + res_r;
    }
    int FindFirstGE(int pos, int val) {
        for (pos += pn; pos > 0 && ((pos & 1) || d[pos ^ 1].max_val < val); pos >>= 1) {}
        if (pos == 0) {
            return -1;
        }
        for (pos ^= 1; pos < pn; pos = pos << 1 | (d[pos << 1].max_val < val)) {}
        return pos - pn;
    }
} sgt0;

struct SegmentTree1 {
    Info1 d[(4 << __lg(kMaxN + 1)) + 10];
    int pn;
    void Build(int n) {
        pn = 2 << (31 ^ __builtin_clz(n + 1));
        for (int i = 1; i < pn * 2; i++) {
            d[i] = Info1();
        }
    }
    void Set(int pos, Info1 val) {
        pos += pn;
        d[pos] = val;
        for (pos >>= 1; pos > 0; d[pos] = d[pos << 1] + d[pos << 1 | 1], pos >>= 1) {}
    }
    array<int, 3> FindBetterSuffix() {
        Info1 sum;
        int pos = 1;
        for (; pos < pn;) {
            if (d[pos << 1].chance ||
                d[pos << 1].max_head > min(d[pos << 1 | 1].d.min_val, sum.d.min_val) ||
                d[pos << 1].d.max_val > min(d[pos << 1 | 1].min_head, sum.min_head)) {
                sum = d[pos << 1 | 1] + sum;
                pos <<= 1;
            } else {
                pos = pos << 1 | 1;
            }
        }
        return {pos - pn, min(d[pos].d.min_val, sum.d.min_val), sum.min_head};
    }
} sgt1;

int n, p[kMaxN + 10];
set<int> segment_start;

void Flip(int x) {
    int l, r;
    if (segment_start.count(x)) {
        auto it = segment_start.find(x);
        l = *prev(it), r = *next(it);
        segment_start.erase(it);
        sgt1.Set(p[l], Info1(sgt0.Query(l, r - 1), p[l]));
        sgt1.Set(p[x], Info1());
    } else {
        auto it = segment_start.insert(x).first;
        l = *prev(it), r = *next(it);
        sgt1.Set(p[l], Info1(sgt0.Query(l, x - 1), p[l]));
        sgt1.Set(p[x], Info1(sgt0.Query(x, r - 1), p[x]));
    }
}

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

    pw10[0] = 1;
    for (int i = 1; i <= kMaxN; i++) {
        pw10[i] = 10ll * pw10[i - 1] % kMod;
    }

    int T;
    cin >> T;
    while (T--) {
        static int ans[kMaxN + 10], q[kMaxN + 10];

        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> p[i];
            q[p[i]] = i;
        }
        sgt0.Build(p, n);
        sgt1.Build(n);
        sgt1.Set(p[1], Info1(sgt0.Query(1, n), p[1]));
        segment_start = {1, n + 1};
        for (int cur = 0; cur <= n; cur++) {
            ans[segment_start.size() - 1] = sgt1.d[1].d.hash_val;
            if (cur == n) {
                break;
            }
            bool cond0 = cur > 0 && q[cur] != n && p[q[cur] + 1] > cur + 1;
            bool cond1 = q[cur + 1] > 1 && p[q[cur + 1] - 1] > cur + 1;
            if (cond0 && cond1) {
                auto [x, y, z] = sgt1.FindBetterSuffix();
                int pos;
                if (y < x) {
                    pos = q[y];
                } else {
                    pos = sgt0.FindFirstGE(q[x], z);
                }
                if (pos == -1) {
                    ans[segment_start.size()] = ans[segment_start.size() - 1];
                } else {
                    Flip(pos);
                    ans[segment_start.size() - 1] = sgt1.d[1].d.hash_val;
                    Flip(pos);
                }
            }
            if (cond0) {
                Flip(q[cur] + 1);
            }
            if (cond1) {
                Flip(q[cur + 1]);
            }
        }
        for (int i = segment_start.size(); i <= n; i++) {
            ans[i] = ans[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}
0