专栏文章

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

llovely_nst
P9970题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipunm1o
此快照首次捕获于
2025/12/03 18:13
3 个月前
此快照最后确认于
2025/12/03 18:13
3 个月前
查看原文

P9970 套娃

前置知识

  1. 主席树（动态开点权值线段树）
  2. set 维护 mex\text{mex}

在线区间 mex\text{mex}

考虑确定右端点后 mex\text{mex} 咋求。设 ii 出现最晚的位置记为 pip_i，若没有则为 00，权值线段树单点赋值实现；询问时，满足 0≤i≤mex0\le i\le mex 的 ii 一定有 pi≥lp_i\ge l，可以转化为 min⁡i=0mex−1pi≥l\min_{i=0}^{mex-1} p_i\ge l，权值线段树上二分求出答案。至于右端点不同的情况，主席树每次加链就行了。

极小 mex\text{mex} 区间

设 [l,r][l,r] 的 mex=x\text{mex}=x，定义满足 [l,r][l,r] 不存在另一个子区间 [L,R][L,R] 的 mex=x\text{mex}=x 的 [l,r][l,r] 为极小 x−mexx-\text{mex} 区间。
结论是极小 mex\text{mex} 区间的个数为 O(n)O(n) 级别的，简单证明我不会证。
那么如何求呢？对于 x−mexx-\text{mex} 找左边第一个 aL=xa_L=x，右边第一个 aR=xa_R=x（若没有则不做）。接下来求 [L,r][L,r] 的 y=mexy=\text{mex} 并放进 y−mexy-\text{mex} 中；求 [l,R][l,R] 的 y=mexy=\text{mex} 并放进 y−mexy-\text{mex} 中。
每次要进行去重，即只保留小区间，包含小区间的大区间删除。

答案

对于每个极小 x−mexx-\text{mex} 区间找左边第一个 aL=xa_L=x，右边第一个 aR=xa_R=x（和前面不一样，若没有则赋为边界值 0/n+10/n+1）。那么区间长度为 r−l+1∼R−L−1r-l+1\sim R-L-1 会有 mex=x\text{mex}=x 的区间。
之后用扫描线 set 动态维护 mex\text{mex} 就做完了。
注意在 mex=x\text{mex}=x 时可能会有 l1∼r1∣l2∼r2(l1≤l2≤r1≤l2)l1\sim r1|l2\sim r2(l1\le l2\le r1\le l2)，即有重区，直接扫会出问题。因此可以用 ODT 区间推平或区间去重做。

AC Code

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100000 , M = 20 * N + 5 , inf = 1e9;
int cc , siz , st[N + 5];
struct STree
{
	int idx = 0;
	int lc[M] = {0} , rc[M] = {0} , d[M] = {0};
	void push_up (int p) { d[p] = min (d[lc[p]] , d[rc[p]]); }
	void bld (int &p , int s = 1 , int t = siz)
    {
    	p = ++ idx;
		if (s == t) return ;
		int mid = s + t >> 1;
		bld (lc[p] , s , mid);
		bld (rc[p] , mid + 1 , t);
	}
	void add (int &p , int q , int ps , int c , int s = 1 , int t = siz)
	{
		p = ++ idx;
		if (s == t)
	  	{
	    	d[p] = c;
	    	return;
	  	}
		int m = s + t >> 1;
		if (ps <= m) rc[p] = rc[q] , add (lc[p] , lc[q] , ps , c , s , m);
		else lc[p] = lc[q] , add (rc[p] , rc[q] , ps , c , m + 1 , t);
		push_up (p);
	}
	int qry (int p , int w , int s = 1 , int t = siz)
	{
		if (s == t)
	  		return s - 1;
		int m = s + t >> 1;
		
		if (d[lc[p]] >= w) return qry (rc[p] , w , m + 1 , t);
		else return qry (lc[p] , w , s , m);
	}
} T;
int n , x;
vector <pair <int , int> > mex[N + 5] , ln[N + 5];
vector <int> s[N + 5] , g[N + 5];
bool cmp (pair <int , int> x , pair <int , int> y)
{
	if (x.first != y.first) return x.first > y.first;
	return x.second < y.second;
}
bool cmp2 (pair <int , int> x , pair <int , int> y)
{
	if (x.first != y.first) return x.first < y.first;
	return x.second > y.second;
}
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	T.d[0] = inf;
	cin >> n;
	siz = n + 3;
	T.bld (st[0]); 
	for (int i = 0;i <= n + 1;i ++) s[i].push_back (0);
	for (int i = 1;i <= n;i ++)
	{
		cin >> x;
		T.add (st[i] , st[i - 1] , x + 1 , i);
		if (!x) mex[1].push_back ({i , i});
		else mex[0].push_back ({i , i});
		s[x].push_back (i);
	}
	for (int i = 0;i <= n + 1;i ++) s[i].push_back (n + 1);
	for (int i = 0;i <= n;i ++)
	{
		sort (mex[i].begin () , mex[i].end () , cmp);
		vector <pair <int , int> > now;
		int mn = 1e9;
		for (auto w : mex[i])
			if (mn > w.second)
				now.push_back (w) , mn = w.second;
		reverse (now.begin () , now.end ());
		mex[i] = now;
		for (auto w : mex[i])
		{
			int l = w.first , r = w.second;
			int L = *(lower_bound (s[i].begin () , s[i].end () , l) - 1) , R = *upper_bound (s[i].begin () , s[i].end () , r);
			if (L)
			{
				int _mex = T.qry (st[r] , L);
				mex[_mex].push_back ({L , r});
			}
			if (R <= n)
			{
				int _mex = T.qry (st[R] , l);
				mex[_mex].push_back ({l , R});
			}
		}
	}
	multiset <int> S;
	for (int i = 0;i <= n + 1;i ++)
	{
		S.insert (i);
		for (auto w : mex[i])
		{
			int l = w.first , r = w.second;
			int L = *(lower_bound (s[i].begin () , s[i].end () , l) - 1) , R = *upper_bound (s[i].begin () , s[i].end () , r);
			ln[i].push_back ({r - l + 1 , R - L - 1});
		}
	}
	S.insert (n + 2);
	for (int i = 0;i <= n;i ++)
	{
		int mx = 0;
		vector <pair <int , int> > now;
		sort (ln[i].begin () , ln[i].end () , cmp2);
		for (auto w : ln[i])
			if (mx < w.second)
				mx = w.second , now.push_back (w);
		int len = now.size ();
		for (int i = 1;i < len;i ++)
			now[i].first = max (now[i].first , now[i - 1].second + 1);
		for (auto w : now)
			g[w.first].push_back (i + 1) , g[w.second + 1].push_back (-i - 1);
	}
	for (int i = 1;i <= n;i ++)
	{
		for (int w : g[i])
		{
			if (w < 0) S.insert (-w - 1);
			else S.erase (w - 1);
		}
		cout << *S.begin () << ' ';
	}
	return 0;
}

评论

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

正在加载评论...