Irelia

Irelia

逝去的是刀锋,不变的是意志

题解 P2468 【[SDOI2010]粟粟的书架】

posted on 2019-08-12 10:45:13 | under 题解 |

模拟赛,本来奔着最多70写的,结果A了

解题思路

  • 看到鬼畜的数据点分布,我们可以猜到这道题是两道题捏到一起的(

  • 对于后 $50\%$ ,是一维数据。考虑把 $1e3$ 的值域看做常数,我们可以使用莫队,维护一个范围是 $1000$ 的桶,每次统计答案时暴力从 $1000$ 往回扫,复杂度 $m \sqrt n \times \text{最大1000的“常数”}$

  • 对于前 $50\%$ ,考虑到范围是 $200 \times 200$ ,继续把 $1e3$ 的值域看做常数,开 $1000$ 的桶存数,暴力扫一遍给定长方形,然后从 $1000$ 往回扫桶,复杂度 $m n^2 \times \text{最大1000的“常数”}$

代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using std::sort;
using std::min;
using std::max;
typedef long long LL;

int n, m;

void Init() {
    std::cin >> n >> m;
}

namespace Solution1{
    const int MAXN = 5e5 + 5;
    const int MAXNUM = 1e3 + 5;
    const int MAXQ = 2e4 + 5;

    int cnt[MAXNUM], a[MAXN], len;
    LL ans[MAXQ];
    int q;
    LL sum;

    struct Query{
        int l, r, id;
        LL h;
    }qs[MAXQ];

    int Comp(const Query &a, const Query &b) {
        if (a.l / len != b.l / len) return a.l < b.l;
        if (a.l / len % 2 == 1) return a.r < b.r;
        else return a.r > b.r;
    }

    void Add(int x) {
        cnt[x]++;
        sum += x;
    }

    void Del(int x) {
        cnt[x]--;
        sum -= x;
    }

    void Work() {
        std::cin >> q;
        for (int i = 1; i <= m; i++) std::cin >> a[i];
        int tmp;
        for (int i = 1; i <= q; i++) {
            std::cin >> tmp >> qs[i].l >> tmp >> qs[i].r >> qs[i].h;
            qs[i].id = i;
        }
        len = sqrt(m);
        sort(qs + 1, qs + q + 1, Comp);
        int nl = 1, nr = 0;
        for (int i = 1; i <= q; i++) {
            int l = qs[i].l, r = qs[i].r, id = qs[i].id;
            // std::cerr << l << " " << r << " " << id << "\n";
            LL h = qs[i].h;
            while (nl < l) {
                Del(a[nl]);
                nl++;
            }
            while (nl > l) {
                nl--;
                Add(a[nl]);
            }
            while (nr < r) {
                nr++;
                Add(a[nr]);
            }
            while (nr > r) {
                Del(a[nr]);
                nr--;
            }
            // std::cerr << "###" << "\n";
            // std::cerr << l << " " << r << " " << "\n";
            // for (int i = 1; i <= 1000; i++) std::cerr << cnt[i] << " ";
            // std::cerr << "###" << "\n";
            if (sum < h) {
                ans[id] = -1;
                continue;
            }
            for (int j = 1000; j; j--) {
                if (cnt[j] == 0) continue;
                if (1LL * j * cnt[j] < h) {
                    h -= 1LL * j * cnt[j];
                    ans[id] += cnt[j];
                } else {
                    // std::cerr << "*";
                    LL tmp;
                    if (h % j == 0) tmp = h / j;
                    else tmp = h / j + 1;
                    // std::cerr << tmp;
                    ans[id] += tmp;
                    // std::cerr << ans[id];
                    break;
                }
            }
        }
        for (int i = 1; i <= q; i++) {
            if (ans[i] == -1) std::cout << "Poor QLW" << "\n";
            else std::cout << ans[i] << "\n";
        }
    }
}

namespace Solution2{
    const int MAXN = 205;
    const int MAXNUM = 1e3 + 5;

    int q;
    int cnt[MAXNUM];
    int a[MAXN][MAXN];

    void Work() {
        std::cin >> q;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                std::cin >> a[i][j];
            }
        }
        int xl, xr, yl, yr;
        LL h;
        for (int i = 1; i <= q; i++) {
            std::cin >> xl >> yl >> xr >> yr >> h;
            LL ans = 0, sum = 0;
            memset(cnt, 0, sizeof(cnt));
            for (int j = xl; j <= xr; j++) {
                for (int k = yl; k <= yr; k++) {
                    cnt[a[j][k]]++;
                    sum += a[j][k];
                }
            }
            if (sum < h) {
                std::cout << "Poor QLW" << "\n";
                continue;
            }
            for (int j = 1000; j; j--) {
                if (cnt[j] == 0) continue;
                if (1LL * j * cnt[j] < h) {
                    h -= 1LL * j * cnt[j];
                    ans += cnt[j];
                } else {
                    LL tmp;
                    if (h % j == 0) tmp = h / j;
                    else tmp = h / j + 1;
                    ans += tmp;
                    break;
                }
            }
            std::cout << ans << "\n";
        }
    }
}

int main() {
    Init();
    if (n == 1) Solution1::Work();
    else Solution2::Work();
    return 0;
}