关键词：
粟粟的书架题解
第一次见到这种二合一的题，
开始的时候居然死磕二维主席树，
又是屈辱看题解系列，
其实很比较好做
第一部分(R, C≤200，M≤200000,1≤Pi,j≤1,000)
这一部分可以用两个数组来记录：
(num[i][j][k]):代表1~i,1~j的矩形中小于等于k的书页数量，
(v[i][j][k]):代表1~i,1~j的矩形中小于等于k的书页页数之和。
二分最大书页页数，找到满足矩阵内v值大于给定h的最小值，输出对应num,
预处理时用二维前缀和的方式维护即可，
bool check(int x)return v[t3][t4][x]-v[t1-1][t4][x]+v[t1-1][t2-1][x]-v[t3][t2-1][x]>=t5;
int ef(int l,int r)
if(l==r) return l;
int mid=(l+r+1)>>1;
if(check(mid)) return ef(mid,r);
return ef(l,mid-1);
int main()
if(r!=1)
for(int i=1;i<=r;++i) for(int j=1;j<=c;++j)t=read(); for(int k=1;k<=1000;++k) num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+(t>=k),v[i][j][k]=v[i-1][j][k]+v[i][j-1][k]-v[i-1][j-1][k]+(t>=k?t:0);
for(int i=1;i<=m;++i)t1=read(),t2=read(),t3=read(),t4=read(),t5=read(); if(!check(1))printf("Poor QLW
"); continue; t=ef(1,1000),p=num[t3][t4][t+1]-num[t1-1][t4][t+1]+num[t1-1][t2-1][t+1]-num[t3][t2-1][t+1],q=v[t3][t4][t+1]-v[t1-1][t4][t+1]+v[t1-1][t2-1][t+1]-v[t3][t2-1][t+1],printf("%d
",p+(t5-q-1)/t+1);
后面r=1的情况：
同样二分，不过是二分第k大的书页页数的k，
我们可以用主席树维护第k大的页数之和，
直接上总代码吧：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+3006,K=202,M=1002;
int m,r,c,t,l=0,t1,t2,t3,t4,t5,num[K][K][M],v[K][K][M],p,q,cnt=0,rt[N],sum[N*12],son[N*12][2];
ll w[N<<4];
inline int read()
int T=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')if(ch=='-') F=-1; ch=getchar();
while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
return F*T;
void update(int l,int r,int k,int &x,int y)
if(!x) x=++cnt;
if(l==r)sum[x]=sum[y]+1,w[x]=w[y]+l; return;
int mid=l+r>>1;
if(k<=mid) update(l,mid,k,son[x][0],son[y][0]),son[x][1]=son[y][1];
else update(mid+1,r,k,son[x][1],son[y][1]),son[x][0]=son[y][0];
sum[x]=sum[son[x][0]]+sum[son[x][1]],w[x]=w[son[x][0]]+w[son[x][1]];
int query(int l,int r,int k,int x,int y)
if(l==r) return min(sum[x]-sum[y],k)*l;
int mid=l+r>>1;
if(k<=sum[son[x][1]]-sum[son[y][1]]) return query(mid+1,r,k,son[x][1],son[y][1]);
return w[son[x][1]]-w[son[y][1]]+query(l,mid,k-sum[son[x][1]]+sum[son[y][1]],son[x][0],son[y][0]);
bool check(int x)return v[t3][t4][x]-v[t1-1][t4][x]+v[t1-1][t2-1][x]-v[t3][t2-1][x]>=t5;
int ef(int l,int r)
if(l==r) return l;
int mid=(l+r+1)>>1;
if(check(mid)) return ef(mid,r);
return ef(l,mid-1);
int ef2(int l,int r)
if(l==r) return l;
int mid=l+r>>1;
if(query(1,1000,mid,rt[t4],rt[t2-1])>=t5) return ef2(l,mid);
return ef2(mid+1,r);
int main()
r=read(),c=read(),m=read(),rt[0]=++cnt;
if(r!=1)
for(int i=1;i<=r;++i) for(int j=1;j<=c;++j)t=read(); for(int k=1;k<=1000;++k) num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+(t>=k),v[i][j][k]=v[i-1][j][k]+v[i][j-1][k]-v[i-1][j-1][k]+(t>=k?t:0);
for(int i=1;i<=m;++i)t1=read(),t2=read(),t3=read(),t4=read(),t5=read(); if(!check(1))printf("Poor QLW
"); continue; t=ef(1,1000),p=num[t3][t4][t+1]-num[t1-1][t4][t+1]+num[t1-1][t2-1][t+1]-num[t3][t2-1][t+1],q=v[t3][t4][t+1]-v[t1-1][t4][t+1]+v[t1-1][t2-1][t+1]-v[t3][t2-1][t+1],printf("%d
",p+(t5-q-1)/t+1);
else
for(int i=1;i<=c;++i) t=read(),update(1,1000,t,rt[i],rt[i-1]);
for(int i=1;i<=m;++i)t1=read(),t2=read(),t3=read(),t4=read(),t5=read(); if(query(1,1000,t4-t2+1,rt[t4],rt[t2-1])<t5)printf("Poor QLW
"); continue; printf("%d
",ef2(1,t4-t2+1));
return 0;
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]粟粟的书架(代码片段)
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的矩形，每次询问一个子矩... 查看详情
[sdoi2010]粟粟的书架(代码片段)
[SDOI2010]粟粟的书架题意：一个R*C的矩阵，每个位置都有个数page[ij]，现在选定一个小矩阵范围(给左上角坐标，和右下角坐标)，问这个范围内的数总和是否大于h，如果大于h的话最少选几个数aij对于50%的数... 查看详情
bzoj1926[sdoi2010]粟粟的书架
题解：这是两道题前50%:发现p[i][j]很小，于是记录f[i][j][k]表示（1，1）~（i，j）这个子矩阵内>=k的书的总高度,g[i][j][k]记录本数查询是二分答案就好了后50%:主席树，右子树够了就向右走，否则向左走 #include<iostream>#includ... 查看详情
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列... 查看详情
bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的... 查看详情
刷题bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有P... 查看详情
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 查看详情
[sdoi2010]粟粟的书架
题目大意：网址：https://daniu.luogu.org/problemnew/show/2468大意：本题有两问：[1]给定一个(R*C)的带权矩阵，询问(2×10^5)次在一个子矩阵内至少选择多少个点使他们的权值和大于(H)。[2]给定长度为L的一条链，询问(2×10^4)次在一个区间([L,... 查看详情
[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[sdoi2010]粟粟的书架主席树+二分+前缀和
题目幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j... 查看详情
sdoi2010粟粟的书架lg2468（可持久化，前缀和）(代码片段)
题面见https://www.luogu.org/problemnew/show/P2468然后这道题属于合二为一题，看一眼数据范围就能发现首先我们先考虑50分，二维前缀和维护一下（反正我不记得公式，手推了半天）tot[i][j][k]表示矩阵（1,1）到（i，j）中数值大等于k的总... 查看详情
洛谷p2676超级书架题解(代码片段)
题目传送门题目一看就是贪心。C++福利来了：sort。基本思路就是：要使奶牛最少那么肯定高的奶牛先啦。直接排序一遍（从高到矮）然后while，搞定！#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llN,B,H[20010];boolcmp(intx,inty)retur... 查看详情
可持久化汇总(讲解+题目)
...OI2016]神秘数CF484ESignonFenceCF1080FKatyaandSegmentsSetsP2468[SDOI2010]粟粟的书架P3302[SD 查看详情
[题解]bzoj1861book书架-splay
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1396 Solved: 803[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到 查看详情
题解[zjoi2006]书架（splay）
懒得复制，戳我戳我Solution:还是一个\(Splay\)，我们只用多存一个值\(rad\)来维护二叉树，然后用数组存下每个书对应的值是多少\(Top\)操作，我是把\(s\)旋转到根节点，然后删除，将\(s\)对应的\(rad\)值调至最小，然后插入就可以\(Bot... 查看详情