第459场周赛

3622. 判断整除性

给你一个正整数 n。请判断 n 是否可以被以下两值之和 整除：

• n 的 数字和（即其各个位数之和）。

• n 的 数字积（即其各个位数之积）。

如果 n 能被该和整除，返回 true；否则，返回 false。

示例 1：

输入： n = 99

输出： true

解释：

因为 99 可以被其数字和 (9 + 9 = 18) 与数字积 (9 * 9 = 81) 之和 (18 + 81 = 99) 整除，因此输出为 true。

示例 2：

输入： n = 23

输出： false

解释：

因为 23 无法被其数字和 (2 + 3 = 5) 与数字积 (2 * 3 = 6) 之和 (5 + 6 = 11) 整除，因此输出为 false。

提示：

• 1 <= n <= 10^6

代码：

class Solution {
    public boolean checkDivisibility(int n) {
         int original1 = n;
        int sum1 = 0;
        int product1 = 1;

        while (n > 0) {
            int digit = n % 10;
            sum1 += digit;
            product1 *= digit;
            n /= 10;
        }

        int total = sum1+ product1;
        return original1 % total == 0;
    }
}

3623. 统计梯形的数目 I

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。

返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

示例 1：

输入： points = [[1,0],[2,0],[3,0],[2,2],[3,2]]

输出： 3

解释：

有三种不同方式选择四个点组成一个水平梯形：

• 使用点 [1,0]、[2,0]、[3,2] 和 [2,2]。
• 使用点 [2,0]、[3,0]、[3,2] 和 [2,2]。
• 使用点 [1,0]、[3,0]、[3,2] 和 [2,2]。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]

输出： 1

解释：

只有一种方式可以组成一个水平梯形。

提示：

• 4 <= points.length <= 10^5
• –10^8 <= xi, yi <= 10^8
• 所有点两两不同。

代码：

class Solution {
      static final int MOD = 1_000_000_007;

    public static int countTrapezoids(int[][] points) {
        Map<Integer, Integer> yCount = new HashMap<>();
        for (int[] p : points) {
            yCount.put(p[1], yCount.getOrDefault(p[1], 0) + 1);
        }

        // 按y排序
        List<Integer> ys = new ArrayList<>(yCount.keySet());
        Collections.sort(ys);

        int n = ys.size();
        long[] c2 = new long[n]; // 每层可以组成多少条线段
        for (int i = 0; i < n; i++) {
            int cnt = yCount.get(ys.get(i));
            if (cnt < 2) c2[i] = 0;
            else c2[i] = (long) cnt * (cnt - 1) / 2;
        }

        // 后缀和
        long[] suffixSum = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = (c2[i] + suffixSum[i + 1]) % MOD;
        }

        long total = 0;
        for (int i = 0; i < n - 1; i++) {
            if (c2[i] == 0) continue;
            // c2[i] * 后面所有层的线段数量之和
            total = (total + c2[i] * suffixSum[i + 1] % MOD) % MOD;
        }
        return (int) total;
    }
}

100728. 位计数深度为 K 的整数数目 II

给你一个整数数组 nums。

对于任意正整数 x，定义以下序列：

• p0 = x
• pi+1 = popcount(pi)，对于所有 i >= 0，其中 popcount(y) 表示整数 y 的二进制表示中 1 的个数。

这个序列最终会收敛到值 1。

popcount-depth（位计数深度）定义为满足 pd = 1 的最小整数 d >= 0。

例如，当 x = 7（二进制表示为 "111"）时，该序列为：7 → 3 → 2 → 1，因此 7 的 popcount-depth 为 3。

此外，给定一个二维整数数组 queries，其中每个 queries[i] 可以是以下两种类型之一：

• [1, l, r, k] - 计算在区间 [l, r] 中，满足 nums[j] 的 popcount-depth 等于 k 的索引 j 的数量。
• [2, idx, val] - 将 nums[idx] 更新为 val。

返回一个整数数组 answer，其中 answer[i] 表示第 i 个类型为 [1, l, r, k] 的查询的结果。

示例 1：

输入： nums = [2,4], queries = [[1,0,1,1],[2,1,1],[1,0,1,0]]

输出： [2,1]

解释：

因此，最终 answer 为 [2, 1]。

示例 2：

