二维带权数颜色。
根据套路，采用莫队套二维分块，没写过去看 P7448。
一维带权数颜色谁都会，记每个颜色的上一个与其颜色相同的位置 /(pre/)，问题转化为查询区间 /([l,r]/) 中 /(pre<l/) 的数的个数。
然后转成二维数点的形式，有 /(n/) 个点 /((i,pre_i)/)，查询 /([l,r][0,l)/) 这个矩阵的和，带修。
再考虑二维，选一维度跑莫队。
剩下的就是维护 /(pre/)，然后动态二维数点，跑 /(/mathcal O(1)-/mathcal O(/sqrt n)/) 二维分块即可。
对于散块，考虑到 /(pre/) 独特的性质：除了有多个位置 /(pre_i=0/) 之外其余 /(pre/) 互不相等。于是对于 /(pre_i=0/) 的情况，写个一维分块维护，其他均摊复杂度正确。
考虑到这个莫队删除容易，增加爆炸，故使用回滚莫队。
时间复杂度 /(/mathcal O(n/sqrt n)/)，空间复杂度 /(/mathcal O(n)/)。
原创文章，作者：wure，如若转载，请注明出处：https://blog.ytso.com/268336.html