提高组T1 个人题解

首先考虑暴力：枚举所有的 $(x,y)$，同时包含 $x,y$ 的区间mex必然不变，因此我们只需考虑仅含其中一个的区间。

设 $lm_i$ 为 $[1,i]$ 的mex，$rm_i$ 为 $[i,n]$ 的mex，这两个数组可以通过正逆序枚举 $O(n)$ 得出。那么简单推导可知成立的充要条件为：

$rm_{i+1} \neq a_i,lm_{j-1} \neq a_j,lm_{j-1}<a_i,rm_{i+1}<a_j$。

其中前两个条件只与一个量有关，可以 $O(n)$ 预处理打tag标记（即不满足的直接不考虑）。对于第三个条件，不难注意到一旦 $lm_k \ge a_j$，则对于所有的 $l \ge k$ 都有 $lm_l \ge a_j$，这时 $k-1$ 就是对于这个数能够满足要求的极限位置。因此我们可以预处理出数组 $lim_i$ 表示每个数的极限位置（方法是桶排记录 $a_i$ 下标后双指针处理）。对于 $rm$ 同理。处理完后，对于每个 $a_i$ 只有 $[i+1,lim_i]$ 这段区间的点可能满足条件（即与之形成稳定化子）。

接着考虑最后一个条件。不难发现我们要求的是 $j\in[i+1,lim_i]$ 中满足 $a_j>rm_{i+1}$ 的个数，我们可以用值域树状数组记录每个合法的 $a_i$，扫描线处理。注意这只能统计到半边的答案，需要倒序再扫描线一遍，这时我们需要以最后一个条件为基础，将第三个条件扫描线。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x) & (-x)
using namespace std;

const int N = 1e6+10;
int n,m,ax[N];
int buc[N];
int lm[N],rm[N];
bool vis[N];
int c[N];
int res[N];
int lim[N];
bool tag[N]; 
int ulti[N];

inline void add(int x,int v){
	while(x<=n){
		c[x] += v;
		x += lowbit(x);
	}
}
inline int query(int x){
	int res = 0;
	while(x){
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}
struct node{
	int pos,cval,t,id;
}no[N];
inline bool cmp(node x,node y){
	return x.pos<y.pos;
}
inline bool cmp2(node x,node y){
	return x.pos>y.pos;
}

inline void deal(int a[],int mode){
	memset(buc,0,sizeof buc);
	memset(vis,0,sizeof vis);
	memset(lm,0,sizeof lm);
	memset(rm,0,sizeof rm);
	memset(res,0,sizeof res);
	memset(lim,0,sizeof lim);
	memset(c,0,sizeof c);
	memset(tag,0,sizeof tag);
	
	if(mode==0){
		for(int i=1;i<=n;i++){
			add(i,a[i]);
			buc[a[i]] = i;
		}
		int now = 1;
		for(int i=1;i<=n;i++){
			vis[a[i]] = 1;
			while(vis[now]) ++now;
			lm[i] = now;
		}
		memset(vis,0,sizeof vis);
		now = 1;
		for(int i=n;i;i--){
			vis[a[i]] = 1;
			while(vis[now]) ++now;
			rm[i] = now;
		}
	
		for(int i=1;i<=n;i++){
			if(lm[i]!=lm[i-1]){
				for(int j=lm[i-1];j<lm[i];j++){
					lim[buc[j]] = i;
				}
			}
		}
		
		int idx = 0;
		for(int i=1;i<=n;i++){
			if(lm[i-1]==a[i]) tag[i] = 1;
		}
		for(int i=1;i<=n;i++){
			if(rm[i+1]==a[i] || lim[i]==i){
				continue;
			}
			no[++idx] = {i,rm[i+1],-1,i};
			no[++idx] = {lim[i],rm[i+1],1,i};
		}
		sort(no+1,no+idx+1,cmp);
		int p = 0,zs = 0;
		for(int i=1;i<=idx;i++){
			while(p<no[i].pos){
				++p;
				if(!tag[p]) add(a[p],1);
				else zs++;
			}
			res[no[i].id] += no[i].t*(p-zs-query(no[i].cval));
		}	
	}
	else{
		for(int i=1;i<=n;i++){
			add(i,a[i]);
			buc[a[i]] = i;
		}
		int now = 1;
		for(int i=1;i<=n;i++){
			vis[a[i]] = 1;
			while(vis[now]) ++now;
			lm[i] = now;
		}
		memset(vis,0,sizeof vis);
		now = 1;
		for(int i=n;i;i--){
			vis[a[i]] = 1;
			while(vis[now]) ++now;
			rm[i] = now;
		}
	
		for(int i=n;i>=1;i--){
			if(rm[i]!=rm[i+1]){
				for(int j=rm[i+1];j<rm[i];j++){
					lim[buc[j]] = i;
				}
			}
		}
		
		int idx = 0;
		for(int i=1;i<=n;i++){
			if(rm[i+1]==a[i]) tag[i] = 1;
		}
		for(int i=1;i<=n;i++){
			if(lm[i-1]==a[i] || lim[i]==i){
				continue;
			}
			no[++idx] = {i,lm[i-1],-1,i};
			no[++idx] = {lim[i],lm[i-1],1,i};
		}
		sort(no+1,no+idx+1,cmp2);
		int p = n+1,zs = 0;
		for(int i=1;i<=idx;i++){
			while(p>no[i].pos){
				--p;
				if(!tag[p]) add(a[p],1);
				else zs++;
			}
			res[no[i].id] += no[i].t*(n-p-zs-query(no[i].cval));
		}
	}
	
	for(int i=1;i<=n;i++){
		ulti[i] += res[i];
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ax[i];
	}
	deal(ax,0);
	deal(ax,1);
	
	for(int i=1;i<=n;i++){
		cout<<ulti[i]<<' ';
	}
	
	return 0;
}