一、法一
将所有的询问挂在序列上,按操作进行区间减,小于等于零就取出这个询问,答案就是正在进行的这个操作。
e.g.
1 1 5 3
2 3 2
2 3 4
1 3 5 4
2 5 6
start:
operator 1:
发现有询问小于等于 0,则这些询问的答案就是 opeartor 1
operator 2:
发现有询问小于等于 0,则这些询问的答案就是 operator 2
但是注意,第二个询问在序列中的编号小于第二个操作在序列中的编号,所以第二个询问的答案为 0.
二、法二
考虑每个位置有哪些操作会影响到,然后二分第一个前缀操作和等于等于 h 的操作,这个操作就是答案。
e.g.
1 1 3 3
2 3 2
2 3 4
1 3 5 4
2 5 6
position 1:
操作 1 的左端点等于 1,说明这个操作会一直影响,将他加入线段树。
position 2:
position 3:
操作 2 的左端点等于 3,说明这个操作会一直影响,将他加入线段树。
position 4:
操作 1 的右端点等于 3,说明这个操作的影响取消,将他踢出线段树。
position 5: