[线段树套单调栈] 2019-2020 ICPC Asia Hong Kong Regional Contest H.[Hold the Line]

线段树套单调栈 2019-2020 ICPC Asia Hong Kong Regional Contest H.Hold the Line 题目大意

你已经建造了一条由编号从到的战壕组成的防线，每条战壕最初都是空的。士兵们正在等待你的命令，每个士兵都有一个喜欢的射击高度。

随着战斗的进行，以下两个事件可能会发生。

• 一个拥有首选射击高度的士兵被派去驻守一个空的战壕。
• 一个有高度的敌人被发现，只有驻守在编号在和之间的战壕里的士兵可以射杀这个敌人。为了提高命中率，从而节省子弹，有必要选择一个首选射击高度尽可能接近敌人高度的士兵来射击敌人。你需要知道所选士兵的首选射击高度和敌人的高度之间的差异。

题目思路

非常妙的思路

分别将修改操作和询问操作离线，然后分别按照右端点排序。

然后以高度 h h h为下标建立权值线段树，然后将“最接近”转化为两次线段树上二分：求左侧最右和右侧最左，然后取差值最小值即可。

考虑如何检查合法性：由于在权值线段树上丢失了区间信息，因此二分时要检查合法性：我们对每个节点记录两个值：位置 x x x和时间戳 i d id id。

那么对于任意两个节点状态，当时间戳 i d 1 > i d 2 id_1>id_2 id1​>id2​且 x 1 < x 2 x_1 < x_2 x1​ = x l >= x l>=x且 i d ′ < i d id' < id id′= INF) res = min(res, queryl(rson, L, R, val, pos)); return res; } int queryr(int rt, int l ,int r, int L, int R, int val, int pos){ if(l > R || r = L && r > 1, res = -1; if(res