BZOJ 1926
题意：见上
本题显然是两个题。
首先考虑$n,m \leq 200$的，二维前缀和记录矩形大于某数个数和和，二分查找即可
考虑$r=1$的，即用类似的方法，二分+主席树即可。
知识点
1、主席树节点数和操作次数有关，与值域无关
2、主席树边更新边合并和更新完合并两种写法不要写混
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int r, c, Q;
namespace task1 {
const int MAXN = 200 + 5;
int a[MAXN][MAXN], qzh_num[MAXN][MAXN][1000 + 5], qzh_he[MAXN][MAXN][1000 + 5];
int getNum(int x1, int y1, int x2, int y2, int k) {return qzh_num[x2][y2][k] - qzh_num[x2][y1 - 1][k] - qzh_num[x1 - 1][y2][k] + qzh_num[x1 - 1][y1 - 1][k];}
int getHe(int x1, int y1, int x2, int y2, int k) {return qzh_he[x2][y2][k] - qzh_he[x2][y1 - 1][k] - qzh_he[x1 - 1][y2][k] + qzh_he[x1 - 1][y1 - 1][k];}
int solve() {
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) scanf("%d", &a[i][j]);
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) qzh_num[i][j][a[i][j]] = 1;
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) qzh_he[i][j][a[i][j]] = a[i][j];
for (int k = 1000 - 1; k; --k)
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) qzh_num[i][j][k] += qzh_num[i][j][k + 1];
for (int k = 1000 - 1; k; --k)
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) qzh_he[i][j][k] += qzh_he[i][j][k + 1];
for (int k = 1000; k; --k)
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) qzh_num[i][j][k] += qzh_num[i - 1][j][k] + qzh_num[i][j - 1][k] - qzh_num[i - 1][j - 1][k];
for (int k = 1000; k; --k)
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) qzh_he[i][j][k] += qzh_he[i - 1][j][k] + qzh_he[i][j - 1][k] - qzh_he[i - 1][j - 1][k];
while (Q--) {
int x1, y1, x2, y2, h;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &h);
int l = 1, r = 1000 + 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (getHe(x1, y1, x2, y2, mid) >= h) {
l = mid + 1;
int tmp2 = getHe(x1, y1, x2, y2, mid + 1);
int hh = (h - tmp2) / mid + (bool)((h - tmp2) % mid);
ans = getNum(x1, y1, x2, y2, mid + 1) + hh;
} else r = mid - 1;
}
if (ans == -1) printf("Poor QLW\n"); else printf("%d\n", ans);
}
return 0;
}
}
namespace task2 {
const int MAXN = 500000 + 5, MV = 1000 + 5;
#define M ((l + r) >> 1)
int a[MAXN];
int sz, rt[MAXN], lc[MAXN * 20], rc[MAXN * 20], sumv[MAXN * 20], he[MAXN * 20];
void update(int &now, int l, int r, int x, int v, int pre) {
if (!now) now = ++sz;
sumv[now] = sumv[pre] + 1, he[now] = he[pre] + v; //
if (l == r) return ;
if (x <= M) rc[now] = rc[pre], update(lc[now], l, M, x, v, lc[pre]);
else lc[now] = lc[pre], update(rc[now], M + 1, r, x, v, rc[pre]);
}
int query(int x, int l, int r, int v) {
if (l == r) return he[x];
if (v <= M) {
return he[rc[x]] + query(lc[x], l, M, v);
} else {
return query(rc[x], M + 1, r, v);
}
}
int queryNum(int x, int l, int r, int v) {
if (l == r) return sumv[x];
if (v <= M) {
return sumv[rc[x]] + queryNum(lc[x], l, M, v);
} else {
return queryNum(rc[x], M + 1, r, v);
}
}
int solve() {
for (int i = 1; i <= c; ++i) scanf("%d", &a[i]), update(rt[i], 1, MV, a[i], a[i], rt[i - 1]);
//query(rt[3], 1, MV, 9);
while (Q--) {
int x1, y1, x2, y2, h;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &h);
int l = 1, r = 1000 + 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(rt[y2], 1, MV, mid) - query(rt[y1 - 1], 1, MV, mid) >= h) {
l = mid + 1;
int tmp2 = query(rt[y2], 1, MV, mid + 1) - query(rt[y1 - 1], 1, MV, mid + 1);
int hh = (h - tmp2) / mid + (bool)((h - tmp2) % mid);
ans = queryNum(rt[y2], 1, MV, mid + 1) - queryNum(rt[y1 - 1], 1, MV, mid + 1) + hh;
} else r = mid - 1;
}
if (ans == -1) printf("Poor QLW\n"); else printf("%d\n", ans);
}
return 0;
}
}
void clean() {}
int solve() {
clean();
cin >> r >> c >> Q;
if (r == 1) task2::solve(); else task1::solve();
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
