牛客练习赛68——A 牛牛的mex

Powered by:AB_IN 局外人

又爆0了

A 牛牛的mex

• 首先这个题挺鸡贼的。
  先看题面条件
  
  你只知道这是个长度为$n$n的序列，我当时觉得
  $n=5 ,10 \ 6 \ 5 \ 2 \ 3$n=5,10 6 5 2 3这种数据也是可以的。
  接着往下看
  
  这就代表了如果$n=5$n=5, $0 \ 1 \ 2 \ 3 \ 4$0 1 2 3 4一定在数据里。
  那么问题就变得明朗许多了

$[l,r]$[l,r]没出现的最小值$=[1,l-1]$=[1,l−1]和$[r+1,n]$[r+1,n]最小值

• 如果$l=1,r=n$l=1,r=n,说明$[0,n-1]$[0,n−1]数据都在里面，最小值只能是$n$n。
  另外单独的这两个条件$l=1,r=n$l=1,r=n，就单独特判即可。
  这是我上树AC代码，区间维护最小值即可。

#include <bits/stdc++.h>
#define rep(i,x,y) for (register int i=(x);i<=(y); i++)
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll a[maxn<<2],tr[maxn<<2];
ll n,m;

inline void pushup(ll i)
{
    tr[i] = min(tr[i<<1],tr[i<<1|1]);
}

void bulid(ll i,ll l,ll r)
{
    if(l==r){
        tr[i]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    bulid(i<<1,l,mid);
    bulid(i<<1|1,mid+1,r);
    pushup(i);
}

ll query(ll i,ll l,ll r,ll x,ll y)
{
    ll res=inf;
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y) return tr[i];
    ll mid=(l+r)>>1;
    if(x<=mid) res=min(res,query(i<<1,l,mid,x,y));
    if(y>mid)  res=min(res,query(i<<1|1,mid+1,r,x,y));
    return res;
}

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
ll l,r,q;
int main()
{
    n=read();q=read();
    rep(i,1,n)  a[i]=read();
    bulid(1,1,n);
    rep(i,1,q){
        l=read();r=read();
        if(l==1&&r==n){
            write(n);
            pc('\n');
        }
        else if(l==1){
            write(query(1, 1, n, r+1, n));
            pc('\n');
        }
        else if(r==n){
            write(query(1, 1, n, 1, l-1));
            pc('\n');
        }
        else{
            write(min(query(1, 1, n, 1, l-1),query(1, 1, n, r+1, n)));
            pc('\n');
        }
    }
    return 0;
}

• 最简单的还是正解——前缀、后缀最小值
  $b$b为前缀最小值，$c$c为后缀最小值。

#pragma GCC optimize (2)
#pragma GCC optimize (3)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define ll long long
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
ll a[N],b[N],c[N];
ll n,m,q,l,r;
namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
int main()
{
    n=read();q=read();
    rep(i,1,n)  a[i]=read();
    b[0]=c[n+1]=n;
    rep(i,1,n)  b[i]=min(b[i-1],a[i]);
    per(i,n,1)  c[i]=min(c[i+1],a[i]);
    rep(i,1,q){
        l=read();r=read();
        write(min(b[l-1],c[r+1]));
        pc('\n');
    }
    return 0;
}

完结。