A题解¶

对于每一个入栈的元素都有其必须死线和必须存活线，即假设操作有下标，设-操作的位置为在操作后面，则必定在之内。

除此之位重要特性为为括号序列类似的结构，即为\(+x,+y,-y,-x\)，即先出现的\(x\)的-号必定在后出现的\(y\)的嵌套外（即+前或-后

假设现在该处理+ x，处理此时的栈内元素:

由于不能再有\(x\)，如果有\(x\)，则不断弹栈直到\(x\)的数变为0（这个和F一样）
由于要满足括号序列结构，此时栈中的元素都存活，所以不断弹栈，直到开头的死的位置大于\(x\)的存活线，此时把\(x\)压入，由于他们的-的位置又必定顺序，所以把\(x\)死线的时间更新为\(min(D[x],D[栈头])\)。（这个顺序又保证了弹到头后栈里面死的位置都大于存活线。

现在思考第二个问题：弹出去的时候会不会导致一些误弹？

对于第一个，不会，因为这个肯定是要弹到终止位置的死线，又由于顺序和每一个都是一个死线，所以栈头的几个死线都一致，既然是这个的死线，那活线肯定也满足（这也论证了我们记录的死线在这种弹出中实际上就是真实死的线）。（更直接的方法：每一次都弹出\(R_i\)的元素）

对于第二个，也不会，首先死线肯定满足（要不然已经被弹出去了），考虑活线，我们最终弹到的元素都是死线小于下一个元素存活线的东西，不管在任何方案中这种元素一定都要在进入前弹出去，故如果不行就没有合法元素。

考虑一下dirty work：如何搞定\([L_i,R_i]\)?

\(L_i\)来自于最近的T x,\(R_i\)来源于最近的同\(x\)和F x

正序维护map，保存最后的\(x\)的位置，然后每次依次更新即可。

L题解¶

对于tire插入然后利用单调性更新了话会T

考虑深度对应值的区间，考虑直到\(t[i]\)存在的地方