\(\color{purple}\text{P6007 [USACO20JAN]Springboards G}\)
题意
你从 \((0,0)\) 出发，到达 \((n,n)\) ，每次只能向上或向右走，有 \(m\) 个传送门，将你传送到传送门起点右上方的一个终点。求最少走路次数。
解法
我们不走传送门的时候答案就是 \(2n\) ，走了一个传送门从 \((sx,sy)\) 到 \((ex,ey)\) 后，答案就变成 \(2n-[(ex-sx)+(ey-sy)]\)。
我们把每个传送门看做一个点，把终点和起点的曼哈顿距离看作点权，答案就是 \(2n-max(\sum 经过的传送门点权)\)。
设 \(f[i]\) 表示到达第 \(i\) 个传送门时的点权最大值，状态转移方程： \(f[i]=max(f[i],f[j]+val[i]),ex[j]<=sx[i],ey[j]<=sy[i]\) 。
两维的限制条件，显然可以用树状数组维护 \(y\) 的值，我们需要保证更新 \(i\) 时，全部且仅有 \(ex[j]<=sx[i]\) 的点 \(j\) 被扔入树状数组。
我的第一思路是双指针，用 \(i\) 表示更新到第几个值，用 \(j\) 表示扔进树状数组的值到了第几个，但普通的双指针是不行的，因为 \(ex\) 和 \(sx\) 不一定同时单调递增。
但是：