题解：P12539 [XJTUPC 2025] 结束乐队

· · 题解

作为少女乐队痴，我必须来写一写这个题解。

因为题目已有形式化题目描述，因此直接给出思路。

思路

我们可以看到，该题目包含区间查询与单点修改的要素，因此我们想到线段树。事实上，这是一道非常好的线段树板子题，可以拿来练手。

题目要点是查询在 [l,r] 上未出现的最小正整数，假如我们从正面入手，很难想到该怎样在每个子节点存下这个值，但我们应该有正难则反的思维意识，想到查询在 [1,l-1] 与 [r+1,n] 上出现的最小值也是同样的效果。这样，我们可以在每个子节点存储该区间上出现的最小值，从而方便地查询到答案。

注：在进行单点修改操作时，我们可以维护一个数组来存储每个数字所在的位置，在修改操作完成时一并修改操作的数的位置，从而方便地进行单点修改操作。

Code

#include<bits/stdc++.h>
#define Iseri namespace
#define Nina std
#define Kawaragi int
#define Momoka main
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define ll long long
#define ull unsigned long long
#define endl "\n"
const int maxn=500005;

using Iseri Nina;

inline ll read(){//快读
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

//===========================================================

struct node{
    ll l,r;
    ll mn;
}t[maxn*4];

ll n,a[maxn],l,r,m,ans=0,pos[maxn];//pos是每个数的位置

inline void pushup(ll p){//更新区间最小值
    t[p].mn=min(t[ls(p)].mn,t[rs(p)].mn);
    return;
}

inline void build(ll p,ll l,ll r){//建树
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].mn=a[l];
        return;
    }

    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
    return;
}

inline ll ask(ll p,ll dl,ll dr){//查询操作
    if(t[p].l>=dl&&t[p].r<=dr)return t[p].mn;

    ll mid=(t[p].l+t[p].r)>>1,ans=1145141919;
    if(mid>=dl)ans=min(ans,ask(ls(p),dl,dr));
    if(mid<dr)ans=min(ans,ask(rs(p),dl,dr));
    return ans;
}

inline void change(ll p,ll x,ll d){//修改操作
    if(t[p].l==x&&t[p].r==x){
        t[p].mn=d;
        return;
    }

    ll mid=(t[p].l+t[p].r)>>1;
    if(mid>=x)change(ls(p),x,d);
    else change(rs(p),x,d);
    pushup(p);
    return;
}

Kawaragi Momoka(){
    n=read();
    for(ll i=1;i<=n;i++)a[i]=read(),pos[a[i]]=i;
    build(1,1,n);

    m=read();
    while(m--){
        l=read(),r=read();
        ll x=1145141919,y=1145141919;//设极大值
        if(l>1)x=ask(1,1,l-1);//注：在l=1的情况下，不能进行左边区间查询，无意义
        if(r<n)y=ask(1,r+1,n);//同理，r=n的情况下，不能进行右边区间查询，无意义
        ans=min(x,y);
        if(ans>=n)printf("peace\n");
        else{
            printf("%lld\n",ans);
            change(1,pos[ans],ans+1);//修改操作
            change(1,pos[ans+1],ans);
            swap(pos[ans],pos[ans+1]);//更新数字所在位置
        }
    }
    return 0;
}

提交记录：这里