365 day challenge leetcode 1000 questions - day 037 elements and the maximum side length of squares less than or equal to the threshold + the number of subsequences that meet the conditions

---

1292. The maximum side length of an element and a square less than or equal to the threshold

This question needs to use The prefix and , The official explanation of the question is very good

Code implementation （ Part depends on the solution ）

class Solution {
    
private:
    bool validate(vector<vector<int>>& _mat, int threshold,
    int x1, int y1, int x2, int y2) {
    
        return _mat[x2][y2] - _mat[x1 - 1][y2] - _mat[x2][y1 - 1]
        + _mat[x1 - 1][y1 - 1] <= threshold;
    }
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
    
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> _mat(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++)
                _mat[i][j] = _mat[i - 1][j] + _mat[i][j - 1] -
                _mat[i - 1][j - 1] + mat[i - 1][j - 1];
        }
        int l = 0;
        int r = min(m, n);
        while (l < r) {
    
            int mid = (l + r + 1) >> 1;
            bool flag = false;
            for (int i = 1; i <= m - mid + 1; i++) {
    
                for (int j = 1; j <= n - mid + 1; j++) {
    
                    if (validate(_mat, threshold, i, j, i + mid - 1,
                    j + mid - 1)) {
    
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
            if (flag) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

---

1498. The number of subsequences satisfying the condition

This problem requires a pretreatment for the number of subsequences , Otherwise, the upper limit will be exceeded

Code implementation （ Part depends on the solution ）

class Solution {
    
private:
    static constexpr int P = int(1E9) + 7;
    static constexpr int MAX_N = int(1E5) + 5;
    void pretreatment(vector<int>& po) {
    
        int f = 1;
        po.push_back(f);
        for (int i = 1; i < MAX_N; i++) {
    
            f = f * 2 % P;
            po.push_back(f);
        }
    }
public:
    int numSubseq(vector<int>& nums, int target) {
    
        vector<int> po;
        pretreatment(po);
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long ans = 0;
        for (int i = 0; i < n; i++) {
    
            if (2 * nums[i] > target) break;
            int t = target - nums[i];
            int bound = upper_bound(nums.begin() + i, nums.end(), t) -
            nums.begin();
            ans += po[bound - i - 1];
        }
        return ans % P;
    }
};