#P17963. Watering System
Watering System
Watering System
有 个花盆排成一行,编号为 到 。可以在这行花盆上放置浇水机。每台浇水机有一个位置 (),以及向左或向右的方向。
所有浇水机使用相同的浇水范围 ,其中 是非负整数:
- 位于 、方向向右的机器,浇灌编号在 内的花盆。
- 位于 、方向向左的机器,浇灌编号在 内的花盆。
只有编号在 到 之间的花盆实际存在。
初始没有任何浇水机。按时间顺序处理 次操作:
- 操作 “1 d x”:在位置 新增一台机器。 表示向左, 表示向右。同一位置允许有多台机器,机器不会被删除。
- 操作 “2 l r”:对于当前所有机器,求一个最小的非负整数 ,使区间 内每个花盆都至少被一台机器浇灌。区间外的机器也可以浇灌区间内的花盆。 若无论 多大都不能覆盖全部目标花盆,输出 。
每次询问独立选择范围 ,不会改变机器的位置和方向。
输入格式
第一行两个整数 ()。
接下来 行,每行描述一次操作:
- “1 d x”,其中 ,;
- “2 l r”,其中 。
输出格式
对于每次第二类操作,输出一行一个整数:所需的最小 ;若不存在则输出 。
样例 1
输入
10 11
1 0 6
2 5 8
1 1 3
2 9 10
2 3 9
1 1 8
2 1 9
2 1 8
1 0 4
2 3 7
2 2 9
输出
-1
7
6
5
5
4
4