题目描述
幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j页厚。
粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。不过她发现，如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第i天指定的那个苹果，只要她脚下放置书的总页数之和不低于Hi，就一定能够摘到。
由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形，第i天给定区域的左上角是上数第x1i行的左数第y1i本书，右下角是上数第x2i行的左数第y2i本书。换句话说，粟粟在这一天，只能在这﹙x2i－x1i＋1﹚×﹙y2i－y1i＋1﹚本书中挑选若干本垫在脚下，摘取苹果。
粟粟每次取书时都能及时放回原位，并且她的书架不会再撤下书目或换上新书，摘苹果的任务会一直持续M天。给出每本书籍的页数和每天的区域限制及采摘要求，请你告诉粟粟，她每天至少拿取多少本书，就可以摘到当天指定的苹果。
输入格式
输入文件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”（不含引号）。
输入输出样例
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
6 15 2 Poor QLW 9 1 3
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
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%的数据用二分加前缀和，后50%的数据用主席树维护就好了。
我们可以很容易看出，要使得数量最少，那么我们每次取应该取页数最大的那本书。
前50%的数据我们使用两个三维数组前缀和维护前k大的总和以及数量，最后二分答案即可。
二维前k大值之和的维护如下：
for (int i=1; i<=n; i++) for (int j = 1; j <= m; j++) { in(a[i][j]); if (vis[a[i][j]]) continue; vis[a[i][j]]=1; lis[++use]=a[i][j]; } sort(lis+1,lis+1+use,cmp); for (int k=1; k<=use; k++) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { num[i][j][k] = num[i - 1][j][k] + num[i][j - 1][k] - num[i - 1][j - 1][k]; sum[i][j][k] = sum[i - 1][j][k] + sum[i][j - 1][k] - sum[i - 1][j - 1][k]; if (a[i][j] < lis[k]) continue; num[i][j][k]++; sum[i][j][k]+=a[i][j]; } }
接下来就是无脑二分了，不过二分完之后由于最后一种页数的书可能会多出来，所以我们需要特判最后一种页数的情况：
int pu=sum[x2][y2][ans-1]-sum[x2][y1-1][ans-1]-sum[x1-1][y2][ans-1]+sum[x1-1][y1-1][ans-1];//ans是二分完之后的最小的页数值 int p=(h-pu)/lis[ans];//总值-前k-1大之和，剩下的就是需要用第k(ans)大的数来填补的空缺 if ((h-pu)%lis[ans]) p++; int cnt=num[x2][y2][ans-1]-num[x2][y1-1][ans-1]-num[x1-1][y2][ans-1]+num[x1-1][y1-1][ans-1];//前k-1大的数的数量 printf ("%d\n",p+cnt);
于是前50%的数据就很快解决了：
inline int ok(int x1,int y1,int x2,int y2,int x,int h) { int tot=sum[x2][y2][x]-sum[x2][y1-1][x]-sum[x1-1][y2][x]+sum[x1-1][y1-1][x]; if (tot<h) return 0; return 1; } inline void work1(int n,int m,int q) { int use=0; for (int i=1; i<=n; i++) for (int j = 1; j <= m; j++) { in(a[i][j]); if (vis[a[i][j]]) continue; vis[a[i][j]]=1; lis[++use]=a[i][j]; } sort(lis+1,lis+1+use,cmp); for (int k=1; k<=use; k++) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { num[i][j][k] = num[i - 1][j][k] + num[i][j - 1][k] - num[i - 1][j - 1][k]; sum[i][j][k] = sum[i - 1][j][k] + sum[i][j - 1][k] - sum[i - 1][j - 1][k]; if (a[i][j] < lis[k]) continue; num[i][j][k]++; sum[i][j][k]+=a[i][j]; } } while(q--){ int x1,x2,y1,y2,h; in(x1);in(y1);in(x2);in(y2); in(h); int l=1,r=use,mid; int ans=1005; while (l<=r){ mid=(l+r)>>1; if (ok(x1,y1,x2,y2,mid,h)){ ans=mid; r=mid-1; } else l=mid+1; } if (ans==1005) printf ("Poor QLW\n"); else { int pu=sum[x2][y2][ans-1]-sum[x2][y1-1][ans-1]-sum[x1-1][y2][ans-1]+sum[x1-1][y1-1][ans-1]; int p=(h-pu)/lis[ans]; if ((h-pu)%lis[ans]) p++; int cnt=num[x2][y2][ans-1]-num[x2][y1-1][ans-1]-num[x1-1][y2][ans-1]+num[x1-1][y1-1][ans-1]; printf ("%d\n",p+cnt); } } }
后面的50%的数据我们想一下，如果用前50%的方法做的话，维护5e5 的序列然后在枚举1e3的页数。。。。果断T了
那么我们想一想，维护前k大的序列之和。。。主席树不是挺OK的吗，m*log(1000)的复杂度，完全OK。
套个主席树（区间第k大）的update的板子，然后改一改query部分就好了：
inline int update(int l,int r,int pos,int val,int ed) { int rt=++tree_sum; int mid=(l+r)>>1; tree[rt].l=tree[ed].l;tree[rt].r=tree[ed].r; tree[rt].size=tree[ed].size+1; tree[rt].sum=tree[ed].sum+val; if (l==r) return rt; if (mid>=pos) tree[rt].l=update(l,mid,pos,val,tree[ed].l); else tree[rt].r=update(mid+1,r,pos,val,tree[ed].r); return rt; } inline int query(int l,int r,int L,int R,int val) { int ans=0; while (l<r){ int mid=(l+r)>>1; int x=tree[tree[R].r].sum-tree[tree[L].r].sum; if (x<val){ ans+=tree[tree[R].r].size-tree[tree[L].r].size; val-=x;r=mid,L=tree[L].l;R=tree[R].l; } else l=mid+1,L=tree[L].r,R=tree[R].r; } ans+=(val+l-1)/l; return ans; }
update部分就不多说了，前一篇博客刚好讲到了，遍历经过的所有路径都会有所修改。
至于query部分，这里写的是非递归方式，当然递归的方式可能比较好理解。我们的每个树的节点分为左右节点，由于是先取大的，所以我们先判断右子树的值是否大于需要的高度，如果否，说明需要更多的书，那么我们的ans值就需要+右子树的大小，然后往左子树递归，如果是的话我们直接往右子树递归就好了。最后所得的val的值就是剩下第k大的值所要填补的空缺。为了保证向上取整，我们可以先把val+l（第k大的值）-1再除以l就好了
以下是AC代码：
#include <bits/stdc++.h> using namespace std; const int mac=5e5+10; int a[205][205],sum[205][205][1005],num[205][205][1005]; int vis[1005],lis[1005]; struct node { int sum,size,l,r; }tree[mac*11]; inline void in(int &x) { int f=0; char ch=getchar(); while (ch>'9' || ch<'0') ch=getchar(); while (ch>='0' && ch<='9') f=(f<<1)+(f<<3)+ch-'0',ch=getchar(); x=f; } inline int ok(int x1,int y1,int x2,int y2,int x,int h) { int tot=sum[x2][y2][x]-sum[x2][y1-1][x]-sum[x1-1][y2][x]+sum[x1-1][y1-1][x]; if (tot<h) return 0; return 1; } inline bool cmp(int x,int y) { return x>y; } int tree_sum=0,ver[mac]; inline int build(int l,int r) { int rt=++tree_sum; if (l==r) return rt; int mid=(l+r)>>1; tree[rt].l=build(l,mid); tree[rt].r=build(mid+1,r); return rt; } inline int update(int l,int r,int pos,int val,int ed) { int rt=++tree_sum; int mid=(l+r)>>1; tree[rt].l=tree[ed].l;tree[rt].r=tree[ed].r; tree[rt].size=tree[ed].size+1; tree[rt].sum=tree[ed].sum+val; if (l==r) return rt; if (mid>=pos) tree[rt].l=update(l,mid,pos,val,tree[ed].l); else tree[rt].r=update(mid+1,r,pos,val,tree[ed].r); return rt; } inline int query(int l,int r,int L,int R,int val) { int ans=0; while (l<r){ int mid=(l+r)>>1; int x=tree[tree[R].r].sum-tree[tree[L].r].sum; if (x<val){ ans+=tree[tree[R].r].size-tree[tree[L].r].size; val-=x;r=mid,L=tree[L].l;R=tree[R].l; } else l=mid+1,L=tree[L].r,R=tree[R].r; } ans+=(val+l-1)/l; return ans; } inline void work1(int n,int m,int q) { int use=0; for (int i=1; i<=n; i++) for (int j = 1; j <= m; j++) { in(a[i][j]); if (vis[a[i][j]]) continue; vis[a[i][j]]=1; lis[++use]=a[i][j]; } sort(lis+1,lis+1+use,cmp); for (int k=1; k<=use; k++) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { num[i][j][k] = num[i - 1][j][k] + num[i][j - 1][k] - num[i - 1][j - 1][k]; sum[i][j][k] = sum[i - 1][j][k] + sum[i][j - 1][k] - sum[i - 1][j - 1][k]; if (a[i][j] < lis[k]) continue; num[i][j][k]++; sum[i][j][k]+=a[i][j]; } } while(q--){ int x1,x2,y1,y2,h; in(x1);in(y1);in(x2);in(y2); in(h); int l=1,r=use,mid; int ans=1005; while (l<=r){ mid=(l+r)>>1; if (ok(x1,y1,x2,y2,mid,h)){ ans=mid; r=mid-1; } else l=mid+1; } if (ans==1005) printf ("Poor QLW\n"); else { int pu=sum[x2][y2][ans-1]-sum[x2][y1-1][ans-1]-sum[x1-1][y2][ans-1]+sum[x1-1][y1-1][ans-1]; int p=(h-pu)/lis[ans]; if ((h-pu)%lis[ans]) p++; int cnt=num[x2][y2][ans-1]-num[x2][y1-1][ans-1]-num[x1-1][y2][ans-1]+num[x1-1][y1-1][ans-1]; printf ("%d\n",p+cnt); } } } inline void work2(int n,int m,int q) { ver[0]=build(1,1000); for (int i=1; i<=m; i++){ int x;in(x); ver[i]=update(1,1000,x,x,ver[i-1]); } while (q--){ int x1,x2,y1,y2,h; in(x1);in(y1);in(x2);in(y2);in(h); int ans=0; if (tree[ver[y2]].sum-tree[ver[y1-1]].sum<h) {printf ("Poor QLW\n");continue;} ans=query(1,1000,ver[y1-1],ver[y2],h); printf("%d\n",ans); } } int main() { //freopen("in.txt","r",stdin); int n,m,q; in(n);in(m);in(q); if (n>1) work1(n,m,q); else work2(n,m,q); return 0; }