大致题意： 问你选取一个矩形区间内至少几个数，才能使它们的和\(\ge H_i\)。
二合一
根据数据范围，比较显然能看出它是一道二合一的题目。
对于第一种情况，\(R,C\le 200\)，我们可以用前缀和+二分去做。
而对于另一种情况，\(R=1,C\le500000\)，就需要使用主席树 了。
前缀和+二分
先来讲讲第一种情况。
我们可以用\(sum_{i,j,k}\)来表示 \((1,1)\)到\((i,j)\)的矩形区间内\(\ge k\)的数的总和，然后用\(tot_{i,j,k}\)来表示 \((1,1)\)到\((i,j)\)的矩形区间内\(\ge k\)的数的个数。
这样一来，如何二分应该不用多说了吧！
直接二分\(k\)的大小即可。
主席树
显然，对于\(R=1\)，我们可以用主席树来维护。
我们可以直接在树上查询，求出最少的和\(\ge H_i\)的数的个数。
这应该是主席树比较经典的操作了。
如果不会，可以参考代码。
代码
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define P 1000
using namespace std;
int n,m;
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class Class_SumSolver//前缀和+二分
{
private:
#define N 200
#define get_val(array,x1,y1,x2,y2,v) (array[x2][y2][v]-array[x1-1][y2][v]-array[x2][y1-1][v]+array[x1-1][y1-1][v])//求出区间内的值
int a[N+5][N+5],sum[N+5][N+5][P+5],tot[N+5][N+5][P+5];
public:
inline void Solve()
{
register int i,j,k,Q,x1,y1,x2,y2,v,l,r,mid;
for(F.read(Q),i=1;i<=n;++i) for(j=1;j<=m;++j)//读入+预处理
{
for(F.read(a[i][j]),k=0;k<=a[i][j];++k) sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+a[i][j],tot[i][j][k]=tot[i-1][j][k]+tot[i][j-1][k]-tot[i-1][j-1][k]+1;
for(;k<=P;++k) sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k],tot[i][j][k]=tot[i-1][j][k]+tot[i][j-1][k]-tot[i-1][j-1][k];
}
while(Q--)
{
F.read(x1),F.read(y1),F.read(x2),F.read(y2),F.read(v);
if(get_val(sum,x1,y1,x2,y2,0)<v) {F.write_string("Poor QLW\n");continue;}//特判是否无解
for(mid=(l=0)+(r=P+1)+1>>1;l+1<r;mid=l+r+1>>1) get_val(sum,x1,y1,x2,y2,mid)>=v?l=mid:r=mid;//二分
F.write(get_val(tot,x1,y1,x2,y2,l)-(get_val(sum,x1,y1,x2,y2,l)-v)/l),F.write_char('\n');//输出答案
}
}
}SumSolver;
class Class_ChairmanTreeSolver//主席树
{
private:
#define M 500000
#define LogP 10
int a[M+5],sum[M+5];
class Class_ChairmanTree
{
private:
int n,v,tot,Root[M+5];
struct Tree
{
int Sum,Size,Son[2];
}node[P*LogP+5];
inline void Build(int l,int r,int &rt)//建树
{
if(!rt) rt=++tot;if(!(l^r)) return;
register int mid=l+r>>1;
Build(l,mid,node[rt].Son[0]),Build(mid+1,r,node[rt].Son[1]);
}
inline void upt(int l,int r,int &rt,int lst,int val)//修改
{
node[rt=++tot]=node[lst],node[rt].Sum+=val,++node[rt].Size;
if(!(l^r)) return;
register int mid=l+r>>1;
val<=mid?upt(l,mid,node[rt].Son[0],node[lst].Son[0],val):upt(mid+1,r,node[rt].Son[1],node[lst].Son[1],val);
}
inline int qry(int l,int r,int rt1,int rt2,int v)//查询
{
if(!(l^r)) return (v+l-1)/l;
register int mid=l+r>>1,t=node[node[rt2].Son[1]].Sum-node[node[rt1].Son[1]].Sum;
if(t<v) return node[node[rt2].Son[1]].Size-node[node[rt1].Son[1]].Size+qry(l,mid,node[rt1].Son[0],node[rt2].Son[0],v-t);
return qry(mid+1,r,node[rt1].Son[1],node[rt2].Son[1],v);
}
public:
inline void Init(int len) {n=len,Build(1,n,Root[0]);}
inline void Insert(int val) {++v,upt(1,n,Root[v],Root[v-1],val);}
inline int Query(int ql,int qr,int v) {return qry(1,n,Root[ql-1],Root[qr],v);}
}ChairmanTree;
public:
inline void Solve()
{
register int i,Q,x,y,v;
for(ChairmanTree.Init(P),F.read(Q),i=1;i<=m;++i) F.read(a[i]),sum[i]=sum[i-1]+a[i],ChairmanTree.Insert(a[i]);//读入，预处理前缀和，然后将该元素插入主席树
while(Q--)
{
F.read(x),F.read(x),F.read(y),F.read(y),F.read(v);
if(sum[y]-sum[x-1]<v) {F.write_string("Poor QLW\n");continue;}//特判是否无解
F.write(ChairmanTree.Query(x,y,v)),F.write_char('\n');//在主席树上查询
}
}
}ChairmanTreeSolver;
int main()
{
if(F.read(n),F.read(m),n^1) SumSolver.Solve();else ChairmanTreeSolver.Solve();
return F.end(),0;
}