来了来了，随便拽一道题写题解【大雾】
最近发现自己基础奇差于是开始复习之前学过的东西，正好主席树我几乎完全没学会，然后打开洛谷试炼场…
发现了这么一道二合一的题。
这道题其实分成两个部分，前50%是一道题，后50%是另一道。观察数据范围的时候发现两种范围差别很大，似乎具有针对性，于是分开来想。
再仔细一看，书页的范围p小于等于1000，似乎在暗示值域上可以搞什么幺蛾子。
前50%是矩阵上的问题，c和r小于等于200。题目要求在一个矩形内凑出某一高度，正好值域很小，可以想到用二维前缀和记录一下每种高度的书页在(1,1)-(i,j)内出现的数量以及累计的高度，时间复杂度O(crp)。然后对于每个询问，在书页的值域p上从大到小累加高度和数量，时间复杂度O(p)。
后50%r=1，成为了序列上的问题。要求在一段区间内凑出要求的高度，如果依然从大到小枚举书页高度，预处理的复杂度是不能接受的。然而区间整体加减某一段值域的数据，这就是主席树的板子…时间复杂度O(nlogn)，空间复杂度O(nlogn)。
于是因为我主席树写得不熟练，之后的查询出了锅。查询一直递归到某个叶节点的时候，应该像上面前缀和那样讨论一下这一种书页要凑多少个，对答案产生多少贡献。然而我直接打了个return 1上去，导致第二个样例都卡了我很久…
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int r,c,m,x1,x2,y1,y2;
int cnt[][][],ans;
long long sum[][][],h,num; const int log=;
int T[],L[*log],R[*log],SUM[*log],CNT[*log];
int tot;
void build(int &p,int l,int r){
p=++tot;
if(l==r)return;
int mid=(l+r)/;
build(L[p],l,mid);
build(R[p],mid+,r);
}
void update(int &p,int pre,int l,int r,int x){
p=++tot;
L[p]=L[pre],R[p]=R[pre],CNT[p]=CNT[pre]+,SUM[p]=SUM[pre]+x;
if(l==r)return;
int mid=(l+r)/;
if(x<=mid)update(L[p],L[pre],l,mid,x);
else update(R[p],R[pre],mid+,r,x);
}
int query(int x,int y,int l,int r,long long h){
int mid=(l+r)/;
if(l==r){
if(h%l==)return h/l;
else return h/l+;
}
int val=;
if(SUM[R[y]]-SUM[R[x]]>=h)return query(R[x],R[y],mid+,r,h);
else if(SUM[R[y]]-SUM[R[x]]==h)return CNT[R[y]]-CNT[R[x]];
else{
val+=CNT[R[y]]-CNT[R[x]];
return val+query(L[x],L[y],l,mid,h-SUM[R[y]]+SUM[R[x]]);
}
}
int main()
{
scanf("%d%d%d",&r,&c,&m);
if(r==){
build(T[],,);
for(int i=,x;i<=c;i++){
scanf("%d",&x);
update(T[i],T[i-],,,x);
}
for(int i=;i<=m;i++){
scanf("%d%d%d%d%lld",&x1,&y1,&x2,&y2,&h);
num=,ans=;
if(SUM[T[y2]]-SUM[T[y1-]]<h)printf("Poor QLW\n");
else{
ans=query(T[y1-],T[y2],,,h);
printf("%d\n",ans);
}
}
}
else{
for(int i=;i<=r;i++){
for(int j=,x;j<=c;j++){
scanf("%d",&x);
for(int p=;p<=;p++){
cnt[i][j][p]=cnt[i][j-][p]+cnt[i-][j][p]-cnt[i-][j-][p];
sum[i][j][p]=sum[i][j-][p]+sum[i-][j][p]-sum[i-][j-][p];
}
cnt[i][j][x]++;
sum[i][j][x]+=x;
}
}
for(int i=;i<=m;i++){
scanf("%d%d%d%d%lld",&x1,&y1,&x2,&y2,&h);
num=,ans=;
for(int p=;p>=;p--){
if(num+sum[x2][y2][p]+sum[x1-][y1-][p]-sum[x2][y1-][p]-sum[x1-][y2][p]>=h){
long long cha=h-num;
if(!(cha%p)){
ans+=cha/p;
}
else{
ans+=cha/p+;
}
num+=sum[x2][y2][p]+sum[x1-][y1-][p]-sum[x2][y1-][p]-sum[x1-][y2][p];
break;
}
else{
num+=sum[x2][y2][p]+sum[x1-][y1-][p]-sum[x2][y1-][p]-sum[x1-][y2][p];
ans+=cnt[x2][y2][p]+cnt[x1-][y1-][p]-cnt[x2][y1-][p]-cnt[x1-][y2][p];
}
}
if(num>=h)printf("%d\n",ans);
else printf("Poor QLW\n");
}
}
return ;
}