https://www.luogu.com.cn/problem/P4314

先不考虑赋值操作，先拿个 20 分。

再考虑赋值操作对标记的影响，显然我们不能对每个状态开一个 vector 记录所有历史操作，但我们发现赋值操作可以清空前面的所有历史操作，且之后的加减操作可以和这个赋值操作合并。
因此我们只需要 (a, b) 两个数表示先加再赋值即可描述标记。
再讨论操作，对于加减操作，如果之前存在赋值，我们转化成赋值操作即可。

手写下放标记思路是比较清晰的。
https://www.luogu.com.cn/record/207893466
难点主要是分情况讨论，赋值存在和不存在的情况，如果开 LL 的话还可以用哨兵少开一个数组！

当然我们发现强行套 atc 模板双半群填空大法也是可以的！
https://www.luogu.com.cn/record/208212684

后来经过这个题的启发，我们发现直接用 checkMax 去模拟赋值可能是更好的选择?
https://www.luogu.com.cn/record/208211497

这个写法果然和模板相性更好，不仅不用分情况讨论，合并操作更简洁减少犯错的机会，
而且 checkMax 能模拟 set，反过来却不能，应用范围也更广更强大！

还有一个细节是 op 和 mapp 里是不需要 checkMax(b, a) 的，因为维护标记的过程就隐含了这层逻辑。

Posted by xiaodao
Category: 日常