题解：CF2157C Meximum Array 2

Hog_Dawa_IOI · 2025-11-24 20:05:06 · 题解

题意

给你三个正整数 n,k,q 和 q 个三元组 (c_i,l_i,r_i)。
一个数组 a_1,a_2,\dots a_n 被称为 meximum 数组，当且仅当 0 \le a_i\le 10^9，且对于每个给定的三元组 (c_i,l_i,r_i)，满足：

• 如果 c_i=1，那么 \min(a_l,a_{l+1},\dots a_r)=k；
• 否则 \operatorname{MEX}(a_l,a_{l+1},\dots a_r)=k。

注意 k 对所有条件都是相同的。
请你找出一个长度为 n 的 meximum 数组。题目保证输入数据总有解。如果有多个答案，输出任意一个。

解法

尝试挖掘 \min 和 \operatorname{MEX} 的性质。

• 如果一个数组的 \min=k，那么该区间内 0\sim k-1 的数不能出现，且 k 至少出现一次。>k 的随便。
• 如果一个数组的 \operatorname{MEX}=k，那么该区间内 0\sim k-1 的数都必须出现至少一次，且 k 不出现。>k 的随便。

我们惊讶地发现：<k 和 =k 的数，在 \min 区间和 \operatorname{MEX} 区间中的出现情况是截然相反的，而 >k 的数都可以出现。
所以对于同时被 \min 和 \operatorname{MEX} 包括的位置，只能填一个 >k 的数（具体什么数就随便了）。
没有被任何限制包括的位置也随便了。
然后只被 \min 区间包括的位置都要填 k。
最后是只被 \operatorname{MEX} 区间包括的位置。我们要把 0\sim k-1 依次填进去，那直接 0,1,\dots k-1,0,1,\dots k-1 填下去就好了。由于保证有解，因此每一个 \operatorname{MEX} 一定能包括 0 \sim k-1（当然可能有重复的，但关系不大）。

#include<stdio.h>
int t,n,k,q,typ[105],ans[105];
int op[105],l[105],r[105];
int main()
{
    scanf("%d",&t);while(t--)
    {
        scanf("%d%d%d",&n,&k,&q);
        for(int i=1;i<=n;i++) typ[i]=0,ans[i]=-1;
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d",&op[i],&l[i],&r[i]);
            for(int j=l[i];j<=r[i];j++)
            typ[j]|=op[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(typ[i]==3||typ[i]==0) ans[i]=k+1;
            else if(typ[i]==1) ans[i]=k;
        }
        for(int i=1,wh=0;i<=n;i++)
        if(ans[i]==-1) ans[i]=wh,wh=(wh+1)%k;
        for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
        putchar('\n');
    }
}