题解 P2468 【[SDOI2010]粟粟的书架】
Ireliaღ
2019-08-12 10:45:13
~~模拟赛，本来奔着最多70写的，结果A了~~
## 解题思路
- 看到鬼畜的数据点分布，我们可以猜到这道题是两道题捏到一起的(
- 对于后$50\%$，是一维数据。~~考虑把$1e3$的值域看做常数~~，我们可以使用莫队，维护一个范围是$1000$的桶，每次统计答案时暴力从$1000$往回扫，复杂度$m \sqrt n + m \times \text{最大1000的“常数”}$
- 对于前$50\%$，考虑到范围是$200 \times 200$，~~继续把$1e3$的值域看做常数~~，开$1000$的桶存数，暴力扫一遍给定长方形，然后从$1000$往回扫桶，复杂度$m n^2 + m \times \text{最大1000的“常数”}$
## 代码
```cpp
// 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;
}
```