题目链接
从数据范围可以看出，该题给出的数据有两种类型：
1.给一个最大 200 X 200 的矩阵。
2.给一个最长为 500000 的数列。
那么我们显然需要对这两种数据类型设计两种算法来分别解决。
1.对于 200 X 200 的矩阵，因为每本书页数不超过1000，可以用二维前缀和处理sum[i][j][k]记录 (1,1) (i, j) 这个矩阵中高大于k的书的总高度，num[i][j][k]记录(1,1) (i, j) 这个矩阵中高大于k的书的数量。然后二分至多能取的书的最小高度，换句话说，就是定一个高度，只取高于或等于这个高度的书就能满足要求，找到这个高度最高是多少，这个高度对应的书的数量，就是最少需要取得书的数量了，注意这个答案需要排除掉多余的书，比如第一组样例的第一个询问：
二分满足要求的最大高度显然是9，但是发现如果把9选完很明显浪费了，这时就要去掉多余的9，具体看代码。
2.对于第二种情况，我们发现这基本就是一个裸的主席树，那么直接上主席树就好了，当然也要注意上面提到的情况。
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; typedef long long LL; int row,col,m;struct Solve1{int w[210][210],x1,y1,x2,y2,hi,sum[210][210][1010],num[210][210][1010];int numm(int k){return num[x2][y2][k]-num[x2][y1-1][k]-num[x1-1][y2][k]+num[x1-1][y1-1][k];}int summ(int k){return sum[x2][y2][k]-sum[x2][y1-1][k]-sum[x1-1][y2][k]+sum[x1-1][y1-1][k];}int division(){int l=0,r=1000,res=-1; //用一个res=-1判断是否无解 while(l<r){int mid=(l+r+1)>>1;if(summ(mid)>=hi) res=mid,l=mid;else r=mid-1;}return res;}void solve(){for(int i=1;i<=row;i++)for(int j=1;j<=col;j++)scanf("%d",&w[i][j]);for(int k=0;k<=1000;k++)for(int i=1;i<=row;i++)for(int j=1;j<=col;j++){sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k];if(w[i][j]>=k)sum[i][j][k]+=w[i][j],num[i][j][k]+=1; //使用容斥原理求二维前缀和 }for(int i=1;i<=m;i++){scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&hi);int ans=division();if(ans==-1) printf("Poor QLW\n");else printf("%d\n",numm(ans)-(summ(ans)-hi)/ans); //去掉多余的书 }} }Solve1;struct Solve2{#define mid ((l+r)>>1)int root[500010],sum[500010<<5],num[500010<<5],L[500010<<5],R[500010<<5],tot;//为主席树开空间时一定要看准，我RE自闭。 int build(int l,int r){int id=++tot;sum[id]=0;num[id]=0;if(l>=r) return id;L[id]=build(l,mid);R[id]=build(mid+1,r);return id;}int update(int pre,int l,int r,int h){int id=++tot;sum[id]=sum[pre]+h;num[id]=num[pre]+1;L[id]=L[pre];R[id]=R[pre];if(l==h&&r==h) return id;if(h<=mid) L[id]=update(L[pre],l,mid,h);else R[id]=update(R[pre],mid+1,r,h);return id;}//前面基本都是主席树模板，ask有一点变化 int ask(int u,int v,int l,int r,int h){if(l>=r) return (h-1)/l+1; //锁定答案，但要排除多余的书 int x=sum[R[v]]-sum[R[u]];if(x>=h) return ask(R[u],R[v],mid+1,r,h); //因为要选尽可能高的书，所以看右子树能否满足 else return num[R[v]]-num[R[u]]+ask(L[u],L[v],l,mid,h-x); //如果右子树不够，由左子树来填补 }void solve(){root[0]=build(1,1000);for(int i=1,h;i<=col;i++){scanf("%d",&h);root[i]=update(root[i-1],1,1000,h);}for(int i=1,l,r,temp,hi;i<=m;i++){scanf("%d%d%d%d%d",&temp,&l,&temp,&r,&hi);if(sum[root[r]]-sum[root[l-1]]<hi) printf("Poor QLW\n");else printf("%d\n",ask(root[l-1],root[r],1,1000,hi));}} }Solve2;int main() {scanf("%d%d%d",&row,&col,&m);if(row!=1) Solve1.solve();else Solve2.solve();return 0; }