ARC222A Colorful Intervals
2026-06-24
题目大意
给定一个 n,要求你构造一个正整数序列 A 满足 m 条限制,每条限制形式为 (li,ri),要求为 Ali∼Ari 每个数字互不相同。
多组测试数据。
数据范围:1≤T≤105,1≤n≤2×105,1≤m≤2×105,∑n≤2×105,∑m≤2×105。
题解
已经没有人类了。
显然答案有一个下界 k=max(ri−li+1),考虑以下构造:1,2,3,⋯,k,1,2,3,⋯k,⋯,显然满足题目要求。
所以 k 就是答案。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
void solve() {
int n , m;
scanf("%d%d" , &n , &m);
int ans = 0;
while(m --) {
int l , r;
scanf("%d%d" , &l , &r);
ans = max(ans , r-l+1);
}
for(int i = 1 ; i <= n ; i ++)
printf("%d " , i%ans+1);
puts("");
return;
}
int main() {
int T; scanf("%d" , &T);
while(T --) solve();
return 0;
}