带修莫队

普通的莫队只能解决没有修改的问题，那么带修改的问题怎么解决呢？带修莫队就是一种支持单点修改的莫队算法。

算法简介

还是对询问进行排序，每个询问除了左端点和右端点还要记录这次询问是在第几次修改之后（时间），以左端点所在块为第一关键字，以右端点所在块为第二关键字，以时间为第三关键字进行排序。

暴力查询时，如果当前修改数比询问的修改数少就把没修改的进行修改，反之回退。

需要注意的是，修改分为两部分：

1. 若修改的位置在当前区间内，需要更新答案（del原颜色，add修改后的颜色）。

2. 无论修改的位置是否在当前区间内，都要进行修改（以供add和del函数在以后更新答案）

时间复杂度：O(n^(5/3))

带修莫队

原文：https://www.cnblogs.com/lkx422/p/11736350.html