关键词：
题面见https://www.luogu.org/problemnew/show/P2468
然后这道题属于合二为一题，看一眼数据范围就能发现
首先我们先考虑50分，二维前缀和维护一下（反正我不记得公式，手推了半天）
tot[i][j][k]表示矩阵（1,1）到（i，j）中数值大等于k的总和
num[i][j][k]表示矩阵（1,1）到（i，j）中数值大等于k的个数
那么做法也就显而易见了，二分k的值进行check
最后注意一个小问题，就是有可能一个k值有多个点，而我不需要全选就能满足条件，这个可以自行理解一下
后百分之五十，一开始口胡了一个一维前缀和的做法，貌似是两个log，然而我在学可持久化数据结构，不能偷懒
思考了一下，开一棵权值线段树，把它变成主席树，根x代表插入了第x个数后的情况
然后建树，更新都是裸的操作
关于查询我的想法我写在了代码里，想不通的可以看一下
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; inline int read() int w=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) if(ch==‘-‘) f=-1; ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) w=(w<<3)+(w<<1)+ch-48; ch=getchar(); return w*f; int n,m,q,a[210][210],tot[210][210][1010],num[210][210][1010],ans,cnt,root[5000010],b[5000010]; int get_sum(int x1,int y1,int x2,int y2,int k,int f) if(f==1)return tot[x2][y2][k]-tot[x2][y1-1][k]-tot[x1-1][y2][k]+tot[x1-1][y1-1][k]; else return num[x2][y2][k]-num[x2][y1-1][k]-num[x1-1][y2][k]+num[x1-1][y1-1][k]; inline void work2()//二维前缀和大力维护，口胡了一下写在上面了，就不多解释了，着重看主席树 int i,j,k,maxx=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]=read();maxx=max(maxx,a[i][j]); for(k=0;k<=maxx;k++) for(i=1;i<=n;i++) for(j=1;j<=m;j++) tot[i][j][k]=tot[i-1][j][k]+tot[i][j-1][k]-tot[i-1][j-1][k]+(a[i][j]>=k)*a[i][j]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+(a[i][j]>=k); while(q--) int x1,y1,x2,y2,h; x1=read();y1=read();x2=read();y2=read();h=read(); if(get_sum(x1,y1,x2,y2,0,1)<h) puts("Poor QLW"); else int l=0,r=maxx+1;ans=-1; while(l<=r) int mid=(l+r)>>1; if(get_sum(x1,y1,x2,y2,mid,1)>=h) ans=mid;l=mid+1; else r=mid-1; printf("%d ",get_sum(x1,y1,x2,y2,ans,2)-(get_sum(x1,y1,x2,y2,ans,1)-h)/ans); struct Node int ls,rs,sum,size; st[50000010]; inline int build(int l,int r) int pos=cnt++; if(l==r) return pos; int mid=(l+r)>>1; st[pos].ls=build(l,mid); st[pos].rs=build(mid+1,r); return pos; //常规建树 inline int update(int tim,int l,int r,int x)//tim表示历史版本，l,r为范围，x为我当前插入的数 int pos=cnt++; st[pos]=st[tim];st[pos].size++;st[pos].sum+=x;//这个节点的size+1,sum+=x if(l==r) return pos;//到叶子了，大力返回就好 int mid=(l+r)>>1; if(x<=mid) st[pos].ls=update(st[tim].ls,l,mid,x); else st[pos].rs=update(st[tim].rs,mid+1,r,x); return pos; inline int query(int l,int r,int fir,int sec,int w)//具体解释见下方 if(l==r) return (w-1)/l+1;//可能不会整除，就这么处理一下就好了 int mid=(l+r)>>1;int x=st[st[sec].rs].sum-st[st[fir].rs].sum; if(w<=x) return query(mid+1,r,st[fir].rs,st[sec].rs,w); else return st[st[sec].rs].size-st[st[fir].rs].size+query(l,mid,st[fir].ls,st[sec].ls,w-x); /* 这棵主席树是基于权值线段树的，权值的范围只有1k 主席树维护了历史版本的权值线段树上的size和sum 然后关于建树和更新都没什么新意 查询这个我一开始不能很好的理解，那么我现在稍微解释一下我的思路 首先l,r,fir,sec,w分别表示区间，版本号，还需要多少值 然后大多数题查询的时候都是向左子树查一下，比一下大小 这里查右子树是因为这是一棵权值线段树，我们希望尽量少地选点，也就意味着选的数要尽可能大 那么能选右子树（也就是值更大的点），当然选大的啊 如果右子树总和够，就往右子树走，不够的话，算上右子树，往左子树走 */ inline void work1() int maxw=-1e9-7; for(int i=1;i<=m;i++) b[i]=read(),maxw=max(b[i],maxw); root[0]=build(1,maxw+10); for(int i=1;i<=m;i++) root[i]=update(root[i-1],1,maxw,b[i]); for(int i=1;i<=q;i++) int y1,y2,h;y1=read(),y1=root[read()-1],y2=read(),y2=root[read()],h=read(); if(st[y2].sum-st[y1].sum<h)puts("Poor QLW");continue; printf("%d ",query(1,maxw,y1,y2,h)); int main() n=read();m=read();q=read(); if(n!=1)//合二为一辣鸡题 work2(); else work1(); return 0;
1926:[sdoi2010]粟粟的书架
1926:[Sdoi2010]粟粟的书架TimeLimit: 30Sec MemoryLimit: 552MBSubmit: 807 Solved: 321[Submit][Status][Discuss]Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢 查看详情
bzoj1926:[sdoi2010]粟粟的书架
1926:[Sdoi2010]粟粟的书架TimeLimit:30Sec MemoryLimit:552MBSubmit:1013 Solved:396[Submit][Status][Discuss]Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟... 查看详情
bzoj1926sdoi2010粟粟的书架[主席树]
粟粟的书架TimeLimit: 30Sec MemoryLimit: 552MB[Submit][Status][Discuss]Description 幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。 粟粟家中有一个R行C列... 查看详情
[sdoi2010]粟粟的书架(代码片段)
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有P... 查看详情
sdoi2010粟粟的书架(代码片段)
传送门代码1#include<iostream>2#include<cstring>3#include<cstdio>4#include<algorithm>5#include<math.h>6#definemaxn5000057usingnamespacestd;8intR,C,M;9intcont[1005];10inthe[205] 查看详情
bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的... 查看详情
刷题bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有P... 查看详情
[sdoi2010]粟粟的书架(代码片段)
[SDOI2010]粟粟的书架题意：一个R*C的矩阵，每个位置都有个数page[ij]，现在选定一个小矩阵范围(给左上角坐标，和右下角坐标)，问这个范围内的数总和是否大于h，如果大于h的话最少选几个数aij对于50%的数... 查看详情
ac日记——[sdoi2010]粟粟的书架bzoj1926
1926 思路： 主席树+二分水题； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn500005#definemaxr205#definemaxn_maxn*13#defineFalseAns"PoorQLW"intn,m,q,lc[maxn_],rc[maxn_],num[maxn_],ci[max 查看详情
bzoj1926[sdoi2010]粟粟的书架主席树+二分+前缀和
题目幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j... 查看详情
bzoj1926[sdoi2010]粟粟的书架
题解：这是两道题前50%:发现p[i][j]很小，于是记录f[i][j][k]表示（1，1）~（i，j）这个子矩阵内>=k的书的总高度,g[i][j][k]记录本数查询是二分答案就好了后50%:主席树，右子树够了就向右走，否则向左走 #include<iostream>#includ... 查看详情
可持久化汇总(讲解+题目)
可持久化(一)可持久化(二)可持久化3–可持久化01Trie可持久化4–可持久化并查集各模块的例题都在各自讲解下面有写下面是加强练习练习题讲解——肖然老师的博客练习题：P4137RmqProblem/mexP4587[FJOI2016]神秘数CF484ESignonFenceCF1080F... 查看详情
[sdoi2010]粟粟的书架[主席树](代码片段)
[SDOI2010]粟粟的书架考虑暴力怎么做显然是提取出来(x2-x1+1)*(y2-y1+1)个数字拿出来然后从大到小排序然后就可以按次取数了…然而接下来看数据范围(50\%r,cleq200)(50\%r=1,cleq5*10^5)值域(in[1,1000])对于前50%可以用个前缀和搞定…令(sum_i,j,k)... 查看详情
[bzoj1926]粟粟的书架(代码片段)
BZOJ:https://www.lydsy.com/JudgeOnline/problem.php?id=1926Luogu:https://www.luogu.org/problemnew/show/P2468BZOJ的sillyB评测机各种无故CE，只好去Luogu上A了o(╯□╰)o Algorithm:从数据范围可以发现，这其实是2道题：1、一个R×C的矩形，每次询问一个子矩... 查看详情
粟粟的书架题解(代码片段)
粟粟的书架题解第一次见到这种二合一的题，开始的时候居然死磕二维主席树，又是屈辱看题解系列，其实很比较好做第一部分(R,C≤200，M≤200000,1≤Pi,j≤1,000)这一部分可以用两个数组来记录：(num[i][j][k]):代表1~i,1~j的矩形中小于... 查看详情
刷题[sdoi2010]魔法猪学院/luogup2483_k短路_可持久化可并堆（并没有）(代码片段)
...用最短路树。最牛逼的做法可以看这里，这是标题上的可持久化可并堆。我们发现这种做法，实际上就是变成了在最短路树上走，（记上次走的边是(e_1)，上上次是(e_2)），那每次可以：往当前最末端的那个点的祖先走若干步，... 查看详情
sdoi2010魔法猪学院(代码片段)
...1.$A$*算法$A$*可以解决一般的$k$短路问题，但是并不如可持久化可并堆优秀。$A$*的本质是$f+g$，而估价函数可以用终止节点到终点的最短路表示。所以先反向建图$dij$，然后小根堆跑$A$*即可。优化一下，总代价/起点终点最短路就... 查看详情
bzoj1925:[sdoi2010]地精部落
1925:[Sdoi2010]地精部落TimeLimit:10Sec MemoryLimit:64MBSubmit:1442 Solved:902[Submit][Status][Discuss]Description传说很久以前，大地上居住着一种神秘的生物：地精。地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可... 查看详情