脚本宝典收集整理的这篇文章主要介绍了[Ynoi2018] 五彩斑斓的世界 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

人生第一个大分块

题意

《第二分块》

长度为 (n) 的序列 ({a})，(m) 次询问。

写一个数据结构，支持以下操作：

1. 区间 ([l,r]) 中大于 (x) 的数减去 (x)。
2. 区间 ([l,r]) 中询问 (x) 的出现次数。

(n le 10^6)，(m le 5 times 10^5),(a_i,x le 10^5 + 1)。

分析和题解

首先可以注意到的是，值域很小。操作只会让数字变小，不会变大。

一个小小的想法就是均摊。但是这个属于说起来容易，做起来不容易的那种。不像一些比较显然的题目，想到“均摊”就能直接做的。

那么我们就得先考虑怎么利用值域实现“大于 (x) 的减少 (x)”。

基于值域的减法

我们可以维护一个并查集。

具体地，(fa(i)) 表示的是序列 ({a}) 中，(a_i) 实际上变成的元素的下标。即，如果 (a_i) 因为某个减法操作被修改成另一个值，恰好是 (a_j)，那么 (fa(i) = j)。

之后维护 (rt(x)) 表示 (x) 这个值在序列 ({a}) 中第一次出现的下标。即，如果 (a_i) 这个值在 ({a}) 是第一次出现，那么 (rt(a_i) = i)。

维护一个逆于 (rt) 的映射 (val)。即，(val(rt(a_i)) = a_i)。

维护 (sz(x)) 表示 (x) 这个值的出现次数。

这样，我们可以对于所有是同一个值 (x) 的元素都直接并进 (fa(rt(x)))。

设我们把值为 (x) 的合并到值为 (y) 的上。

• 如果 (rt(y)) 不存在，(rt(y) = rt(x), val(rt(y)) = y)。
• 否则，(fa(rt(x)) = rt(y))。
• 不论如何，都计算 (sz(y) += sz(x))，并清空关于 (x) 的信息：(sz(x) = rt(x) = 0)。

To Be Continued.

脚本宝典总结

以上是脚本宝典为你收集整理的[Ynoi2018] 五彩斑斓的世界 题解全部内容，希望文章能够帮你解决[Ynoi2018] 五彩斑斓的世界 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。