【BZOJ 1926】[Sdoi]粟粟的书架

题目来源：BZOJ 1926

思路：

考虑分成两个部分做，R=1是可以考虑用主席树维护，R,C是200的时候考虑用三维前缀和暴力。

具体的，主席树的做法与区间求第K个数类似，当时维护的权值出现的次数，现在维护的是二元组（数字出现的次数，所有数字之和）；暴力的做法是预处理 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示前i行，前j列，权值小于k的元素和， g [ i ] [ j ] [ k ] g[i][j][k] g[i][j][k]表示前i行，前j列，权值小于k的元素个数，对每一个询问暴力枚举k的值，找到第一个大于 H i H_i Hi​的输出 g [ . . . ] [ . . . ] [ . . . ] g[...][...][...] g[...][...][...]就好了。

当然，二分的时候边界注意适当的调整，有可能很多个相同的只选择一个。

代码：

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define mid ((l+r)>>1)using namespace std;const int maxn = 5e5+5;const int n = 1000;int r, c, m;int f[201][201][1001], g[201][201][1001], val[201][201];int cnt, a1[maxn];struct Tree{int num, sum;Tree* ch[2];}T[maxn*13], *root[maxn];Tree* get(){return &T[++ cnt];}void made(Tree *now, int l, int r){if(l == r) return;made(now->ch[0] = get(), l, mid);made(now->ch[1] = get(), mid+1, r);}void build(Tree* now, Tree* pre, int val, int l, int r){if(l == r) return;int wh = 1;if(val <= mid) wh = 0;now->ch[wh^1] = pre->ch[wh^1];now->ch[wh] = get();now->ch[wh]->num = pre->ch[wh]->num + 1;now->ch[wh]->sum = pre->ch[wh]->sum + val;build(now->ch[wh], pre->ch[wh], val, wh == 0 ? l : mid+1, wh == 0 ? mid : r);}int ask(Tree* fi, Tree* se, int val, int l, int r, int &sum, int &num){if(l == r){sum += se->sum - fi->sum;num += se->num - fi->num;return l;} int lch = se->ch[0]->sum - fi->ch[0]->sum;int rch = se->ch[1]->sum - fi->ch[1]->sum;if(val <= rch) return ask(fi->ch[1], se->ch[1], val, mid+1, r, sum, num);else{sum += rch, num += se->ch[1]->num - fi->ch[1]->num;return ask(fi->ch[0], se->ch[0], val-rch, l, mid, sum, num);}}int main(){scanf("%d%d%d", &r, &c, &m);if(r != 1){for(int i = 1; i <= r; i ++)for(int j = 1; j <= c; j ++){scanf("%d", &val[i][j]);for(int k = 0; k <= n; k ++){f[i][j][k] = f[i-1][j][k] + f[i][j-1][k] - f[i-1][j-1][k] + (val[i][j] >= k ? val[i][j] : 0);g[i][j][k] = g[i-1][j][k] + g[i][j-1][k] - g[i-1][j-1][k] + (val[i][j] >= k ? 1 : 0);}}for(int i = 1; i <= m; i ++){int x1, y1, x2, y2, kk, ok = 1;scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &kk);for(int j = n; j >= 0; j --){int t = f[x2][y2][j] + f[x1-1][y1-1][j] - f[x2][y1-1][j] - f[x1-1][y2][j];if(t >= kk){printf("%d\n", g[x2][y2][j] + g[x1-1][y1-1][j] - g[x2][y1-1][j] - g[x1-1][y2][j] - (t-kk)/j);ok = 0; break;}}if(ok) printf("Poor QLW\n");}return 0;}for(int i = 1; i <= c; i ++) scanf("%d", &a1[i]);root[0] = get(), made(root[0], 1, n);for(int i = 1; i <= c; i ++){root[i] = get();build(root[i], root[i-1], a1[i], 1, n);}for(int i = 1; i <= m; i ++){int a1, b1, c1, d1, val;scanf("%d%d%d%d%d", &a1, &b1, &c1, &d1, &val);int sum = 0, num = 0;int t = ask(root[b1-1], root[d1], val, 1, n, sum, num);if(sum < val){printf("Poor QLW\n"); continue;}printf("%d\n", num - (sum-val)/t);}return 0;}

如果觉得《【BZOJ 1926】[Sdoi]粟粟的书架》对你有帮助，请点赞、收藏，并留下你的观点哦！