本以为是线段树套主席书 不过看数据做题，大数据只有一条线。。 二分一个厚度直接大数据主席书 小数据暴力dp
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<iostream> #define mid (l+r>>1) using namespace std; const int M=1000010; int n,m,root[M],tot=0,a[2][M],q,b[201][201],maxn,sum[201][201][1010],num[201][201][1001]; struct OL_SEG{ int l,r,num,sum;OL_SEG(){l=r=num=sum=0;} }T[M]; void update(int o){T[o].sum=T[T[o].l].sum+T[T[o].r].sum;} void modify(int &o,int pre,int l,int r,int ins){ o=++tot;T[o]=T[pre];T[o].num++; if(l==r) {T[o].sum=T[o].num*l;return ;} if(ins<=mid)modify(T[o].l,T[pre].l,l,mid,ins); else modify(T[o].r,T[pre].r,mid+1,r,ins); update(o); } int query(int pre,int now,int l,int r,int ql,int qr) { if(l>qr||r<ql) return 0; if(ql<=l&&r<=qr) return T[now].sum-T[pre].sum; return query(T[pre].l,T[now].l,l,mid,ql,qr)+query(T[pre].r,T[now].r,mid+1,r,ql,qr); } int query2(int pre,int now,int l,int r,int ql,int qr) { if(l>qr||r<ql) return 0; if(ql<=l&&r<=qr) return T[now].num-T[pre].num; return query2(T[pre].l,T[now].l,l,mid,ql,qr)+query2(T[pre].r,T[now].r,mid+1,r,ql,qr); } int ask(int x,int y,int xx,int yy,int w){return sum[xx][yy][w]-sum[x][yy][w]-sum[xx][y][w]+sum[x][y][w];} int ask2(int x,int y,int xx,int yy,int w){return num[xx][yy][w]-num[x][yy][w]-num[xx][y][w]+num[x][y][w];} int main(){ scanf("%d%d%d",&n,&m,&q); if(n==1){for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),modify(root[j],root[j-1],0,1000,a[i][j]); while(q--){int x,y,xx,yy,h; scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&h); int l=0,r=10000000; while(l<=r){ if(query(root[y-1],root[yy],0,1000,mid,1000)>=h) l=mid+1; else r=mid-1; } if(!l) {printf("Poor QLW\n");continue;} int w1=query(root[y-1],root[yy],0,1000,l-1,1000),w2=query2(root[y-1],root[yy],0,1000,l-1,1000); while(w1-l+1>=h)w1-=l-1,w2--; printf("%d\n",w2); } }else{ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&b[i][j]),maxn=max(maxn,b[i][j]); for(int i=0;i<=maxn;i++)for(int j=1;j<=n;j++)for(int k=1;k<=m;k++) sum[j][k][i]=sum[j][k-1][i]+sum[j-1][k][i]-sum[j-1][k-1][i]+((b[j][k]>=i)?b[j][k]:0), num[j][k][i]=num[j][k-1][i]+num[j-1][k][i]-num[j-1][k-1][i]+((b[j][k]>=i)?1:0); while(q--){int x,y,xx,yy,h; scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&h); int l=0,r=maxn+1; while(l<=r){ if(ask(x-1,y-1,xx,yy,mid)>=h) l=mid+1; else r=mid-1; } if(!l) {printf("Poor QLW\n");continue;} int w1=ask(x-1,y-1,xx,yy,l-1),w2=ask2(x-1,y-1,xx,yy,l-1); while(w1-l+1>=h)w1-=l-1,w2--; printf("%d\n",w2); } } }