题解：P13524 [KOI 2025 #2] 跳跃

· · 题解

爱来自联考模拟，分享一个唐氏 O(n\log n) 做法。

Key Observation 1：出现次数都是奇数。

Key Observation 2：将出现次数的连续段搞出来，相邻两段的差一定为 2。

Key Observation 3：出现次数等于 3 是好处理的，找到一个这样的连续段，走过去、走过来，这样就覆盖两次了，然后就转换成出现一次的情况了。

然后我们直接开始模拟。

若当前出现次数为 1，不断往右填直到下一个出现次数为 3。找到后面第一个出现次数降回 1 的位置，走过去、走回来，再将这段区间整体减二，递归处理这段区间，注意最后走到区间末尾的时候需要跳一步。

维护两个线段树，一个代表出现次数，一个代表当前走了哪些位置。往右填的过程可以在第一棵线段树上二分出第一个未被覆盖的位置，区间整体减二以及找到第一个出现次数等于一的位置可以在第二棵线段树上二分即可。复杂度 O(n\log n)。挑战最劣解。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,tot;
int a[N],p[N];
struct tree{
    int l,r,mn,mnpos,tag;
}t[N*4],t2[N*4];
void pushup(int u){
    t[u].mn=min(t[u*2].mn,t[u*2+1].mn);
    t[u].mnpos=(t[u].mn==t[u*2].mn?t[u*2].mnpos:t[u*2+1].mnpos);
}
void pushup2(int u){
    t2[u].mn=min(t2[u*2].mn,t2[u*2+1].mn);
    t2[u].mnpos=(t2[u].mn==t2[u*2].mn?t2[u*2].mnpos:t2[u*2+1].mnpos);
}
void build(int u,int l,int r){
    t[u].l=l,t[u].r=r;
    if(l==r){
        t[u].mn=a[l],t[u].mnpos=l;
        return;
    }
    int mid=(l+r)/2;
    build(u*2,l,mid),build(u*2+1,mid+1,r);
    pushup(u);
}
void build2(int u,int l,int r){
    t2[u].l=l,t2[u].r=r,t2[u].mn=0;
    if(l==r){
        t2[u].mnpos=l;
        return;
    }
    int mid=(l+r)/2;
    build2(u*2,l,mid),build2(u*2+1,mid+1,r);
    pushup2(u);
}
void pushdown(int u){
    t[u*2].mn+=t[u].tag,t[u*2+1].mn+=t[u].tag;
    t[u*2].tag+=t[u].tag,t[u*2+1].tag+=t[u].tag;
    t[u].tag=0;
}
void update(int u,int l,int r,int x){
    if(l<=t[u].l&&t[u].r<=r){
        t[u].mn+=x,t[u].tag+=x;
        return;
    }
    if(!(l>t[u].r||r<t[u].l)){
        pushdown(u);
        update(u*2,l,r,x),update(u*2+1,l,r,x);
        pushup(u);
    }
}
int query(int u,int l,int r){
    if(l<=t[u].l&&t[u].r<=r){
        return t[u].mn;
    }
    if(!(l>t[u].r||r<t[u].l)){
        pushdown(u);
        return min(query(u*2,l,r),query(u*2+1,l,r));
    }
    return 1e9;
}
int calc(int u,int x){
    if(t[u].r<x||t[u].mn>1) return 1e9;
    if(t[u].l==t[u].r) return t[u].l;
    pushdown(u);
    if(x<=t[u*2].r) return min(calc(u*2,x),(t[u*2+1].mn==1?t[u*2+1].mnpos:(int)(1e9)));
    else return calc(u*2+1,x);
}
int calc2(int u,int x){
    if(t2[u].r<x||t2[u].mn>0) return 1e9;
    if(t2[u].l==t2[u].r) return t2[u].l;
    if(x<=t2[u*2].r) return min(calc2(u*2,x),(t2[u*2+1].mn==0?t2[u*2+1].mnpos:(int)(1e9)));
    else return calc2(u*2+1,x); 
}
void update2(int u,int x){
    if(t2[u].l==t2[u].r){
        t2[u].mn=1;
        return;
    }
    if(x<=t2[u*2].r) update2(u*2,x);
    else update2(u*2+1,x);
    pushup2(u);
}
int query2(int u,int l,int r){
    if(l<=t2[u].l&&t2[u].r<=r){
        return t2[u].mn;
    }
    if(!(l>t2[u].r||r<t2[u].l)){
        return min(query2(u*2,l,r),query2(u*2+1,l,r));
    }
    return 1e9;
}
void ins(int x){
    p[++tot]=x,update2(1,x);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a[i];
    }
    build(1,1,n-1),build2(1,1,n),ins(1);
    int pos=1;
    while(tot<n){
        pos=calc2(1,pos);/*the first not walked pos*/
        if(query(1,pos,pos)==3){
            int x=calc(1,pos);/*the first a=1 pos*/
            ins(x),ins(pos);
            update(1,pos,x-1,-2);
        }else ins(pos);
    }
    for(int i=1;i<=n;i++){
        cout<<p[i]<<' ';
    }
    return 0;
}