专栏文章

题解：P9970 [THUPC 2024 初赛] 套娃

NNetheris10+7
P9970题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miqfxp1y
此快照首次捕获于
2025/12/04 04:09
3 个月前
此快照最后确认于
2025/12/04 04:09
3 个月前
查看原文
除了一个 trick 之外都挺简单的。
首先就是这个性质：
我们设二元组 (l,r)(l,r) 表示不存在 [l,r][l,r] 的子区间（不为它本身）的 mex 为 [l,r][l,r] 的 mex，那么 (l,r)(l,r) 的个数是 2n2n 级别的。
证明可以参考 CF1870E。
于是我们可以考虑找出这些二元组。
首先 mex 为 00 和 11 的可以预处理。
然后可以发现除此之外的一个合法的二元组一定是从另一个合法二元组拓展而来的。
具体的：我们现在有一个二元组 (l,r)(l,r)，设它的 mex 为 valval，那么我们在 ll 的左边或者 rr 的右边找最近的 kk，使得 ak=vala_k=val，那么区间 [k,r][k,r] 或 [l,k][l,k] 才可能成为新的满足条件的二元组。
然后我们对于每个二元组可以求出最大的区间长度使得 mex 值依旧不变，然后差分一下，扫描线扫一遍用值域线段树维护 mex 就做完了。
CPP
#include<bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1e5+5;
int n,a[Maxn];
vector<pair<int,int> >g[Maxn];
struct Tree{
	int ls,rs,data;
}t[Maxn*50];
int root[Maxn],cnt;
void change(int&x,int y,int l,int r,int d,int p){
	x=++cnt;t[x]=t[y];if(l==r)return void(t[x].data=p);
	int mid=l+r>>1;
	if(mid>=d)change(t[x].ls,t[y].ls,l,mid,d,p);
	else change(t[x].rs,t[y].rs,mid+1,r,d,p);
	t[x].data=min(t[t[x].ls].data,t[t[x].rs].data);
}
int query(int x,int l,int r,int L){
	if(l==r)return l;
	int mid=l+r>>1;
	if(t[t[x].ls].data>=L)return query(t[x].rs,mid+1,r,L);
	return query(t[x].ls,l,mid,L);
}
inline int query(int l,int r){return query(root[r],0,n+1,l);}
vector<int>ww[Maxn];
vector<int>G[Maxn];
int cntt[Maxn];
struct seg{
	int t[Maxn<<2];
	void change(int x,int l,int r,int d,int p){
		t[x]+=p;if(l==r)return;
		int mid=l+r>>1;
		if(mid>=d)change(x<<1,l,mid,d,p);
		else change(x<<1|1,mid+1,r,d,p);
	}
	int query(int x,int l,int r){
		if(l==r)return l;
		int mid=l+r>>1;
		if(t[x<<1]==mid-l+1)return query(x<<1|1,mid+1,r);
		return query(x<<1,l,mid);
	}
}T;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();while(cnt)t[cnt--]={0,0,0};
	ww[0].clear();g[0].clear();
	for(int i=1;i<=n;i++)a[i]=read(),change(root[i],root[i-1],0,n+1,a[i],i);
	g[n+1].clear();
	for(int i=1;i<=n;i++)ww[a[i]].push_back(i);
	for(int i=1;i<=n;i++){
		if(a[i]!=0)g[0].push_back(make_pair(i,i));
		if(a[i]==0)g[1].push_back(make_pair(i,i));
	}
	for(int i=0;i<=n+1;i++){
		sort(g[i].begin(),g[i].end(),[&](pair<int,int>a,pair<int,int>b){return a.fir==b.fir?a.sec<b.sec:a.fir>b.fir;});
		vector<pair<int,int> >tmp;
		int R=1e9+7;
		for(pair<int,int>j:g[i])if(j.sec<R)tmp.push_back(j),R=j.sec;
		swap(tmp,g[i]);
		for(pair<int,int>tmp:g[i]){
			int L=lower_bound(ww[i].begin(),ww[i].end(),tmp.fir)-ww[i].begin()-1;
			int R=upper_bound(ww[i].begin(),ww[i].end(),tmp.sec)-ww[i].begin();
			if(~L)g[query(ww[i][L],tmp.sec)].push_back(make_pair(ww[i][L],tmp.sec)),L=ww[i][L]+1;
			else L=1;
			if(R<ww[i].size())g[query(tmp.fir,ww[i][R])].push_back(make_pair(tmp.fir,ww[i][R])),R=ww[i][R]-1;
			else R=n;
			G[tmp.sec-tmp.fir+1].push_back(i+1);
			G[R-L+2].push_back(-i-1);
//			printf("fewfew %d %d %d\n",tmp.sec-tmp.fir+1,R-L+1,i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j:G[i]){
			if(j>0){
				j--;
				if(!cntt[j]++)T.change(1,0,n+1,j,1);
			}else{
				j=-j;
				j--;
				if(!--cntt[j])T.change(1,0,n+1,j,-1);
			}
		}
		printf("%d ",T.query(1,0,n+1));
	}
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...