粟粟的书架(主席树+前缀和)

题目链接粟粟的书架
题目大意: 给你一个$n \times m$的矩阵, $q$个询问, 每次给你一个左上角在$(x1,y1)$,右下角在$(x2,y2)$的子矩阵, 和一个权值$h$, 要求在子矩阵中选出最少的数,使得这些数的和不小于$h$.
思路:
注意到题目数据有$50 %$是${n \leq 200, n \leq 200, q \leq
2 \times 10^5}$, 这样我们可以对这$50%$的数据进行前缀和暴力预处理, 设$cnt_k[i][j][k]$为$(1,1) 到 (i,j)$这个子矩阵中$\geq k$的个数, $sum_k[i][j][k]为(1,1) 到(i,j)$这个子矩阵中$\geq k$的元素和.这样我们就可以二分$k$,来进行求解.
另外$50%$的数据是${n=1, m \leq 5 \times 10^5 , q \leq 2 \times 10^4}$, 那么就变成了区间$(y1,y2)$内找出最少的数使其和不小于$h$, 我们可以用主席树来求解, 并二分$k$使区间内大于等于$k$的元素和不小于$h$.
注意, 这里二分过程中求解的次数并非最小次数, 还需要将多余的$\lceil \frac{h}{k} \rceil$向上取整转化为次数

#include<bits/stdc++.h>
using namespace::std;
#define fi first
#define se second
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l + r) >> 1)
#define zty(x) cout << #x << " = " << x << '\n';
const int MAX_N = 5e5 + 5;
const int MAX_M = 2e6 + 5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;

int n, m, q;
struct PresidentTree {
    int rt[MAX_N], tot;
    int sum[MAX_N * 32], cnt[MAX_N * 32], ls[MAX_N * 32], rs[MAX_N * 32];
    int update(int p, int l, int r, int val) {
        int x = ++ tot;
        sum[x] = sum[p] + val;
        cnt[x] = cnt[p] + 1;
        if(l == r) return x;
        if(val <= mid) ls[x] = update(ls[p], l, mid, val), rs[x] = rs[p];
        else rs[x] = update(rs[p], mid + 1, r, val), ls[x] = ls[p];
        return x;
    }
    int query(int p, int q, int l, int r, int limit) {
        if(l == r) return (limit + l - 1) / l;
        int rcnt = cnt[rs[p]] - cnt[rs[q]];
        int rsum = sum[rs[p]] - sum[rs[q]];
        if(rsum >= limit) return query(rs[p], rs[q], mid + 1, r, limit);
        else return query(ls[p], ls[q], l, mid, limit - rsum) + rcnt;
    }
} PT;
int a[205][205];
int sum_k[205][205][1005];
int cnt_k[205][205][1005];
void solve() {
    cin >> n >> m >> q;
    if(n == 1) {
        for(int i = 1; i <= m; ++ i) {
            int x;
            cin >> x;
            PT.rt[i] = PT.update(PT.rt[i - 1], 1, 1000, x);
        }
        while(q -- ) {
            int x1, y1, x2, y2, h;
            cin >> x1 >> y1 >> x2 >> y2 >> h;
            if(PT.sum[PT.rt[y2]] - PT.sum[PT.rt[y1 - 1]] < h) {
                cout << "Poor QLW" << '\n';
            } else {
                cout << PT.query(PT.rt[y2], PT.rt[y1 - 1], 1, 1000, h) << '\n';
            }
        }
    } else {
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= m; ++ j) cin >> a[i][j];
        }
        for(int k = 1; k <= 1000; ++ k) {
            for(int i = 1; i <= n; ++ i) {
                for(int j = 1; j <= m; ++ j) {
                    sum_k[i][j][k] = sum_k[i - 1][j][k] + sum_k[i][j - 1][k] - sum_k[i - 1][j - 1][k] + (a[i][j] >= k ? a[i][j] : 0);
                    cnt_k[i][j][k] = cnt_k[i - 1][j][k] + cnt_k[i][j - 1][k] - cnt_k[i - 1][j - 1][k] + (a[i][j] >= k ? 1 : 0);
                }
            }
        }
        auto Get_sum = [&](int x1, int y1, int x2, int y2, int k) {
            return sum_k[x2][y2][k] - sum_k[x1 - 1][y2][k] - sum_k[x2][y1 - 1][k] + sum_k[x1 - 1][y1 - 1][k];
        };
        auto Get_cnt = [&](int x1, int y1, int x2, int y2, int k) {
            return cnt_k[x2][y2][k] - cnt_k[x1 - 1][y2][k] - cnt_k[x2][y1 - 1][k] + cnt_k[x1 - 1][y1 - 1][k];
        };
        while(q -- ) {
            int x1, y1, x2, y2, h;
            cin >> x1 >> y1 >> x2 >> y2 >> h;
            if(Get_sum(x1, y1, x2, y2, 1) < h) {
                cout << "Poor QLW" << '\n';
            } else {
                int l = 1, r = 1000, ret = 0;
                while(l <= r) {
                    if(Get_sum(x1, y1, x2, y2, mid) >= h) {
                        ret = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                cout << Get_cnt(x1, y1, x2, y2, ret) - (Get_sum(x1, y1, x2, y2, ret) - h) / ret << '\n';
            }
        }
    }
}
signed main() {
//    freopen("SPO.IN", "r", stdin);
//    freopen("SPO.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ZTY = 1;
    //cin >> ZTY;
    while(ZTY -- ) solve();
    return 0;
}