简化题意。
有一个n*m的矩阵,q个询问,求问,在每个矩阵中最少取多少个数,使得和至少为h。
观察数据范围,我们惊讶地发现这一题不可避免地要做两次。
因为,n,m<=200显然不是用普通的数据结构可以维护的。我们考虑使用\(cnt_{i,j,k}\)表示大于k的数的数量,\(sm_{i,j,k}\)表示大于k的数的总和。然后二分这个k来求解即可。
对于n==1的情况,我们很容易可以想到维护一棵权值主席树。对于每一个询问,我们在两棵权值线段树上二分然后求差。
#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int n,m,q;
int b[205][205],cnt[205][205][1005],sm[205][205][1005];
//不需要开longlong!!!MLE警告!!!
inline long long cntQry(int X1,int Y1,int X2,int Y2,int K){
return cnt[X2][Y2][K]-cnt[X1-1][Y2][K]-cnt[X2][Y1-1][K]+cnt[X1-1][Y1-1][K];
}
inline long long smQry(int X1,int Y1,int X2,int Y2,int K){
return sm[X2][Y2][K]-sm[X1-1][Y2][K]-sm[X2][Y1-1][K]+sm[X1-1][Y1-1][K];
}
inline void slv2(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&b[i][j]);
}
}
for(int k=0;k<=1000;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(int)(b[i][j]>=k);
sm[i][j][k]=sm[i-1][j][k]+sm[i][j-1][k]-sm[i-1][j-1][k]+(int)(b[i][j]>=k)*b[i][j];
}
}
}
long long l,r,mid,h,ans;
int X1,X2,Y1,Y2;
while(q--){
l=0,r=1001,ans=-1;
scanf("%d%d%d%d%lld",&X1,&Y1,&X2,&Y2,&h);
while(l<=r){
mid=(l+r)>>1,smQry(X1,Y1,X2,Y2,mid)>=h?(ans=mid,l=mid+1):r=mid-1;
}
(~ans)?(printf("%lld\n",cntQry(X1,Y1,X2,Y2,ans)-(smQry(X1,Y1,X2,Y2,ans)-h)/ans)):(puts("Poor QLW"));
}
// 对于同一个k可能有多个值,而可能只需要选取部分。
}
const int MAXN2=10000005;
int a[MAXN2];
//数组大小别算错
class ChairmanTree{
private:
class Node{
public:
int l;
int r;
int fa;
int sz;
int sm;
};
Node tr[MAXN2];
int cnt,rt[MAXN2];
inline void build(int LST,int &NW,int L,int R,int V){
NW=++cnt;tr[NW].sz=tr[LST].sz+1;tr[NW].sm=tr[LST].sm+V;
if(L==R){return;}
MID>=V?(build(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(build(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
//如果值小等于MID。那么就更新右边的值;否则更新左边的值。一定要注意判断V==MID时的情况。
//如果更新的是右边的值,那么就把右边的节点与上一个版本的右边的节点一并下传,并修改本节点的左节点;否则反之。
}
//从根往下搜索。注意减去的应当是右节点的值。
inline int qry(int A,int B,int L,int R,int V){
int RT=0;
while(L<R){(tr[tr[B].r].sm-tr[tr[A].r].sm)>V?(L=MID+1,B=tr[B].r,A=tr[A].r):(RT+=tr[tr[B].r].sz-tr[tr[A].r].sz,V-=(tr[tr[B].r].sm-tr[tr[A].r].sm),R=MID,B=tr[B].l,A=tr[A].l);}
//同理,对于等于的情况也应当特别注意。
return RT+(V+L-1)/(L);
//剩下的部分应该全部由大小为R的这些东西,也就是当前点的值来处理掉。故而要加上(V+L-1)/(L)
}
public:
inline void ADD(int VER,int X){
build(rt[VER-1],rt[VER],1,1000,X);
}
inline int QUREY(int LVER,int RVER,int X){
return qry(rt[LVER-1],rt[RVER],1,1000,X);
}
inline int SUM(int L,int R){
return tr[rt[R]].sm-tr[rt[L-1]].sm;
}
inline void INIT(){
cnt=0;
}
};
ChairmanTree T;
inline void slv1(){
T.INIT();
for(int i=1;i<=m;++i){
scanf("%d",&a[i]);
T.ADD(i,a[i]);
}
int l,r,tmp,x;
while(q--){
scanf("%d%d%d%d%d",&tmp,&l,&tmp,&r,&x);
if(T.SUM(l,r)<x){
puts("Poor QLW");
continue;
}
printf("%d\n",T.QUREY(l,r,x));
}
}
void init(){
scanf("%d%d%d",&n,&m,&q);
n==1?slv1():slv2();
}
int main(){
init();
return 0;
}