#1164445 (C++23) No.3452 Divide Permutation

• 問題: No.3452 Divide Permutation
• ユーザー: momoyuu
• 提出日時: 2026-05-12 14:39:20
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 6,762 bytes
• コンパイル時間: 2,010 ms
• コンパイル使用メモリ: 218,476 KB
• 実行使用メモリ: 54,048 KB
• 最終ジャッジ日時: 2026-05-12 14:40:14
• 合計ジャッジ時間: 52,390 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	WA * 1
other	AC * 10 WA * 49 RE * 10

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
using ll = long long;

#include<set>
#include<atcoder/segtree>
#include<atcoder/modint>
#include<cassert>
using mint = atcoder::modint998244353;

using dat1 = pair<pair<mint,mint>,pair<int,int>>;
dat1 op1(dat1 a,dat1 b) {
    dat1 now;
    now.first.first = a.first.first * b.first.second + b.first.first;
    now.first.second = a.first.second * b.first.second;
    return now;
}

dat1 e1(){
    return make_pair(make_pair(0, 1), make_pair(-1, -1));
}

using dat2 = int;
dat2 op2(dat2 a,dat2 b) {
    return min(a,b);
}
dat2 e2() {
    return 1e9;
}

using dat3 = int;
dat3 op3(dat3 a,dat3 b){
    return max(a,b);
}
dat3 e3(){
    return -1;
}

