P2460清理花瓶 | |
|
问题描述
Nicole是大家心中的女神,她每天都会收到很多束男生们送的鲜花。她有N个花瓶,编号0到N-1.
每天她都会试着把收到的花束放到花瓶里,一个花瓶只能装一束花。她总是随机地选择一个花瓶A,如果该花瓶是空的,她就放一束花在里面,否则她会跳过这个花瓶。接着她会试着往A+1,A+2,...,N-1号花瓶里面放花,直到没有花了或者是第N-1号花瓶都被讨论了。然后她会扔掉剩下的花。
有时Nicole也会去清理花瓶,因为花瓶太多了,所以她每次都随机选择一段花瓶清理。比如编号A到编号B这一段花瓶,她会把里面的花全都扔掉。
输入格式
第一行,两个整数N和M,表示花瓶的个数和操作的次数
接下来M行,每行三个整数K,A,B。
若K=1,表示今天Nicole收到了B束花,她打算从第A号花瓶开始放花。
若K=2,表示今天Nicole要清理花瓶,她打算清理掉从第A号到第B号花瓶里的花(A <= B)。
输出格式
对于每次操作,输出一行结果:
若K=1,输出Nicole放花的起止花瓶的编号。若一束花也放不进去,输出 “Can not put any one.”
若k=2,输出Nicole清理掉的花的数目。
样例输入
输入样例1
10 5
1 3 5
2 4 5
1 1 8
2 3 6
1 8 8
输入样例2
10 6
1 2 5
2 3 4
1 0 8
2 2 5
1 4 4
1 2 3
样例输出
输出样例1
3 7
2
1 9
4
Can not put any one.
输出样例2
2 6
2
0 9
4
4 5
2 3
提示
1 < N < 50001
1 < M < 50001
来源 改编自 multi 2013 contest 2 4614