T1

什么寄吧

这个Y有什么存在的意义吗

T2

？真的是我想的那样吗

反正最短路都唯一了，那就先跑一遍dij

然后对终点的所有出边判断一遍？

手玩样例也没问题啊？

难道是我想假了？

T3

容易想到枚举开头元素，二分其长度

问题就变成了“我如何判断能不能取到这些数”

变成狗构造了（

首先当数的个数大于 $n+1$ 时一定无解，当不包含起始位置时当大于 $n$ 一定无解

容易发现它的逻辑其实是这样的：牺牲一边的数从而取到另一边的数

所以从中间开始拓展一定最优

草了好像没什么变化

check咋弄都是 $O(n)$ 的

其实就是说每个黑格子都得匹配一个上方的白格子嘛

欸那是不是就是说对于每个黑格子，都满足他顶上的黑格子数小于另一侧的白格子数

设每个格子当前值为其顶上的白-黑，那么应时刻保持其大于等于0

我们发现其实把一个格子从白变成黑的过程其实就会将其下方所有位置减去1

而我们又知道初始时这是一个排列

所以双指针+线段树维护即可

牛皮