题目链接 区间取反与区间数一 题目描述 给定一个长度为  的 01 字符串，你需要实现一个数据结构来支持以下两种操作：  区间取反：将区间  内的所有字符进行取反操作（0 变为 1，1 变为 0）。 区间数一：查询区间  内值为 1 的字符的个数。  输入:  第一行包含两个整数  和 ，分别表示 01 串的长度和操作的次数。 第二行是一个长度为  的 01 字符串。 接下来  行，每行描述一个操作。格式为 1 l r 或 2 l r。  输出:  对于每个查询操作，输出一行，表示对应区间中 1 的个数。  解题思路 本题是典型的数据结构问题，涉及区间修改和区间查询，非常适合使用线段树来解决。...

题目链接 区间增量与单点求值 题目描述 给定一个长度为  的数组，需要支持两种操作：  区间增量：将区间  内的所有元素加上一个值 。 单点求值：查询下标为  的元素的值。  解题思路 这是一个经典的数据结构问题，要求我们实现“区间更新”和“单点查询”。解决此类问题的标准方法之一是使用 差分数组 配合 树状数组 (Fenwick Tree)。   差分数组   首先，我们引入 差分 的思想。对于原数组 ，我们构建一个差分数组 ，使得：   (对于 )   从这个定义可以看出，原数组  的任意一项  都可以表示为差分数组  的一个前缀和：    这样，对  的单点查询就转化为了对  的区间和查询...

题目链接 单点修改与区间非平凡异或和 题目描述 给定一个长度为  的数组 ，你需要实现一个数据结构来支持以下两种操作：  单点修改：将下标为  的元素  修改为 。 区间非平凡异或和查询：查询区间  内所有连续子序列的异或和的异或和。 形式化地，查询  的值。  输入:  第一行包含两个整数  和 ，分别表示数组的长度和操作的次数。 第二行包含  个整数，表示数组的初始元素。 接下来  行，每行描述一个操作。格式为 1 x k 或 2 l r。  输出:  对于每个查询操作，输出一行，表示对应的查询结果。  解题思路 这道题的难点在于理解和简化“区间非平凡异或和”的查询。 1. 简化查询表达式...

题目链接 区间取反与单点求值 题目描述 给定一个长度为  的 01 字符串，我们需要实现一个数据结构来支持以下两种操作：  区间取反：将区间  内的所有字符进行取反操作（0 变为 1，1 变为 0）。 单点查询：查询下标为  的字符的值。  输入:  第一行包含两个整数  和 ，分别表示 01 串的长度和操作的次数。 第二行是一个长度为  的 01 字符串。 接下来  行，每行描述一个操作。格式为 1 l r 或 2 x。  输出:  对于每个查询操作，输出一行，表示对应下标的字符值。  解题思路 本题要求我们维护一个可以进行区间修改和单点查询的数据结构。对于这类问题，一个非常有效的方法是使用...

题目链接 【模板】动态区间和Ⅰ ‖ 单点修改 + 区间查询 题目描述 给定一个长度为  的数组，我们需要实现一个数据结构来支持以下两种操作：  单点修改：将第  个位置的元素增加 。 区间查询：查询区间  内所有元素的和。  输入:  第一行包含两个整数  和 ，分别表示数组的长度和操作的次数。 第二行包含  个整数，表示数组的初始元素。 接下来  行，每行描述一个操作。格式为 1 x k 或 2 l r。  输出:  对于每个查询操作，输出一行，表示对应区间的元素和。  解题思路 本题是典型的数据结构问题，要求在支持单点修改的同时，能够快速查询区间和。树状数组（Fenwick Tree）是解...

题目链接 PEEK72 区间增量与区间前驱 题目描述 给定一个长度为  的数组 ，你需要构建一个数据结构来支持以下两种操作共  次：  区间增量：给定区间  和一个整数 ，将该区间中的所有元素  修改为 。 区间前驱：给定区间  和一个整数 ，查询该区间中所有小于  的元素里的最大值。如果不存在这样的元素，则返回 -1。  数据范围：, 。 解题思路 本题涉及区间修改和一种特殊的区间查询（前驱查询）。标准的线段树可以轻松处理区间增量（通过懒标记），但难以高效地回答区间前驱查询，因为这需要在区间的子集内进行条件查询。 这种复杂度的操作组合，非常适合使用分块数据结构来解决。分块的核心思想是“大段维...

题目链接 PEEK70 区间加乘与单点求值 题目描述 给定一个长度为  的数组 。你需要支持三种操作：  区间加数：将区间  内的所有元素都加上一个值 。 区间乘数：将区间  内的所有元素都乘上一个值 。 单点求值：查询下标为  的元素的值，需要对模数 998244353 取模。  解题思路 本题是线段树的经典应用，涉及到两种不同优先级的区间修改操作：加法和乘法。 由于 (a + x) * y 和 a * y + x 的结果不同，我们必须定义一个统一的运算顺序，并设计对应的懒惰标记下推逻辑。通常，我们规定运算的优先级为先乘后加。 懒惰标记 我们需要为线段树的每个节点维护两个懒惰标记：  add...

