线段覆盖

Grade 0 Open Time Tuesday, 22 January 2013, 1:35 pm
Discount 0.8 Time Discount Tuesday, 22 January 2013, 1:35 pm
Allow late Yes Close Time Tuesday, 22 January 2013, 1:35 pm
Input file xdfg.in Output file xdfg.out

【问题描述】

有一根长度为 L 的白色条状物。有两种操作:

  1. 用一条长度为 T 的黑布盖住条状物的 [a, a+T] 这个区间 (0<=a, T<=L) 。
  2. 把某条黑布拿走。

输入 L 和 n 次操作,要你输出每次操作之后:

  1. 条状物上有多少个黑区间。
  2. 条状物上黑区间的总长度。

【输入格式】

输入文件第一行两个整数L(1<=L<=200000), n(1<=n<=200000)

以下有n行,第2--n+1行每行有3个整数m,a,T,m表示操作类型,1表示放入黑布,2表示拿走黑布,a,T表示黑布在L上的起始位置与长度,拿走的黑布保证是原来已经存在的.

【输出格式】

输出有n行,每行两个整数x,y,x表示L上的黑区间个数,y表示黑区间的总长度.

【输入输出样例】
 
输入:

20 4
1 5 3
1 7 2
2 5 3
1 16 3

输出:

1 3
1 4
1 2
2 5