题解：P9474 [yLOI2022] 长安幻世绘

Ptzyc · 2026-06-22 10:36:10 · 题解

解法一

考虑二分答案，这样可以考虑当 i 为最小值时极差为 x 的最长长度，考虑枚举每一位并贪心的选择点，这样可以获得 76 pts。

考虑优化贪心选点的步骤，发现把 a_i 排序后可以通过双指针确定合法的点，考虑用线段树处理答案。

具体的，记录区间长度、答案、左边的连续的 1 的个数、右边的连续的 1 的个数，查询时查询根节点的答案即可，push_up 稍微修改一下即可，复杂度是 O(n \log ^2 n)。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,m,a[N];
pll b[N];
struct info {
    ll lmx,rmx,len,cnt;
};
inline info operator + (info a,info b) {
    info c;
    c.len=a.len+b.len;
    c.lmx=a.lmx;
    if (a.lmx==a.len) {
        c.lmx+=b.lmx;
    }
    c.rmx=b.rmx;
    if (b.rmx==b.len) {
        c.rmx+=a.rmx;
    }
    c.cnt=a.cnt+b.cnt-(a.rmx+1)/2-(b.lmx+1)/2+(a.rmx+b.lmx+1)/2;
    return c;
}
struct Segtree {
    info t[N<<2];
    inline void push_up (ll pos) {
        t[pos]=t[pos<<1]+t[pos<<1|1];
    }
    void build (ll pos,ll l,ll r) {
        if (l==r) {
            t[pos]={0,0,1,0};
            return ;
        }
        ll mid=(l+r)>>1;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        push_up(pos);
    }
    void add (ll pos,ll l,ll r,ll x,ll val) {
        if (l==r) {
            t[pos]={val,val,1,val};
            return ;
        }
        ll mid=(l+r)>>1;
        if (x<=mid) {
            add(pos<<1,l,mid,x,val);
        }
        else {
            add(pos<<1|1,mid+1,r,x,val);
        }
        push_up(pos);
    }
} tr;
inline bool ck (ll x) {
    ll lt=1;
    tr.build(1,1,n);
    for (ll i=1;i<=n;i++) {
        while (lt<=n&&b[lt].first<=b[i].first+x) {
            tr.add(1,1,n,b[lt].second,1);
            lt++;
        }
        if (tr.t[1].cnt>=m) {
            return true;
        }
        tr.add(1,1,n,b[i].second,0);
    }
    return false;
}
inline void solve () {
    n=read(),m=read();
    ll mx=0,mn=inf;
    for (ll i=1;i<=n;i++) {
        a[i]=read();
        b[i]={a[i],i};
        mx=max(mx,a[i]);
        mn=min(mn,a[i]);
    }
    sort(b+1,b+1+n);
    ll l=0,r=mx-mn,cnt=0;
    while (l<=r) {
        ll mid=(l+r)>>1;
        if (ck(mid)) {
            r=mid-1;
            cnt=mid;
        }
        else {
            l=mid+1;
        }
    }
    print(cnt);
}
int main () {
    // freopen("lanterns.in","r",stdin);
    // freopen("lanterns.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}

解法二

考虑优掉二分，发现如果说确定了当 a_i 作为最小点的极差最小值，这些点出现在 a_{i + 1}（当然这个 a 数组是排过序的）一定是更优的，所以考虑通过双指针枚举当 a_i 要满足条件时最大值最小是多少，这个还是用刚才的线段树实现即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,m,a[N];
pll b[N];
struct info {
    ll lmx,rmx,len,cnt;
};
inline info operator + (info a,info b) {
    info c;
    c.len=a.len+b.len;
    c.lmx=a.lmx;
    if (a.lmx==a.len) {
        c.lmx+=b.lmx;
    }
    c.rmx=b.rmx;
    if (b.rmx==b.len) {
        c.rmx+=a.rmx;
    }
    c.cnt=a.cnt+b.cnt-(a.rmx+1)/2-(b.lmx+1)/2+(a.rmx+b.lmx+1)/2;
    return c;
}
struct Segtree {
    info t[N<<2];
    inline void push_up (ll pos) {
        t[pos]=t[pos<<1]+t[pos<<1|1];
    }
    void build (ll pos,ll l,ll r) {
        if (l==r) {
            t[pos]={0,0,1,0};
            return ;
        }
        ll mid=(l+r)>>1;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        push_up(pos);
    }
    void add (ll pos,ll l,ll r,ll x,ll val) {
        if (l==r) {
            t[pos]={val,val,1,val};
            return ;
        }
        ll mid=(l+r)>>1;
        if (x<=mid) {
            add(pos<<1,l,mid,x,val);
        }
        else {
            add(pos<<1|1,mid+1,r,x,val);
        }
        push_up(pos);
    }
    inline ll query () {
        return t[1].cnt;
    }
} tr;
inline void solve () {
    n=read(),m=read();
    ll mx=0,mn=inf;
    for (ll i=1;i<=n;i++) {
        a[i]=read();
        b[i]={a[i],i};
        mx=max(mx,a[i]);
        mn=min(mn,a[i]);
    }
    sort(b+1,b+1+n);
    ll lt=1,ans=inf;
    tr.build(1,1,n);
    for (ll i=1;i<=n;i++) {
        while (lt<=n&&tr.query()<m) {
            tr.add(1,1,n,b[lt].second,1);
            lt++;
        }
        if (tr.query()>=m) {
            ans=min(ans,b[lt-1].first-b[i].first);
        }
        tr.add(1,1,n,b[i].second,0);
    }
    print(ans);
}
int main () {
    // freopen("lanterns.in","r",stdin);
    // freopen("lanterns.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}