题意:
解法:
对于一个排列,区间[l,r]的mex等于区间外所有数的最小值.
因此我们计算min(min[1,l-1],min(r+1,n))就是答案.
预处理前缀min和后缀min即可.
Code:
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define PI pair<int, int>
const int maxm=2e6+5;
const int mod=998244353;
int n,q;
int a[maxm];
int pre[maxm];
int suf[maxm];
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n+1;i++)pre[i]=suf[i]=n;
for(int i=1;i<=n;i++){
pre[i]=min(pre[i-1],a[i]);
}
for(int i=n;i>=1;i--){
suf[i]=min(suf[i+1],a[i]);
}
while(q--){
int l,r;cin>>l>>r;
int ans=min(pre[l-1],suf[r+1]);
cout<<ans<<endl;
}
}
signed main() {
// #define MULTI_CASE
ios::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("../in.txt", "r", stdin);
freopen("../out.txt", "w", stdout);
#endif
#ifdef MULTI_CASE
int T;
cin >> T;
while (T--)
#endif
solve();
return 0;
}