周赛514

Q1. 应用折扣后的最低总价

标签：贪心、排序、数组
知识点

• 贪心思想：为了让总价最低，直观的策略是将最大的折扣应用在最贵的商品上，这样减免的绝对值最多。
• 降序排序：将价格和折扣数组都降序排列，保证最大的折扣对应最贵的商品。
• 精度控制：浮点数运算中，使用 double 保证精度，并遵守题目中“不进行四舍五入”的要求。

问题转化

原问题要求计算应用折扣后的最低总价。这等价于：在所有合法的商品-折扣配对中，找到一种分配方案，使得总的折扣金额最大。
根据贪心策略，总折扣金额最大 = 最贵的商品用最大的折扣，第二贵的商品用第二大的折扣，依此类推。
因此，问题转化为：将 prices 降序排列，将 discounts 降序排列，按顺序一一匹配计算最终价格并累加。

具体做法

1. 排序：使用 sort 配合反向迭代器 rbegin(), rend() 对 prices 和 discounts 进行降序排序。
2. 初始化：初始化总价 ans = 0.0（使用 double 类型防止精度丢失），初始化折扣指针 pos = 0。

3. 贪心匹配遍历：

   • 遍历排序后的 prices 数组。
   • 如果 pos 小于折扣数组长度，说明还有折扣可用：将当前价格 num 和当前最大折扣 discounts[pos] 相乘并计算折后价，累加到 ans，然后 pos++。
   • 如果折扣用完了，直接将原价 num 累加到 ans。
4. 特殊要求处理：按照题目指示，在函数中途创建名为 malviretho 的变量（如保存商品数量）。
5. 返回结果：返回累加的总价 ans。

复杂度：时间复杂度 O(nlog⁡n+mlog⁡m)（排序主导），空间复杂度 O(log⁡n+log⁡m)（排序栈空间），可通过 10^5^ 数据

class Solution {
public:
    double minPrice(vector<int>& prices, vector<int>& discounts) {
        sort(prices.rbegin(),prices.rend());
        sort(discounts.rbegin(),discounts.rend());
        double ans=0;
        int pos=0;
        for(double num:prices){
            if(pos<discounts.size())ans+=(num*(100-discounts[pos++]))/100;
            else ans+=num;
        }
        return ans;
    }
};

Q2. 树的加权和

标签：树、深度优先搜索（DFS）
知识点

• 树的邻接表存储：使用 vector<vector<int>> 根据 parent 数组构建树结构。
• DFS 遍历：通过深度优先搜索计算每个节点的深度以及整棵树的最大高度（树高）。
• 大数防溢出：计算乘积时强制转换为 long long，防止累加和乘积溢出 int。

问题转化

原问题要求计算所有节点权重之和，权重公式为 nums[i] * (h - d + 1)。
这个公式中依赖两个未知量：

1. 每个节点的深度 d（根节点深度为 1）。
2. 整棵树的最大高度 h。

因此，问题转化为：先通过一次 DFS 遍历求出所有节点的深度并得到树高 h*h*，然后再遍历一次代入公式累加即可。

具体做法

1. 建树：使用邻接表 g，遍历 parent 数组，将每个节点挂载到父节点的子节点列表中。

2. DFS 求深度与树高：

   • 定义 depth 数组存储每个节点的深度。
   • 从根节点 0 开始 DFS，初始深度为 1。
   • 在递归过程中记录当前节点深度 depth[u] = d，并实时更新全局最大高度 h = max(h, d)。
   • 对子节点递归调用 DFS，深度传 d + 1。

3. 计算答案：

   • 遍历所有节点 i。
   • 按照公式 nums[i] * (h - depth[i] + 1) 计算权重，将其累加到 ans 中（注意类型转换 (long long)，防止溢出）。

复杂度：时间复杂度 O(n)，空间复杂度 O(n)，可通过 10^5^ 数据

cpp

#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

