题解：P10392 [蓝桥杯 2024 省 A] 封印宝石

· · 题解

既然是字典序最大那么一定会让能选的中最大的放在最前面。

考虑现在应该放第 i 个，由于体力、位置限制，能选的区间是 i 到 i+k。

但是相邻盒子不能存放魔力值相同的宝石，这说明不能仅仅只考虑最大值，因为可能会冲突。所以还要同时考虑不等于最大值的值中剩下的最大值，也叫严格次大值。显然，两者最多只会有一个会与之前的魔力冲突。

注意，为了节省体力，有多个相同的最大值或次大值时，应当取最前面可以取的。

取完后，这个值就应当删去，一种方法是将其修改为 -1。

至此，只要有一个能维护区间查询最大值和严格次大值以及单点修改的数据结构即可，这里采用线段树。

线段树要存值和索引，所以在编写代码的时候可以写一个合并函数：

bool cmp(PII x,PII y){return x.fi==y.fi?x.se<y.se:x.fi>y.fi;}
pair<PII,PII> GetMax(PII a,PII b,PII c,PII d){
    PII r1={-1,-1},r2={-1,-1};
    vector<PII>vp{a,b,c,d};
    sort(vp.begin(),vp.end(),cmp);
    r1=vp[0];if(vp[1].fi!=r1.fi) r2=vp[1];
    else if(vp[2].fi!=r1.fi) r2=vp[2];
    else if(vp[3].fi!=r1.fi) r2=vp[3];
    return {r1,r2};
}

一定要注意是严格次大值。

剩下就是简单的代码了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define PII pair<int,int>
#define fi first
#define se second
#define ls (p<<1)
#define rs ((p<<1)|1)
const int N=1e5+5;
int n,k,Ans[N],a[N];PII mx[N<<2],mx2[N<<2];
bool cmp(PII x,PII y){return x.fi==y.fi?x.se<y.se:x.fi>y.fi;}
pair<PII,PII> GetMax(PII a,PII b,PII c,PII d){
    PII r1={-1,-1},r2={-1,-1};
    vector<PII>vp{a,b,c,d};
    sort(vp.begin(),vp.end(),cmp);
    r1=vp[0];if(vp[1].fi!=r1.fi) r2=vp[1];
    else if(vp[2].fi!=r1.fi) r2=vp[2];
    else if(vp[3].fi!=r1.fi) r2=vp[3];
    return {r1,r2};
}void pushup(int p){
    auto t=GetMax(mx[ls],mx[rs],mx2[ls],mx2[rs]);
    mx[p]=t.fi,mx2[p]=t.se;
}void build(int p,int l,int r){
    if(l==r){mx[p]={a[l],l},mx2[p]={-1,-1};return;}int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);pushup(p);
}PII q1,q2;
void query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        auto t=GetMax(q1,mx[p],q2,mx2[p]);
        q1=t.fi,q2=t.se;return;
    }int mid=(l+r)>>1;
    if(L<=mid) query(ls,l,mid,L,R);
    if(mid<R) query(rs,mid+1,r,L,R);
}void ask(int L,int R){q1=q2={-1,-1};query(1,1,n,L,R);}
void modify(int p,int l,int r,int K,int C){
    if(l==r){mx[p]={C,K},mx2[p]={-1,-1};return;}
    int mid=(l+r)>>1;if(K<=mid) modify(ls,l,mid,K,C);
    if(mid<K) modify(rs,mid+1,r,K,C);pushup(p);
}signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;
    cin>>n>>k;For(i,1,n)cin>>a[i];build(1,1,n);
    memset(Ans,-1,sizeof(Ans));
    For(i,1,n){
        ask(i,min(i+k,n));
        if(q1.fi==Ans[i-1]){
            if(q2.fi==-1) continue;
            Ans[i]=q2.fi;
            modify(1,1,n,q2.se,-1);
            k-=q2.se-i;
        }else if(q1.fi!=-1){
            Ans[i]=q1.fi;
            modify(1,1,n,q1.se,-1);
            k-=q1.se-i;
        }
    }For(i,1,n) cout<<Ans[i]<<' ';cout<<endl;
    return 0;
}