题目 | Work Group
VK Cup 2015 - Round 2 (unofficial online mirror, Div. 1 only)
B. Work Group
题目 | Box
杂项 | 本站调整知识共享协议
由于站长没有认真了解“知识共享协议”的兼容性，过去本站所有文章使用的 CC-BY-NC-SA 4.0 协议，但引用了很多 CC-BY-SA 3.0 协议的资源，实际上这种情况是违反了协议的。因为根据 ShareAlike 原则，标记有 SA 的协议必须以相同协议进行共享，因此 CC-BY-SA 协议与 CC-BY-NC-SA 协议是不可兼容的。
为了尊重知识共享协议，本站所有文章使用的知识共享协议从 CC-BY-NC-SA 4.0 调整为 CC-BY-SA 4.0，新协议的简介如下：https://creativecommons.org/licenses/by-sa/4.0/deed.zh
数据结构 | 线段树
线段树 (Segment Tree)：用来维护区间信息的数据结构。可在 $O(\log N)$ 的时间复杂度内完成单点修改、区间修改、区间查询（区间和、区间最大值、区间最小值）等操作。
数据结构 | ST 表
ST 表 (Sparse Table)：对于可重复贡献问题，可在 $O(n\log n)$ 完成初始化，在 $O(1)$ 回答每个区间查询的数据结构。但是不支持修改数据。
可重复贡献问题：对于运算 $\star$，如果 $x\star x=x$，且 $\star$ 要满足结合律，则对应的区间询问是可重复贡献问题。符合这个性质的常见运算有 $\max,\min,\gcd$.