专栏文章

题解：P13693 [CEOI 2025] Equal Mex

TTom17
P13693题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimziiqn
此快照首次捕获于
2025/12/01 18:06
3 个月前
此快照最后确认于
2025/12/01 18:06
3 个月前
查看原文
首先可以证明划分之后的若干区间若 mex\textrm{mex} 相同，那么其 mex\textrm{mex} 等于原区间的 mex\textrm{mex}。
证明是简单的。若现在的 mex\textrm{mex} （记作 AA）小于原区间的 mex\textrm{mex}，那么必然存在划分后至少存在一个区间包含 AA，矛盾。若大于，显然不可能，因为原区间的 mex\textrm{mex} 在区间中没有出现，所以划分后若大于，则存在一个区间包含原区间的 mex\textrm{mex}，矛盾。
记询问区间的 mex\textrm{mex} 为 mm。
先特判掉 m=1m=1 的情况，输出 r−l+1r-l+1。
贪心地去考虑，所求值就是要求，将区间划分成若干段，使得包含 11 到 m−1m-1 所有数的区间尽可能多。暴力就是从左往右扫描，贪心选择即可。
考虑优化。
第一是如何在线快速求区间 mex\textrm{mex}。
可以维护一个值域主席树，主席树维护的是当前点前缀每个值最后一次出现的位置（没有则设为 00）。查询就是在 rr 对应的主席树中找到第一个值使得其位置小于 ll，可以用线段树二分（主席树二分）来解决。单次 O(log⁡V)O(\log V)。
第二是如何快速处理询问。
可以这样做到 O(anslog⁡V)O(ans \log V)。贪心反过来也是对的。考虑从 rr 出发，查询该点主席树中 11 到 m−1m-1 的最小值，跳到该位置的前一个，直到跳到 <l<l 的位置就结束。答案就是跳跃的次数。
发现 mex\textrm{mex} 大的时候直接跳。
发现 mex\textrm{mex} 小的时候把其预处理出来，倍增去跳即可。
具体实现时，把询问按照其 mex\textrm{mex} 分类然后离线。按 mex\textrm{mex} 扫，如果小就预处理倍增数组，大就直接跳。那样空间就不用开到 O(Bnlog⁡V)O(Bn\log V) 了。取 B=nB=\sqrt n，可以做到 O(Bnlog⁡n)+O(nBlog⁡n)=O(nnlog⁡n)O(Bn\log n)+O(\frac n B \log n)=O(n\sqrt n \log n)。可以过前 55 档部分分。
我们充分发扬人类智慧。注意到它是区间 mex\textrm{mex}，真正需要倍增的不会很多个。
首先是平衡规划，可以把每个 mex\textrm{mex} 的区间总和和区间数量算出来，用时间复杂度比较一下用哪一个算法较快，动态选择一下。注意将比较函数的倍增的复杂度常数写大一些，以减少倍增的次数。
然后在暴力跳那一部分记忆化一下。就是拿一个数组记录一下当前在这个位置跳跃过没有，如果跳跃过就直接查表，会快很多。
实测最大点不到 11 秒，可以通过。代码已作防抄袭。
CPP
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mtp make_tuple
#define fi first
#define se second 

struct Seg
{
	int minn[N*G],ls[N*G],rs[N*G],c;

	#define mid ((l+r)>>1)

	void push_up(int x)
	{
		minn[x]=min(minn[ls[x]],minn[rs[x]]);
	}

	void change(int A,int l,int r,int& x,int ox,int v)
	{
		x=++c;
		if(l==r) return minn[x]=v,void();
		ls[x]=ls[ox],rs[x]=rs[ox];
		if(A<=mid) change(A,l,mid,ls[x],ls[ox],v);
		else change(A,mid+1,r,rs[x],rs[ox],v);
		push_up(x);
	}

	int query(int A,int B,int l,int r,int x)
	{
		if(A<=l&&r<=B) return minn[x];
		if(B<=mid) return query(A,B,l,mid,ls[x]);
		if(A>=mid+1) return query(A,B,mid+1,r,rs[x]);
		return min(query(A,B,l,mid,ls[x]),query(A,B,mid+1,r,rs[x]));
	}

	int query_bs(int l,int r,int x,int v)
	{
		if(l==r) return l;
		if(minn[ls[x]]<v) return query_bs(l,mid,ls[x],v);
		else return query_bs(mid+1,r,rs[x],v);
	}

	#undef mid
}S;

int n,q,pos[N];

int get_mex(int oril,int orir)
{
	return S.query_bs_(1,V,pos[orir],oril);
}

vi memq[N];
LL sumlth[N],sumcnt[N];

int arr[N],ans[N],st[N][22];

void calc1(int p)
{
	rep(i,1,n)
	{
		int now=0;
		if(p==1) now=i-1;
		else now=S.query(1,p-1,1,V,pos[i])-1;
		st[i][0]=now;
	}
	st[0][0]=-1;
	rep(j,1,20)
	{
		rep(i,0,n)
		{
			if(st[i][j-1]==-1) st[i][j]=-1;
			else st[i][j]=st[st[i][j-1]][j-1];
		}
	}
	for(auto id:memq[p])
	{
		int l=z[id].l,r=z[id].r;
		int nowans=0;
		per(j,20,0)
		{
			if(st[r][j]+1>=l)
			{
				nowans+=(1<<j);
				r=st[r][j];
			}
		}
		ans[id]=nowans;
	}
}

int tt[N],memmex[N];

void calc2(int p)
{
	for(auto id:memq[p])
	{
		int l=z[id].l,r=z[id].r;
		if(p==1)
		{
			ans[id]=r-l+1;
			continue;
		}
		int nowans=0;
		while(true)
		{
			int nex=0;
			if(tt[r]==p) nex=memmex[r];
			else
			{
				tt[r]=p;
				memmex[r]=S.query(1,p-1,1,V,pos[r]);
				nex=memmex[r];
			}
			if(nex>=l)
			{
				++nowans;
				r=nex-1;
			}
			else
			{
				break;
			}
		}
		ans[id]=nowans;
	}
}

std::vector<int> solve(int kn, std::vector<int>& v,int kq,std::vector<std::pair<int, int>>& queries)
{
    n=kn,q=kq;
	rep(i,1,n) arr[i]=v[i-1];
	rep(i,1,n)
	{
		S.change_(arr[i],1,V,pos[i],pos[i-1],i);
	}
	rep(lol,1,q)
	{
		int l,r;
		tie(l,r)=queries[lol-1];
		int mex=get_mex_(l,r);
		z[lol]=node(l,r,mex);
		memq[mex].eb(lol);
		sumlth[mex]+=r-l+1;
		++sumcnt[mex];
	}

	int nlogn=n*int(log2(n)+1);
	int logn=int(log2(n)+1);
	LL CNT=0;
	rep(p,1,V)
	{
		sumlth[p]/=p;
		if(p!=1&&1ll*sumlth[p]+n>4ll*nlogn+(LL)2ll*sumcnt[p]*22)
		{
			calc1(p);
		}
		else
		{
			calc2(p);
		}
	}
	vi vtans;
	rep(lol,1,q)
	{
		vtans.eb(ans[lol]);
	}
	return vtans;
}

评论

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

正在加载评论...