题目链接 PEEK68 【模板】动态区间和Ⅱ ‖ 区间修改 + 区间查询 题目描述 给定一个长度为  的数组 。你需要支持两种操作：  区间修改：将区间  内的所有元素都加上一个值 。 区间和查询：查询区间  内所有元素的和。  解题思路 本题需要同时支持区间的动态修改和区间的查询，是数据结构领域的经典问题。朴素的数组操作（区间修改 ，区间查询 ）在大量操作下会超时。 解决此问题的标准高效方法是使用 线段树 (Segment Tree)，并结合 懒惰标记 (Lazy Propagation) 来处理区间修改。   线段树 线段树是一种二叉树，每个节点代表原数组的一个区间 。  根节点代表整个区...

题目链接 PEEK69 区间根号与区间求和 题目描述 给定一个长度为  的数组 ，你需要构建一个数据结构来支持以下两种操作共  次：  区间根号：给定区间 ，将该区间中的所有元素  修改为其向下取整的平方根，即 。 区间和查询：给定区间 ，输出该区间中所有元素的和，即 。  数据范围：, 。 解题思路 本题是典型的区间修改与区间查询问题，通常可以采用线段树来解决。标准的区间求和是线段树的常规操作，但“区间开方”这个修改操作比较特殊。 一个数开方后的值与它自身的大小有关，这意味着我们不能像区间加法那样，用一个统一的“懒标记”来表示对整个区间的修改。一个直接的想法是，每次修改都遍历到线段树的叶子节...

题目链接 PEEK67 区间增量与单点求值 题目描述 给定一个长度为  的数组 。你需要支持两种操作：  区间增量：将区间  内的所有元素都加上一个值 。 单点求值：查询下标为  的元素  的值。  解题思路 本题包含对区间的动态修改和对单点的查询，是数据结构领域的经典问题。如果使用朴素数组，区间修改的复杂度为 ，在大量操作下会超时。 解决此问题的标准高效方法是利用 差分数组 (Difference Array) 和 树状数组 (Fenwick Tree / Binary Indexed Tree)。   差分数组 我们不直接维护原数组 ，而是维护它的差分数组 ，其中  (约定 )。  性质：...

题目链接 PEEK66 余数求和 题目描述 对于给定的正整数  和  ()，求表达式  的值。 解题思路 本题要求计算 。 首先，一个直接的想法是循环  从  到 ，累加每一个  的值。但由于  的范围可以达到 ，这种  的朴素算法显然会超时。我们需要寻找更高效的方法。 我们可以利用取模运算和整除运算之间的关系来进行数学变换。我们知道，对于任意正整数  和 ，有：  将这个关系代入原求和式中，得到：  我们可以将这个和式拆分为两部分：   现在，问题转化为了如何快速计算 。 这个和式的关键部分是 。我们在此前的题目中已经知道， 的值在  连续变化时，会在很多区间内保持不变。这提示我们可以使用整...

题目链接 PEEK65 下取整乘积求和 题目描述 对于给定的正整数 ，求表达式  的值。 解题思路 本题是 整除分块（也称 数论分块）算法的又一个典型应用。 由于  的范围可以达到 ，使用  的朴素循环来计算每一项的和是不可行的，会导致超时。 核心观察与分块计算 我们注意到，在表达式  中，存在许多连续的  会得到完全相同的商。我们可以将这些  划分成块，并对每个块进行整体计算。 假设对于一个块，其范围是 [l, r]，在这个区间内所有的  都有相同的商 。那么这个块对总和的贡献为：  其中  是一个等差数列，其和为 。 块的边界与算法流程 算法的关键在于，对于一个块的左边界 ，我们可以通过公...

题目链接 PEEK64 区间因数个数之和 题目描述 给定两个正整数  和  ()，求值在  区间内的所有整数的因数个数之和。形式化地，就是计算  的值，其中  表示正整数  的因数个数。 解题思路 本题要求计算区间  内所有数的因数个数之和。直接对区间内每个数进行因数分解并计数，效率会很低。一个常见的优化思路是利用前缀和思想，将问题转化为计算两个从  开始的区间的差：  这样，问题就变成了如何快速计算函数 。 让我们换一个角度来思考  的计算。与其枚举每个数  并计算它的因数个数 ，我们可以反过来考虑每个数  (从  到 ) 作为因数，对总和贡献了多少次。 一个数  是  的因数，其中 。在 ...

题目链接 PEEK62 区间GCD 题目描述 给定一个包含  个正整数的数组 。有  次询问，每次询问给定一个下标区间 ，要求输出  中所有元素的最大公因数 (GCD)。 解题思路 本题要求我们高效地回答关于静态数组的区间查询。具体来说，是查询区间内所有元素的最大公因数 (GCD)。 一个朴素的方法是，对于每次查询 ，都遍历从  到  的所有元素并依次计算它们的 GCD。单次查询的时间复杂度为 ，其中  项是计算 GCD 的开销。在有  次查询的情况下，总时间复杂度会达到 ，这对于  的数据规模来说是无法接受的。 为了优化查询，我们需要一种能在更短时间内处理区间查询的数据结构。注意到 GCD ...