agc003e专题

[AGC003E]Sequential operations on Sequence

Sequential operations on Sequence 题解 其实还是蛮有趣的。 首先,我们发现,我们最后保留下来的,会对我们产生意义的数组操作的长度,一定是递增的。 因为一次减少操作,相当于只给我们保留下来上次操作的一个前缀,相当于上次操作没有增长那么长。 所以我们可以先用一个单调栈维护哪些操作,这样就只剩下增加的操作了。 接下来,我们考虑我们的答案该怎么计算。 显然最开始,