int fuse = 0;
int f1(dat3 a) {
    return a < fuse;
}
void solve(){ 
    int n;
    cin>>n;
    vector<int> p(n);
    for(int i = 0;i<n;i++) cin>>p[i];
    for(int i = 0;i<n;i++) p[i]--;
    vector<int> idx(n);
    for(int i = 0;i<n;i++) {
        idx[p[i]] = i;
    }

    atcoder::segtree<dat1, op1, e1> seg1(n);
    // 数字の index
    set<int> use;
    // 場所の index
    set<int> cutuse;  

    atcoder::segtree<dat2, op2, e2> pmin(p);
    atcoder::segtree<dat3, op3, e3> pmax(p);
    atcoder::segtree<dat1, op1, e1> psum(n);
    atcoder::segtree<dat3, op3, e3> usemax(n);
    for(int i = 0;i<n;i++) {
        psum.set(i, make_pair(make_pair(p[i] + 1, 10),make_pair(i, i)));
    }

    atcoder::segtree<dat2, op2, e2> can(n);
    atcoder::segtree<dat2, op2, e2> notuse(n);
    for(int i = 0;i<n;i++) notuse.set(i, i);
    vector<int> ok(n, 0);
    atcoder::segtree<dat3, op3, e3> conmax(n);

    auto judge = [&](int i) {
        // cout<<i<<endl;
        int mx = conmax.prod(0, i);
        // cout<<i<<" "<<mx<<endl;
        if(mx>i) can.set(i, i);
    };

    auto add = [&](dat1 now,int i) {
        use.insert(i);
        notuse.set(i, e2());
        cutuse.insert(now.second.first);
        usemax.set(idx[i], idx[i]);
        ok[i] = 1;
        seg1.set(i, now);
        conmax.set(i, pmax.prod(now.second.first, now.second.second+1));

        judge(i);
        auto itr = use.upper_bound(i);
        if(itr!=use.end()) {
            int ni = *itr;
            can.set(ni,e2());
            judge(ni);
        }
    };

    auto erase = [&](int i) {
        auto ee = seg1.get(i);
        use.erase(i);
        notuse.set(i, i);
        cutuse.erase(ee.second.first);
        ok[i] = 0;
        conmax.set(i, e3());
        seg1.set(i, e1());
        usemax.set(idx[i], e3());

        can.set(i, e2());

        auto itr = use.upper_bound(i);
        if(itr!=use.end()) {
            int ni = *itr;
            can.set(ni, e2());
            judge(ni);
        }
    };

    for(int i = 0;i<n;i++){
        if(p[i]==i) {
            dat1 now;
            now.first.first = p[i] + 1;
            now.first.second = 10;
            now.second.first = i;
            now.second.second = i;
            add(now, i);
            continue;
        }

        int ni = p[i];
        dat1 now;
        now.first.first = 0;
        now.first.second = 1;
        now.second.first = i;
        now.second.second = n - 1;
        for(int j = i;j<n;j++){
            now.first.first *= 10;
            now.first.first += p[j] + 1;
            now.first.second *= 10;
        }
        add(now, ni);
        break;
    }

    vector<mint> ans(n+1);
    int last = 0;
    
    vector<pair<pair<int,int>,dat1>> rr;
    auto cut = [&](int i) {
        assert(i!=0);
        auto itr = cutuse.lower_bound(i);
        int r = n;
        if(itr!=cutuse.end()) r = *itr;
        assert(itr!=cutuse.begin());
        itr--;
        int l = *itr;

        int nl = p[l];
        dat1 nnl = seg1.get(nl);
        rr.push_back(make_pair(make_pair(nl, 0), nnl));
        
        dat1 newl = nnl;
        newl.second.second = i - 1;
        newl.first = psum.prod(l, i).first;
        add(newl, nl);
        rr.push_back(make_pair(make_pair(nl, 1), newl));

        dat1 newi;
        newi.second.first = i;
        newi.second.second = r - 1;
        newi.first = psum.prod(i, r).first;
        add(newi, p[i]);
        rr.push_back(make_pair(make_pair(p[i], 1), newi));
    };
    ans[0] = seg1.all_prod().first.first;

    for(int t = 1;t < n;) {
        mint tmp = 0;
        if(last==n){
            ans[t] = seg1.all_prod().first.first;
            t++;
            continue;
        }

        {
            int ni = idx[last];
            int nj = ni - 1;
            if(0<=nj && p[nj] == last - 1) {
                cut(ni);
            }
        }

        // assert(last!=n-1);
        int ni = last + 1;
        int need = 0;

        rr.clear();
        int pos = n;
        if(last-1>=0) pos = idx[last-1] + 1;

        if(pos!=n && cutuse.find(pos) == cutuse.end()) need++;
        if(cutuse.find(idx[last])==cutuse.end()) need++;
        if(need==0){
            last++;
            continue;
        }
        if(need==2) {
            // mc の 1 個前の component 
            int mc = can.all_prod();
            int mn = notuse.all_prod();
            auto itrr = use.upper_bound(mn);
            int mm = n;
            if(itrr!=use.end()) mm = *itrr;
            //cout<<mc<<" "<<mm<<endl;
            if(mc <= mm) {
                auto itr = use.find(mc);
                assert((*itr)==mc);
                itr--;
                int ni = *itr;
                auto dd = seg1.get(ni);
                int l = dd.second.first;
                int r = dd.second.second + 1;

                while(r-l>1){
                    int m = (r+l)/2;
                    if(pmax.prod(l, m) > mc) r = m;
                    else l = m;
                }
                cut(r-1);
            }else{
                int ni = idx[mn];
                cut(ni);

            }
                tmp = seg1.all_prod().first.first;
                reverse(rr.begin(),rr.end());
                for(auto e:rr){
                    if(e.first.second==1) erase(e.first.first);
                    else add(e.second, e.first.first);
                }
        }

        // cout<<t<<" "<<need<<" "<<last<<endl;
        if(pos!=n && cutuse.find(pos) == cutuse.end()){
            cut(pos);
        }else{
            int ni = idx[last];
            assert(cutuse.find(ni)==cutuse.end());
            cut(ni);
        }
        
        if(need!=2) {
            ans[t] = seg1.all_prod().first.first;
        }else{
            ans[t] = tmp;
        }
        t++;
        continue;
    }

    for(int i = 0;i<n;i++){
        cout<<ans[i].val();
        if(i!=n-1) cout<<" ";
        else cout<<endl;
    }
}

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

    int t;
    cin>>t;
    while(t--){
        solve();
    }
}