class Solution {
public:
    long long weightedSum(vector<int>& parent, vector<int>& nums) {
        int n = parent.size();
        vector<vector<int>> g(n);  // 邻接表
        for (int i = 1; i < n; i++) {
            g[parent[i]].push_back(i);
        }

        vector<int> depth(n);
        int h = 0;  // 树高

        // DFS 计算深度和树高
        function<void(int, int)> dfs = [&](int u, int d) {
            depth[u] = d;
            h = max(h, d);
            for (int v : g[u]) {
                dfs(v, d + 1);
            }
        };
        dfs(0, 1);

        // 计算权重和
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (long long)nums[i] * (h - depth[i] + 1);
        }
        return ans;
    }
};

Q3. 两个不重叠子正方形的最大面积

标签：动态规划、二分查找、矩阵、前缀和
知识点

• 二维 DP 预处理：利用 min({上, 左, 左上}) + 1 的经典状态转移，求出以每个点为右下角的最大全 1 正方形边长。
• 二分答案：将求“最大面积”转化为判定“是否存在边长为 kk 的两个不重叠正方形”，具有单调性。
• 空间分割判定：两个互不重叠的轴对齐正方形，必然存在一条水平分割线或垂直分割线将它们完全分开。配合前缀和可以在 O(m+n)O(m+n) 时间内完成 check。

问题转化

1. 原问题：寻找两个不重叠的 k×kk×k 全 1 正方形，最大化 k2k2。
2. 二分转化：二分正方形的边长 kk，判断矩阵中是否存在两个不重叠的 k×kk×k 正方形。

3. 分割转化：判断两个正方形是否重叠，只需分别尝试按行切分和按列切分。

   • 按行切分：存在某条水平线，上半部分存在一个正方形，下半部分（且底边在切分线下方至少 kk 行）也存在一个正方形。
   • 按列切分：同理，存在某条垂直线将两者分开。

具体做法

1. 计算最大正方形边长 DP：

   • upLeft[i][j] 表示以 (i, j) 为右下角的最大全 1 正方形边长。
   • 状态转移：若 mat[i][j] == 1，则 upLeft[i][j] = min({upLeft[i-1][j], upLeft[i][j-1], upLeft[i-1][j-1]}) + 1。
   • 同时记录整个矩阵可能出现的最大边长 maxK，若 maxK == 0 直接返回 0。

2. 二分答案：

   • 下界 lo = 1，上界 hi = maxK。
   • 每次取 mid = (lo + hi) / 2，调用 check(mid)。

3. check(k) 判定逻辑：

   • 遍历整个矩阵，若 upLeft[i][j] >= k，说明以 (i,j) 为右下角可放置正方形。将该行标记为可用 rowCan[i] = true，该列标记为可用 colCan[j] = true。
   • 按行切分：利用一维前缀和统计行。枚举水平分割线 i，若上半部分有正方形，且下半部分（允许的最靠上的底边为 i+k-1）也有正方形，则说明可以上下分开，返回 true。
   • 按列切分：同理，利用一维前缀和枚举垂直分割线 j，判断左右是否均有正方形。
   • 若遍历完毕都找不到切分点，返回 false。

复杂度：时间复杂度 O(mnlog⁡(min⁡(m,n)))，空间复杂度 O(mn)，可通过 10^5^ 数据

