結果

問題 No.3452 Divide Permutation
コンテスト
ユーザー momoyuu
提出日時 2026-05-12 18:36:08
言語 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
結果
WA  
実行時間 -
コード長 7,892 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,969 ms
コンパイル使用メモリ 217,620 KB
実行使用メモリ 56,956 KB
最終ジャッジ日時 2026-05-12 18:37:06
合計ジャッジ時間 56,745 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 6 WA * 63
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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);
    atcoder::segtree<dat2, op2, e2> usemin(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);

    vector<int> mcan(n);

    auto judge = [&](int i) {
        // cout<<"j1"<<endl;
        int mx = conmax.get(i);
        int ni = usemin.prod(i + 1, n);
        if(ni>mx) {
            // cout<<"j2"<<endl;
            return;
        }
        can.set(i, i);
        int l = seg1.get(i).second.first;
        int r = seg1.get(i).second.second + 1;
        assert(0<=l&&l<=r&&r<=n);
        assert(pmax.prod(l, r) > ni);
        while(r-l>1) {
            int m = (l+r)/2;
            int mx = pmax.prod(l, m);
            if(ni<mx) r = m;
            else l = m;
        }
        mcan[i] = l;
        // cout<<"j2"<<endl;
    };

    auto add = [&](dat1 now,int i) {
        use.insert(i);
        notuse.set(i, e2());
        cutuse.insert(now.second.first);
        usemax.set(idx[i], idx[i]);
        usemin.set(i, 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());
        usemin.set(i, e2());
        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) {
            // cout<<"N"<<endl;
            bool fn = false;
            while(fn==false){
                // mc の 1 個前の component
                int mc = can.all_prod();
                int mmc = 1e9;
                if(0<=mc && mc < n) mmc = mcan[mc];
                int mn = notuse.all_prod();
                auto itrr = use.upper_bound(mn);
                int mm = n;
                if(itrr!=use.end()) mm = *itrr;
                if(mc < mm) {
                    auto dd = seg1.get(mc);
                    int l = dd.second.first;
                    int r = dd.second.second + 1;
                    //cout<<mmc<<" "<<l<<" "<<r<<" "<<n<<endl;
                    // if(pmax.prod(l, r) <= mc) {
                    //     judge(mc);
                    //     continue;
                    // }
                    cut(mmc);
                    // assert(pmax.prod(l,r) > mc);
                    // while(r-l>1){
                    //     int m = (r+l)/2;
                    //     assert(0<=l&&l<=m&&m<=m);
                    //     if(pmax.prod(l, m) > mc) r = m;
                    //     else l = m;
                    // }
                    // assert(r-1!=0);
                    // 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);
                }
                fn = true;

            }
            // cout<<"N1"<<endl;
        }

        // 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();
    }
}
0