专栏文章

题解：P11570 「chaynOI R1 T3」镍铬合金机器人

llovely_nst
P11570题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqirmx8
此快照首次捕获于
2025/12/04 05:28
3 个月前
此快照最后确认于
2025/12/04 05:28
3 个月前
查看原文

P11570 「chaynOI R1 T3」镍铬合金机器人

前言

这道我场切的，但是赛后发现题解是高贵的单 log⁡\log 做法，而我是低贱的双 log⁡\log 做法。
那就讲一下双 log⁡\log 的做法吧。

正文

首先要会求区间 mex\text{mex}。设 mxi,j=mex({ai,ai+1,…,aj})(i≤j)mx_{i,j}=\text{mex}(\{a_i,a_{i+1},\dots ,a_j\})(i\le j)，nxtxnxt_x 为 xx 后下一个 ay=axa_y=a_x 的 yy，若没有则等于 n+1n+1。那如果已经确定了 mximx_i，要转移到 mxi+1mx_{i+1} 该如何转化？那无疑就是少了个 aia_i 使 mex\text{mex} 变小，也就是原本只有一个 aia_i，现在推掉了。易得，在 i+1i+1 到 nxti−1nxt_i-1 的 mex\text{mex} 可能改变，用线段树处理最小值即可。
其次，因为 mex\text{mex} 是递增的，因此二分即可。

AC Code

CPP
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
int n , m , a[300005] , lst[300005] , nxt[300005] , mex[300005] , cnt[300005];
vector <pair <int , pair <int , int> > > q[300005];
int ans[300005] , d[2000005] , vis[2000005];

void build (int l , int r , int p)
{
	if (l == r)
	{
		d[p] = mex[l];
		return ;
	}
	int mid = l + ((r - l) >> 1);
	build (l , mid , p << 1);
	build (mid + 1 , r , p << 1 | 1);
	vis[p] = inf;
	d[p] = min (d[p << 1] , d[p << 1 | 1]);
}

int query (int l , int s , int t , int p)
{
    if (s == t)
  		return d[p];
    int m = s + ((t - s) >> 1);
    if (vis[p] != inf)
    {
		d[p << 1]       =   min (d[p << 1]       , vis[p]);
		d[p << 1 | 1]   =   min (d[p << 1 | 1]   , vis[p]);
	    vis[p << 1]     =   min (vis[p << 1]     , vis[p]);
		vis[p << 1 | 1] =   min (vis[p << 1 | 1] , vis[p]);
	    vis[p] = inf;
	}
    int sum = inf;
    if (l <= m)
		sum = min (sum , query (l , s , m , p << 1));
    if (l > m)
		sum = min (sum , query (l , m + 1 , t , p << 1 | 1));
    return sum;
}

void update (int l , int r , int c , int s , int t , int p)
{
	if (l <= s && t <= r)
  	{
    	d[p] = min (d[p] , c) , vis[p] = min (vis[p] , c);
    	return;
  	}
	int m = s + ((t - s) >> 1);
	if (s != t)
	{
		d[p << 1]       =   min (d[p << 1]       , vis[p]);
		d[p << 1 | 1]   =   min (d[p << 1 | 1]   , vis[p]);
	    vis[p << 1]     =   min (vis[p << 1]     , vis[p]);
		vis[p << 1 | 1] =   min (vis[p << 1 | 1] , vis[p]);
	    vis[p] = inf;
	}
	if (l <= m) update (l , r , c , s , m , p << 1);
	if (r > m) update (l , r , c , m + 1 , t , p << 1 | 1);
	d[p] = min (d[p << 1] , d[p << 1 | 1]);
}
int chk (int i , int x)
{
	int l = i , r = n + 1 , mid;
	while (l < r)
	{
		mid = l + r >> 1;
		if (query (mid , 1 , n , 1) < x)
			l = mid + 1;
		else
			r = mid;
	}
	return r;
}
signed main ()
{
	cin.tie (0) , cout.tie (0) , ios::sync_with_stdio (0);
	cin >> n >> m;
	int p = 0;
	for (int i = 1;i <= n;i ++)
	{
		cin >> a[i] , cnt[a[i]] ++;
		nxt[lst[a[i]]] = i , lst[a[i]] = i;
		while (cnt[p]) p ++;
		mex[i] = p;
	}
	build (1 , n , 1);
	for (int i = 1;i <= m;i ++)
	{
		int l , x , y;
		cin >> l >> x >> y;
		q[l].push_back ({i , {x , y}});
	}
	for (int i = 1;i <= n;i ++)
	{
		for (auto it : q[i])
		{
			int id = it.first , x = it.second.first , y = it.second.second;
			int p1 = chk (i , x) , p2 = chk (i , y + 1);
			ans[id] = p2 - p1;
		}
		if (nxt[i] == 0) nxt[i] = n + 1;
		update (i , nxt[i] - 1 , a[i] , 1 , n , 1);
	}
	for (int i = 1;i <= m;i ++)
		cout << ans[i] << '\n';
	return 0;
}

评论

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

正在加载评论...