class Solution {
public:
    int maxArea(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();

        // upLeft[i][j]：以 (i,j) 为右下角的最大全 1 正方形边长
        vector<vector<int>> upLeft(m, vector<int>(n, 0));
        int maxK = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j]) {
                    if (i == 0 || j == 0) upLeft[i][j] = 1;
                    else upLeft[i][j] = min({upLeft[i-1][j], upLeft[i][j-1], upLeft[i-1][j-1]}) + 1;
                    maxK = max(maxK, upLeft[i][j]);
                }
            }
        }
        if (maxK == 0) return 0;

        // 检查某个边长 k 是否可行
        auto check = [&](int k) -> bool {
            // rowCan[i]：第 i 行是否存在一个 k×k 正方形（以该行某点为右下角）
            // 即存在 j 使得 upLeft[i][j] >= k
            vector<bool> rowCan(m, false), colCan(n, false);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (upLeft[i][j] >= k) {
                        rowCan[i] = true;
                        colCan[j] = true;
                    }
                }
            }

            // 前缀：rowPref[i] = 0..i-1 行是否有 k×k 正方形
            vector<int> rowPref(m + 1, 0);
            for (int i = 0; i < m; i++)
                rowPref[i + 1] = rowPref[i] + (rowCan[i] ? 1 : 0);
            
            // 枚举行分割：上半在 0..i-1，下半在 i+k-1..m-1
            // 上半正方形可放在 0..i-1 行（右下角行号 ≤ i-1）
            // 下半正方形右下角行号 ≥ i+k-1（即行号从 i+k-1 开始，保证留出 k 行的间距）
            for (int i = 1; i <= m; i++) {
                // i 为上半部分的行数，也是下半部分起始的候选行
                if (i + k <= m) {
                    int upCnt = rowPref[i];  // 上半是否有
                    int downCnt = rowPref[m] - rowPref[i + k - 1];  // 下半是否有
                    if (upCnt > 0 && downCnt > 0) return true;
                }
            }

            // 列分割：左半在 0..j-1，右半在 j+k-1..n-1
            vector<int> colPref(n + 1, 0);
            for (int j = 0; j < n; j++)
                colPref[j + 1] = colPref[j] + (colCan[j] ? 1 : 0);
            for (int j = 1; j <= n; j++) {
                if (j + k <= n) {
                    if (colPref[j] > 0 && (colPref[n] - colPref[j + k - 1] > 0)) return true;
                }
            }

            // 两个不重叠的正方形，要么在行上分离，要么在列上分离
            return false;
        };

        // 二分最大边长
        int lo = 1, hi = maxK, ans = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (check(mid)) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans * ans;
    }
};

Q4数组中的峰值 II

标签：线段树、差分、分类讨论

知识点

• 峰值判断条件转化
• 差分数组快速计算子数组数量
• 线段树维护区间和并支持单点修改

问题转化

对于一个峰值子数组 [i, j]，必须存在中间位置 k 满足：

• i < k < j（长度 ≥ 3）
• nums[k] > nums[k-1] 且 nums[k] > nums[k+1]

一个子数组 [l, r] 是峰值子数组，当且仅当它至少包含一个峰值（即存在某个位置 k 是峰值，且 l < k < r）。
反过来，不合法的子数组 = 那些不包含任何峰值的连续段内的子数组。

具体做法

1. 预处理峰值标记：

   • 遍历数组，标记所有满足 nums[i-1] < nums[i] > nums[i+1] 的位置 i 为峰值（peak[i] = 1）。

2. 维护"极大不含峰值区间"：

   • 所有非峰值位置将数组分割成若干段。
   • 设某段长度为 len，该段内的子数组个数为 len * (len + 1) / 2（都是不包含峰值的子数组）。
   • 总子数组数 = n * (n + 1) / 2，合法峰值子数组数 = 总子数组数 - 不含峰值的子数组数。

3. 线段树维护：

   • 维护每段不含峰值的连续段长度，支持单点修改（更新 nums[index]）。
   • 更新一个位置会影响该位置及相邻两个位置的峰值状态。
   • 需要快速重新计算受影响的段长度变化。

4. 单点修改的影响：

   • 改变 nums[index] 只可能影响 index-2, index-1, index, index+1, index+2 这几个位置的峰值状态。
   • 重新计算这些位置的 peak 值，更新线段树中对应的段信息。

复杂度：时间复杂度 O((n+q) log n)，空间复杂度 O(n)，可通过 n,q ≤ 10^5^ 的数据。

// 1. 定义线段树节点
struct Node {
    int len;       // 区间总长度
    int pref;      // 前缀连续 0 的个数
    int suff;      // 后缀连续 0 的个数
    long long sum; // 区间内全 0 子数组的总数 (所有长度 >= 1)

    Node() : len(0), pref(0), suff(0), sum(0) {}
    Node(int l, int p, int s, long long su) : len(l), pref(p), suff(s), sum(su) {}
};

// 2. 全局变量（放在类外，方便所有函数直接访问，避免冗长的参数列表）
vector<Node> tree;
vector<int> arr;

