题目地址：洛谷：【P2468】[SDOI2010]粟粟的书架 – 洛谷、BZOJ：Problem 1926. — [Sdoi2010]粟粟的书架

题目描述

幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j页厚。
粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。不过她发现，如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第i天指定的那个苹果，只要她脚下放置书的总页数之和不低于Hi，就一定能够摘到。
由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形，第i天给定区域的左上角是上数第x1i行的左数第y1i本书，右下角是上数第x2i行的左数第y2i本书。换句话说，粟粟在这一天，只能在这﹙x2i－x1i＋1﹚×﹙y2i－y1i＋1﹚本书中挑选若干本垫在脚下，摘取苹果。
粟粟每次取书时都能及时放回原位，并且她的书架不会再撤下书目或换上新书，摘苹果的任务会一直持续M天。给出每本书籍的页数和每天的区域限制及采摘要求，请你告诉粟粟，她每天至少拿取多少本书，就可以摘到当天指定的苹果。

题意简述

有一个矩阵，每次询问给一个子矩阵的范围，求该范围中最少取几个数使得它们的和不小于定值h。

输入输出格式

输入格式：
输入文件susu.in第一行是三个正整数R, C, M。
接下来是一个R行C列的矩阵，从上到下、从左向右依次给出了每本书的页数Pi,j。
接下来M行，第i行给出正整数x1i, y1i, x2i, y2i, Hi，表示第i天的指定区域是﹙x1i, y1i﹚与﹙x2i, y2i﹚间的矩形，总页数之和要求不低于Hi。
保证1≤x1i≤x2i≤R，1≤y1i≤y2i≤C。

输出格式：
输出文件susu.out有M行，第i行回答粟粟在第i天时为摘到苹果至少需要拿取多少本书。如果即使取走所有书都无法摘到苹果，则在该行输出“Poor QLW”（不含引号）。

输入输出样例

输入样例#1：

5 5 7
14 15 9 26 53
58 9 7 9 32
38 46 26 43 38
32 7 9 50 28
8 41 9 7 17
1 2 5 3 139
3 1 5 5 399
3 3 4 5 91
4 1 4 1 33
1 3 5 4 185
3 3 4 3 23
3 1 3 3 108

输出样例#1：

6
15
2
Poor QLW
9
1
3

输入样例#2：

1 10 7
14 15 9 26 53 58 9 7 9 32
1 2 1 9 170
1 2 1 9 171
1 5 1 7 115
1 1 1 10 228
1 4 1 4 45704571
1 1 1 1 1
1 7 1 8 16

输出样例#2：

6
7
3
10
Poor QLW
1
2

说明

【数据规模和约定】
对于10%的数据，满足R, C≤10；
对于20%的数据，满足R, C≤40；
对于50%的数据，满足R, C≤200，M≤200,000；
另有50%的数据，满足R＝1，C≤500,000，M≤20,000；
对于100%的数据，满足1≤Pi,j≤1,000，1≤Hi≤2,000,000,000。

题解

强烈谴责这种二合一题目。
第一个50%，考虑求一个前缀和，统计大于等于k的值的数字和以及个数，这个前缀和的处理是O(1000n^2)的。对于每个查询，二分取出的数中最小的数字，check的时候在矩阵中找到大于等于它的数之和，验证是否不小于定值h。注意有可能最小的数字有多个，不一定全部取，可以求一下加起来比h大了多少，减掉没用的那部分。总复杂度是O(1000n^2)。
第二个50%，矩阵变成了序列，自然对序列建主席树来查询。每次查询先判断一下右儿子够不够，不够再向左儿子递归。当递归到叶子节点的时候就是找到了最小值，要类似上面那样计算一下这个最小值要拿多少个。这一部分的复杂度是O(n \log 1000)。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

int n, m, q;

namespace Problem1 {
    const int MAXN = 205;

    int sum[MAXN][MAXN][1005];
    int p[MAXN][MAXN], cnt[MAXN][MAXN][1005];
    int x1, y1, x2, y2, h;

    inline int query(int x1, int y1, int x2, int y2, int h) {
        int l = 0, r = 1001, mid;
        while(r - l > 1) {
            mid = (l + r) >> 1;
            if(sum[x2][y2][mid] - sum[x1 - 1][y2][mid] - sum[x2][y1 - 1][mid] 
                + sum[x1 - 1][y1 - 1][mid] >= h) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if(!l) return -1;
        int rem = sum[x2][y2][l] - sum[x1 - 1][y2][l] - sum[x2][y1 - 1][l] 
                + sum[x1 - 1][y1 - 1][l] - h,
            rcnt = cnt[x2][y2][l] - cnt[x1 - 1][y2][l] - cnt[x2][y1 - 1][l] 
                + cnt[x1 - 1][y1 - 1][l];
        return rcnt - rem / l;
    }

    int main() {
        for(register int i = 1; i <= n; i++) {
            for(register int j = 1; j <= m; j++) {
                p[i][j] = readint();
            }
        }
        for(register int i = 1; i <= n; i++) {
            for(register int j = 1; j <= m; j++) {
                for(register int k = 1; k <= 1000; k++) {
                    sum[i][j][k] = sum[i][j - 1][k] + sum[i - 1][j][k] - sum[i - 1][j - 1][k];
                    cnt[i][j][k] = cnt[i][j - 1][k] + cnt[i - 1][j][k] - cnt[i - 1][j - 1][k];
                    if(p[i][j] >= k) {
                        sum[i][j][k] += p[i][j]; cnt[i][j][k]++;
                    }
                }
            }
        }
        while(q--) {
            x1 = readint(); y1 = readint(); x2 = readint(); y2 = readint(); h = readint();
            int res = query(x1, y1, x2, y2, h);
            if(res != -1) printf("%d\n", res);
            else puts("Poor QLW");
        }
        return 0;
    }
}

namespace Problem2 {
    const int MAXN = 500005;

    int p[MAXN];

    struct Node {
        int lch, rch, cnt, sum;
    } tr[MAXN * 15];
    int rt[MAXN], tot;

    inline void insert(int &o, int l, int r, int x) {
        tr[++tot] = tr[o]; o = tot;
        tr[o].cnt++; tr[o].sum += x;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(x <= mid) insert(tr[o].lch, l, mid, x);
        else insert(tr[o].rch, mid + 1, r, x);
    }

    inline int query(int o1, int o2, int l, int r, int h) {
        if(l == r) return (h + l - 1) / l;
        int mid = (l + r) >> 1, rsum = tr[tr[o2].rch].sum - tr[tr[o1].rch].sum;
        if(h <= rsum) return query(tr[o1].rch, tr[o2].rch, mid + 1, r, h);
        else return tr[tr[o2].rch].cnt - tr[tr[o1].rch].cnt 
            + query(tr[o1].lch, tr[o2].lch, l, mid, h - rsum);
    }

    int x1, y1, x2, y2, h;

    int main() {
        for(register int i = 1; i <= m; i++) {
            p[i] = readint();
            rt[i] = rt[i - 1];
            insert(rt[i], 1, 1000, p[i]);
        }
        while(q--) {
            x1 = readint(); y1 = readint(); x2 = readint(); y2 = readint(); h = readint();
            if(tr[rt[y2]].sum - tr[rt[y1 - 1]].sum < h) puts("Poor QLW");
            else printf("%d\n", query(rt[y1 - 1], rt[y2], 1, 1000, h));
        }
        return 0;
    }
}

int main() {
    n = readint(); m = readint(); q = readint();
    if(n == 1) return Problem2::main();
    else return Problem1::main();
}