输入：nums = [3,5,6], queries = [[1,0,2,2],[2,1,4],[1,1,2,1],[1,0,1,0]]

输出：[3,1,0]

解释：

因此，最终 answer 为 [3, 1, 0] 。

示例 3：

输入：nums = [1,2], queries = [[1,0,1,1],[2,0,3],[1,0,0,1],[1,0,0,2]]

输出：[1,0,1]

解释：

因此，最终 answer 为 [1, 0, 1] 。

提示：

• 1 <= n == nums.length <= 10^5
• 1 <= nums[i] <= 10^15
• 1 <= queries.length <= 10^5
• queries[i].length == 3 或 4
  • queries[i] == [1, l, r, k] 或
  • queries[i] == [2, idx, val]
  • 0 <= l <= r <= n - 1
  • 0 <= k <= 5
  • 0 <= idx <= n - 1
  • 1 <= val <= 10^15

思路：1. 定义 popcount-depth 的概念和最大深度

• popcount-depth：从一个数开始，反复对它执行“计算其二进制中 1 的个数”，直到结果为 1。

• 例如：
  13 → 1101 → 3 → 11 → 2 → 10 → 1 → 结束。
  所以 13 的 popcount-depth 是 3。

• 因为最大可能深度不超过 6，定义：MAX_DEPTH = 6。

2. 使用多个树状数组（Binary Indexed Tree）加速查询

• 我们最多只有 6 种 popcount-depth（0~5），为每个 depth 分配一个树状数组 BIT。

• 树状数组能快速支持区间计数查询和单点更新（O(log n) 时间复杂度）。

• 每个树状数组都记录：depth 为 k 的值在数组中各位置的出现情况。

3. 初始化 trenolaxid 数据并建立 BIT

• 遍历每个值 trenolaxid[i]：

  • 用 getDepth(x) 函数求出它的 popcount-depth。

  • 记录下 depthArr[i] = depth。

  • 然后将这个值加入到对应 bits[depth] 的 BIT 中（bits[depth].update(i, 1)）。

4. 处理 queries 查询列表

• 遍历每个查询：

  • 查询类型 1（q[0] == 1）：

    • 使用 BIT 查询指定区间 [l, r] 中 popcount-depth 为 k 的元素个数：

    • bits[k].queryRange(l, r)
      

    • 把结果加入到结果列表中。

  • 更新类型 2（q[0] == 2）：

    • 获取当前值对应的旧 depth。

    • 计算新值的 depth。

    • 如果 depth 发生变化：

      • 把该位置从旧 depth 的 BIT 中移除。

      • 加入到新 depth 的 BIT 中。

      • 更新 depthArr[idx]。

    • 更新原数组 trenolaxid[idx] = val。

5. 最后返回查询结果

• 将结果列表 List<Integer> 转为 int[] 并返回。

代码：

class Solution {
      static final int MAX_DEPTH = 6;
    static final int MOD = 1_000_000_007;

