专栏文章

CF2146E 题解

DDanielcdo
CF2146E题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mintp3rr
此快照首次捕获于
2025/12/02 08:11
3 个月前
此快照最后确认于
2025/12/02 08:11
3 个月前
查看原文

观察

首先需要根据题面和 mex⁡\operatorname{mex} 的性质得出一个重要结论：对于一个数组 bb，满足∑i=1n(bi>mex⁡(b))=max⁡xbi≠x∑i=1n(bi>x)\sum_{i=1}^{n} (b_i>\operatorname{mex}(b))=\max_{x}^{b_i\ne x} \sum_{i=1}^{n} (b_i>x)，因为满足 bi>xb_i>x 的位置数量越大，xx 越小，而 mex⁡\operatorname{mex} 的定义本身就是最小，所以可以这样放宽条件。

设计

得出这个结论后，我们就可以拿一个数组 cc 维护 xx 的贡献，设当前右端点 rr 约束下，xx 最后一个出现的位置为 pp，那么要使 xx 不存在于 [l,r][l,r] 中，即 l>pl>p，又要使这个区域内大于 xx 的 aia_i 数量尽量多，所以 l=p+1l=p+1，因此 cxc_x 的值就是 [p+1,r][p+1,r] 区间内大于 xx 的 a[i]a[i] 的数量，而对于 rr 的答案就是 cc 数组的最大值。

实现

考虑如何维护 cc 数组，当我们 rr 向后移动 1 次后，加入新的元素 ara_r，对于 cc 的每一个位置 ii：
ci←{ci+10≤i<ar0i=arciar<i≤nc_i\gets \begin{cases} c_i+1 & 0\le i <a_r\\0 &i=a_r \\ c_i & a_r<i\le n \end{cases}
ansr=max⁡i=0ncians_r=\max_{i=0}^{n} c_i
具体操作为区间加，单点归零，可以用线段树动态维护修改、查询。

代码

CPP
#include <iostream>
#include <cstdio>
using namespace std;
int read()
{
	char c=getchar();
	int f=1,x=0;
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
void print(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
int t,n,a[300005];
struct Segment_Tree
{
	int tr[1200005],tag[1200005];
	void build(int p,int s,int t)
	{
		tr[p]=tag[p]=0;
		if(s==t) return;
		int mid=(s+t)>>1;
		build(p<<1,s,mid);
		build(p<<1|1,mid+1,t);
	}
	void pushdown(int p)
	{
		tr[p<<1]+=tag[p];
		tr[p<<1|1]+=tag[p];
		tag[p<<1]+=tag[p];
		tag[p<<1|1]+=tag[p];
		tag[p]=0;
	}
	void update1(int p,int s,int t,int l,int r)
	{
		if(s!=t) pushdown(p);
		if(s>=l&&t<=r)
		{
			tr[p]++;
			tag[p]++;
			return;
		}
		int mid=(s+t)>>1;
		if(l<=mid) update1(p<<1,s,mid,l,r);
		if(r>mid) update1(p<<1|1,mid+1,t,l,r);
		tr[p]=max(tr[p<<1],tr[p<<1|1]);
	}
	void update2(int p,int s,int t,int x)
	{
		if(s==t)
		{
			tr[p]=0;
			return;
		}
		pushdown(p);
		int mid=(s+t)>>1;
		if(x<=mid) update2(p<<1,s,mid,x);
		else update2(p<<1|1,mid+1,t,x);
		tr[p]=max(tr[p<<1],tr[p<<1|1]);
	}
}tree;
int main()
{
	t=read();
	while(t--)
	{
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		tree.build(1,0,n);
		for(int i=1;i<=n;i++)
		{
			if(a[i]) tree.update1(1,0,n,0,a[i]-1);
			tree.update2(1,0,n,a[i]);
			print(tree.tr[1]);
			putchar(' ');
		}
		putchar('\n');
	}
	return 0;
}

评论

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

正在加载评论...