#二分，主席树#洛谷 2468 粟粟的书架

本文主要是介绍#二分，主席树#洛谷 2468 粟粟的书架，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出一个矩阵，问一个子矩阵中至少要多少个数才能使和 $\geq h$ ，多组数据，分成 $1\leq r,c\leq 200和r=1,1\leq c\leq 500000$

分析

这显然是一道以二分为核心的题目，但是这道题目二合一，对于 $r\neq 1$ 维护二维前缀大于等于某个值的数量以及它们的和，最后答案因为会有很多个相同的结果，所以要减掉，对于 $r = 1$ 用主席树同样维护，其实也和 $r\neq 1$ 的答案求法有同样的道理

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=500011;
struct rec{int ws,wr,ls,rs;}b[N<<4];
int root[N],sw[201][201][1001],mx,sr[201][201][1001],tot,a[201][201],c[N],n,m,Q;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline signed max(int a,int b){return a>b?a:b;}
inline signed get_sw(int x1,int y1,int x2,int y2,int now){return sw[x2][y2][now]-sw[x1-1][y2][now]-sw[x2][y1-1][now]+sw[x1-1][y1-1][now];}
inline signed get_sr(int x1,int y1,int x2,int y2,int now){return sr[x2][y2][now]-sr[x1-1][y2][now]-sr[x2][y1-1][now]+sr[x1-1][y1-1][now];}
inline void update(int &rt,int l,int r,int x){b[++tot]=b[rt],rt=tot,b[rt].ws+=x,++b[rt].wr;if (l==r) return; rr int mid=(l+r)>>1;if (x<=mid) update(b[rt].ls,l,mid,x);else update(b[rt].rs,mid+1,r,x);
}
inline signed query(int rt1,int rt2,int l,int r,int h){rr int ans=0;while (l<r){rr int mid=(l+r)>>1,now=b[b[rt2].rs].ws-b[b[rt1].rs].ws;if (now<=h) ans+=b[b[rt2].rs].wr-b[b[rt1].rs].wr,h-=now,r=mid,rt2=b[rt2].ls,rt1=b[rt1].ls;else l=mid+1,rt1=b[rt1].rs,rt2=b[rt2].rs;}ans+=(h+l-1)/l;return ans;
}
signed main(){n=iut(),m=iut(),Q=iut();if (n^1){for (rr int i=1;i<=n;++i)for (rr int j=1;j<=m;++j) mx=max(mx,a[i][j]=iut());for (rr int k=0;k<=mx;++k)for (rr int i=1;i<=n;++i)for (rr int j=1;j<=m;++j)sw[i][j][k]=sw[i-1][j][k]+sw[i][j-1][k]-sw[i-1][j-1][k]+(a[i][j]>=k?a[i][j]:0),sr[i][j][k]=sr[i-1][j][k]+sr[i][j-1][k]-sr[i-1][j-1][k]+(a[i][j]>=k);while (Q--){rr int x1=iut(),y1=iut(),x2=iut(),y2=iut(),h=iut();if (get_sw(x1,y1,x2,y2,0)<h) printf("Poor QLW");else{rr int l=0,r=mx;while (l<r){rr int mid=(l+r+1)>>1;if (get_sw(x1,y1,x2,y2,mid)>=h) l=mid;else r=mid-1;}print(get_sr(x1,y1,x2,y2,l)-(get_sw(x1,y1,x2,y2,l)-h)/l);}putchar(10);}}else{for (rr int i=1;i<=m;++i) mx=max(mx,c[i]=iut());for (rr int i=1;i<=m;++i) update(root[i]=root[i-1],1,mx,c[i]);while (Q--){rr int x1=iut(),y1=iut(),x2=iut(),y2=iut(),h=iut();if (b[root[y2]].ws-b[root[y1-1]].ws<h) printf("Poor QLW");else print(query(root[y1-1],root[y2],1,mx,h));putchar(10);}}return 0;
}