题解 CF2157C Meximum Array 2
cjh20090318
·
·
题解
疑似校内选手最早通过 C。
分析
每个元素会有以下四种情况的限制：
既有 \min 限制也有 \operatorname{mex} 限制
前者需要大于等于 k，后者需要不等于 k，直接填 k+1 即可。
仅有 \min 限制
为了保证最小值能取到 k，避免受 \operatorname{mex} 限制的影响，填 k 即可。
仅有 \operatorname{mex} 限制
### 两个限制都没有
想填什么填什么，对于这些位置没有任何限制。
在保证有解的情况下以上策略可以满足所有性质。
单次时间复杂度 $O(qn)$，精细实现可以用差分做到 $O(q+n)$ 但显然没有必要。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
using namespace std;
int n,k,q;
bool a[105],b[105];
void solve(){
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<=n;i++) a[i]=b[i]=0;
for(int c,l,r;q--;){
scanf("%d%d%d",&c,&l,&r);
if(c==1) for(;l<=r;l++) a[l]=1;// min 限制位置。
else if(c==2) for(;l<=r;l++) b[l]=1;// mex 限制位置。
}
int x=0;
for(int i=1;i<=n;i++)
if(a[i]) printf("%d ",k+b[i]);
else printf("%d ",b[i]?x:k+1),x=(x+b[i])%k;// 周期性填入。
putchar('\n');
}
int main(){
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}
```