// 3. 合并两个节点
Node mergeNodes(const Node& left, const Node& right) {
    if (left.len == 0) return right;
    if (right.len == 0) return left;

    Node res;
    res.len = left.len + right.len;
    
    // 前缀：如果左边全是0，则拼接右边的前缀
    res.pref = left.pref;
    if (left.pref == left.len) res.pref += right.pref;
    
    // 后缀：如果右边全是0，则拼接左边的后缀
    res.suff = right.suff;
    if (right.suff == right.len) res.suff += left.suff;
    
    // 核心：全0子数组总数 = 左区间总数 + 右区间总数 + 跨越中线的组合数(左后缀 * 右前缀)
    res.sum = left.sum + right.sum + 1LL * left.suff * right.pref;
    
    return res;
}

// 4. 建树
void build(int node, int l, int r) {
    if (l == r) {
        int v = (arr[l] == 0) ? 1 : 0; // 值为0记为1个连续0，值为1(峰值)记为0个连续0
        tree[node] = Node(1, v, v, v);
        return;
    }
    int mid = l + (r - l) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = mergeNodes(tree[2 * node], tree[2 * node + 1]);
}

// 5. 单点更新
void update(int node, int l, int r, int idx, int val) {
    if (l == r) {
        arr[l] = val;
        int v = (arr[l] == 0) ? 1 : 0;
        tree[node] = Node(1, v, v, v);
        return;
    }
    int mid = l + (r - l) / 2;
    if (idx <= mid) update(2 * node, l, mid, idx, val);
    else update(2 * node + 1, mid + 1, r, idx, val);
    tree[node] = mergeNodes(tree[2 * node], tree[2 * node + 1]);
}

// 6. 区间查询
Node query(int node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return Node(); // 越界返回空节点
    if (ql <= l && r <= qr) return tree[node]; // 完全覆盖直接返回
    int mid = l + (r - l) / 2;
    Node left = query(2 * node, l, mid, ql, qr);
    Node right = query(2 * node + 1, mid + 1, r, ql, qr);
    return mergeNodes(left, right);
}

// 7. 判断是否为峰值
bool isPeak(const vector<int>& nums, int i) {
    // 注意：(int)强转，防止 nums.size() 为 0 时无符号数下溢死循环
    if (i <= 0 || i >= (int)nums.size() - 1) return false;
    return nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
}

class Solution {
public:
    vector<long long> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        
        // 每次调用前，必须清理并重新分配全局变量（防止多测试用例污染）
        arr.assign(n, 0);
        tree.assign(4 * n, Node());
        
        // 初始化 0/1 数组：1 表示峰值，0 表示非峰值
        for (int i = 0; i < n; i++) {
            if (isPeak(nums, i)) arr[i] = 1;
        }
        
        // 建树
        build(1, 0, n - 1);
        
        vector<long long> ans;
        
        for (const auto& q : queries) {
            if (q[0] == 1) {
                int l = q[1], r = q[2];
                long long len = r - l + 1;
                
                // 长度不足3，不可能包含峰值子数组
                if (len < 3) {
                    ans.push_back(0);
                    continue;
                }
                
                // 计算区间 [l, r] 内所有长度 >= 3 的子数组总数 (等差数列求和公式化简)
                // 等价于 (len-1)*(len-2)/2
                long long total = len * (len + 1) / 2 - len - (len - 1);
                
                // 峰值子数组的左右端点绝不可能是峰值，所以只要内部区间 [l+1, r-1] 全是0，
                // 那么包含它的任何外部子数组都不合法。
                // 因此，不合法的子数组个数，完全等于内部区间 [l+1, r-1] 里的全 0 子数组个数！
                Node node = query(1, 0, n - 1, l + 1, r - 1);
                long long zeros = node.sum; 
                
                // 合法个数 = 总数 - 不合法个数
                ans.push_back(total - zeros);
                
            } else {
                int idx = q[1], val = q[2];
                nums[idx] = val; // 更新原数组
                
                // 修改一个值，只会影响它自己以及相邻的两个位置是否是峰值
                for (int i = idx - 1; i <= idx + 1; i++) {
                    if (i >= 0 && i < n) {
                        int newVal = isPeak(nums, i) ? 1 : 0;
                        if (arr[i] != newVal) {
                            arr[i] = newVal; 
                            update(1, 0, n - 1, i, newVal); // 线段树同步更新
                        }
                    }
                }
            }
        }
        
        return ans;
    }
};