MX 基础赛 D 题讲解
D. 求和（mex）
link
考虑每个 \(i(0 \le i \le n)\) 成为 mex 的次数。
此时我们需要满足在 mex 为 \(i\) 的序列中 \([1,i-1]\) 都出现一次且 \(i\) 未出现。
我们假设 \([0,i-1]\) 的位置的最小值为 \(l\)，最大值为 \(r\)。
需要考虑 \(i\) 值所处的位置，记为 \(w_i\)。
- \(l\le w_i \le r\)
不难发现此种情况下 \(i\) 不可能成为任何一个序列的 mex，因为不存在任何一个子序列满足 \([1,i-1]\) 都出现一次且 \(i\) 未出现。
- \(w_i < l\)
分别考虑 \([1,i]\) 序列的左右端点所有可能的情况，左端点的可能数为 \(l-w_i\)（即左端点为 \([w_i+1,l]\) 中的任意一点），右端点的可能数为 \(n-r+1\)（即右端点为 \([r,n]\) 中的任意一点）。
则此种情况下的答案为 \((l-w_i)\times(n-r+1)\)。
- \(w_i > r\)
同理，答案为 \(l\times(w_i-r)\)。
Example：\(5,2,4,1,0,6,3,7\)
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug puts("#CheZiHe929")
#define Time std::cout<<1.0*clock()/CLOCKS_PER_SEC<<'s'<<endl;
#define Memory std::cout<<abs(&mst - &men)/1024.0/1024<<"MB"<<endl;
const int MAXN=1e6+5;
inline int read(){int 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;}
inline void print(int x){char st[105];int top=0;if(x==0)putchar('0');if(x<0)putchar('-');while(x){if(x>0)st[++top]=x%10+48;else st[++top]=-(x%10)+48;x/=10;}while(top)putchar(st[top--]);}
inline void println(int x){print(x);putchar('\n');}
inline void printsp(int x){print(x);putchar(' ');}
inline void put(int x,int i,int n){i==n?println(x):printsp(x);}
inline void IOS(){std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);}
bool mst;
int n,a[MAXN],w[MAXN];
bool men;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
w[a[i]]=i;
}
int l=w[0],r=w[0],ans=0;//0 对答案无贡献，直接从 1 开始考虑
for(int i=1;i<=n-1;i++){
if(w[i]>=l&&w[i]<=r)continue;
else if(w[i]<l)ans+=(l-w[i])*(n-r+1)*i;
else ans+=l*(w[i]-r)*i;
l=std::min(l,w[i]);
r=std::max(r,w[i]);
}
ans+=n;
println(ans);
return 0;
}