time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Alyona’s mother wants to present an array of n non-negative integers to Alyona. The array should be special.
Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays. Subarray is a set of some subsequent elements of the array. The i-th subarray is described with two integers li and ri, and its elements are a[li], a[li + 1], …, a[ri].
Alyona is going to find mex for each of the chosen subarrays. Among these m mexes the girl is going to find the smallest. She wants this minimum mex to be as large as possible.
You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.
The mex of a set S is a minimum possible non-negative integer that is not in S.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105).
The next m lines contain information about the subarrays chosen by Alyona. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), that describe the subarray a[li], a[li + 1], …, a[ri].
Output
In the first line print single integer — the maximum possible minimum mex.
In the second line print n integers — the array a. All the elements in a should be between 0 and 109.
It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 109.
If there are multiple solutions, print any of them.
Examples
input
5 3
1 3
2 5
4 5
output
2
1 0 2 1 0
input
4 2
1 4
2 4
output
3
5 2 0 1
Note
The first example: the mex of the subarray (1, 3) is equal to 3, the mex of the subarray (2, 5) is equal to 3, the mex of the subarray (4, 5) is equal to 2 as well, thus the minumal mex among the subarrays chosen by Alyona is equal to 2.
【题目链接】:http://codeforces.com/contest/740/problem/C
【题解】
考虑一下所有区间；最后的答案肯定不大于所有区间里面长度最小的那个;
因为如果答案大于区间长度最小的区间li,ri;
则ri-li+1小于ans;
则li-ri这个区间是怎么样都没办法凑出ans的;
因为区间内数字最大的办法是
0 1 2 …ri-li;然后mex==ri-li+1;
所以答案肯定小于等于min(ri-li+1);
然后就开始“贪心”呗；
就假设答案是ans=min(ri-li+1);
会发现；只要按照如下的方法复制序列；就总能满足题意；
即
0 1 2 3 ..ans-1 0 1 2 ….
即以ans-1为循环节在需要满足的m个区间里面周期性地复制这个序列就可以了
如ans=3
然后m个区间把1..n都覆盖了
则在1..n假设n=7应该满足
0 1 2 0 1 2 0
这样长度为3的区间，里面最大的值都是2，则mex为2+1==3；
而长度为4的区间也是一样。总能满足最大值是2，mex为3；
看起来贪心 成功了；
然后我就交了
用线段树搞出1-n上哪些点被覆盖了；
然后再连续的段上不断复制那个1..ans-1的周期串就好了；
其他没被覆盖的点直接输出0就好;
(另解:不用搞线段树，直接在1..n上管他有没有被覆盖，直接覆盖0..ans-1的周期串。这样也是对的.挺容易想明白的);下面贴的是线段树的代码；另解的代码就更简单了；不贴了；
【完整代码】
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e5+100;
LL n,m;
bool bo[MAXN] = {0};
int color[MAXN << 2],l[MAXN],r[MAXN],a[MAXN];
void push_down(int rt)
{
if (color[rt] != -1)
{
color[rt << 1] = color[rt << 1 | 1] = color[rt];
color[rt] = -1;
}
}
void updata(int l, int r, int num,int begin, int end, int rt)
{
if (l <= begin && end <= r)
{
color[rt] = num;
return;
}
push_down(rt);
int m = (begin + end) >> 1;
if (l <= m)
updata(l, r, num, begin, m, rt << 1);
if (m < r)
updata(l, r, num, m + 1, end, rt << 1 | 1);
}
bool query(int pos,int begin,int end,int rt)
{
if (begin==end)
{
if (color[rt]==1)
return true;
else
return false;
}
push_down(rt);
int m = (begin+end)>>1;
if (pos <= m)
return query(pos,begin,m,rt<<1);
else
return query(pos,m+1,end,rt<<1|1);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
memset(color,255,sizeof(color));
cin >> n >> m;
int mi = 21e8;
for (int i = 1;i <= m;i++)
{
int li,ri;
cin >> l[i] >> r[i];
updata(l[i],r[i],1,1,n,1);
mi = min(mi,r[i]-l[i]+1);
}
for (int i = 1;i <= n;i++)
{
if (query(i,1,n,1))
bo[i] = true;
else
bo[i] =false;
}
for (int i = 1;i <= n;i++)
{
if (bo[i] == true)
{
int j = i+1;
while (j<=n && bo[j]==true)
j++;
int now = 0;
for (int k = i;k <= j-1;k++)
{
a[k] = now;
now++;
if (now >mi-1)
now = 0;
}
i = j-1;
}
}
cout << mi << endl;
for (int i = 1;i <= n;i++)
if (i==n)
printf("%d
",a[i]);
else
printf("%d ",a[i]);
return 0;
}