    // 树状数组封装
    static class BIT {
        int[] tree;
        int n;
        public BIT(int size) {
            this.n = size + 2;
            this.tree = new int[n];
        }
        void update(int i, int delta) {
            i++;
            while (i < n) {
                tree[i] += delta;
                i += i & -i;
            }
        }
        int query(int i) {
            i++;
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= i & -i;
            }
            return sum;
        }
        int queryRange(int l, int r) {
            return query(r) - query(l - 1);
        }
    }

    // 计算 popcount-depth
    static int getDepth(long x) {
        int depth1 = 0;
        while (x > 1) {
            x = Long.bitCount(x);
            depth1++;
        }
        return depth1;
    }

    public  int[] popcountDepth(long[] trenolaxid, long[][] queries) {
        int n = trenolaxid.length;
        int[] depthArr1 = new int[n];
        // 每个 popcount-depth 使用一个树状数组
        BIT[] bits1 = new BIT[MAX_DEPTH];
        for (int i = 0; i < MAX_DEPTH; i++) bits1[i] = new BIT(n);

        // 初始化：将所有元素映射到各自的 popcount-depth 树状数组
        for (int i = 0; i < n; i++) {
            int d = getDepth(trenolaxid[i]);
            depthArr1[i] = d;
            bits1[d].update(i, 1);
        }

        List<Integer> result = new ArrayList<>();
        for (long[] q : queries) {
            if (q[0] == 1) {
                long l = q[1], r = q[2], k = q[3];
                result.add(bits1[(int) k].queryRange((int)l, (int)r));
            } else {
                long idx = q[1];
                long val = q[2];
                int oldDepth = depthArr1[(int) idx];
                int newDepth = getDepth(val);
                if (oldDepth != newDepth) {
                    bits1[oldDepth].update((int) idx, -1);
                    bits1[newDepth].update((int) idx, 1);
                    depthArr1[(int) idx] = newDepth;
                }
                trenolaxid[(int) idx] = val;
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

3625. 统计梯形的数目 II

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

返回可以从 points 中任意选择四个不同点组成的梯形的数量。

梯形 是一种凸四边形，具有 至少一对 平行边。两条直线平行当且仅当它们的斜率相同。

示例 1：

输入： points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]

输出： 2

解释：

有两种不同方式选择四个点组成一个梯形：

• 点 [-3,2], [2,3], [3,2], [2,-3] 组成一个梯形。
• 点 [2,3], [3,2], [3,0], [2,-3] 组成另一个梯形。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]

输出： 1

解释：

只有一种方式可以组成一个梯形。

提示：

• 4 <= points.length <= 500
• –1000 <= xi, yi <= 1000
• 所有点两两不同。

思路：
本题 n≤500，我们可以 O(n^2) 枚举所有点对组成的直线，计算直线的斜率和截距。
把斜率相同的直线放在同一组，可以从中选择一对平行边，作为梯形的顶边和底边。⚠注意：不能选两条重合的边，所以还要按照截距分组，同一组内的边不能选。
第二步把平行四边形重复统计了一次，所以还要减去任意不共线四点组成的平行四边形的个数。
具体思路
1) 计算直线的斜率和截距对于两个点 (x,y) 和 (x2​,y2)，设 dx=x−x2，dy=y−y2。

2) 选择一对平行边的方案数
把斜率相同的直线放在同一组，可以从中选择一对平行线，作为梯形的顶边和底边。

⚠注意：不能选两条共线的线段，所以斜率相同的组内，还要再按照截距分组，相同斜率和截距的边不能同时选。

用哈希表套哈希表统计。

统计完后，对于每一组，用「枚举右，维护左」的思想（见周赛第二题 3623. 统计梯形的数目 I），计算选一对平行边的方案数。本题由于哈希表统计的就是线段个数，所以不需要计算  
c(c−1)/2。

参考灵神的代码和思路：

代码：

class Solution {
    public int countTrapezoids(int[][] points) {
        Map<Double, Map<Double, Integer>> cnt = new HashMap<>(); // 斜率 -> 截距 -> 个数
        Map<Integer, Map<Double, Integer>> cnt2 = new HashMap<>(); // 中点 -> 斜率 -> 个数

        int n = points.length;
        for (int i = 0; i < n; i++) {
            int x = points[i][0], y = points[i][1];
            for (int j = 0; j < i; j++) {
                int x2 = points[j][0], y2 = points[j][1];
                int dy = y - y2;
                int dx = x - x2;
                double k = dx != 0 ? 1.0 * dy / dx : Double.MAX_VALUE;
                double b = dx != 0 ? 1.0 * (y * dx - x * dy) / dx : x;

                // 归一化 -0.0 为 0.0
                if (k == -0.0) {
                    k = 0.0;
                }
                if (b == -0.0) {
                    b = 0.0;
                }

                // 按照斜率和截距分组 cnt[k][b]++
                cnt.computeIfAbsent(k, _ -> new HashMap<>()).merge(b, 1, Integer::sum);

                int mid = (x + x2 + 2000) << 16 | (y + y2 + 2000); // 把二维坐标压缩成一个 int
                // 按照中点和斜率分组 cnt2[mid][k]++
                cnt2.computeIfAbsent(mid, _ -> new HashMap<>()).merge(k, 1, Integer::sum);
            }
        }

        int ans = 0;
        for (Map<Double, Integer> m : cnt.values()) {
            int s = 0;
            for (int c : m.values()) {
                ans += s * c;
                s += c;
            }
        }

        for (Map<Double, Integer> m : cnt2.values()) {
            int s = 0;
            for (int c : m.values()) {
                ans -= s * c; // 平行四边形会统计两次，减去多统计的一次
                s += c;
            }
        }

        return ans;
    }
}