\[Preface
\]
\]
看到这题洛谷标签有 主席树 ，还以为是什么二维主席树的玄学做法（雾
\[Description
\]
\]
给出一个 \(R×C\) 的矩阵。
一共 \(m\) 次询问，每次询问给出一个五元组 \((x1,y1,x2,y2,h)\) 。
求：在矩阵 \((x1,y1,x2,y2)\) 里至少取多少个数，它们的和大于等于 \(h\)
无解输出 Poor QLW 。
\[Solution
\]
\]
显然是贪心地取数，数取的越大，就可以越早使和大于等于 \(h\) 。
因此我们都考虑优先选择大的数，然后一步一步往小的数考虑。
所以我们可以把 " 矩阵内大于等于 \(k\) 的数 " 的和以及个数求出来，然后去二分取数的最小值，把最优性问题转化成一个判定性问题。
\(~\)
注意到：
\(~\)
对于 \(type1\) ，可以直接用 \(O(1000RC)\) 的时间预处理（二维前缀和）。
\(~\)
对于 \(type2\) ，发现 \(O(1000RC)\) 的时间预处理会 \(T\) 飞。
观察到 \(R=1\) ，此时实质上这个矩阵是一个序列，解决 " 区间内大于等于 \(k\) 的数 " 的和以及个数正是主席树擅长的，用主席树维护一下即可。
\[Code
\]
\]
#include<cstdio>
#define RI register int
using namespace std;
inline int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
const int N1=210,N2=500100,MLOGN=10001000;
const int MaxV=1000;
int n,m,Q;
int val[N1][N1];
int sum[N1][N1][MaxV+100],cnt[N1][N1][MaxV+100];
int GetSum(int x1,int y1,int x2,int y2,int k)
{
return sum[x2][y2][k]-sum[x1-1][y2][k]-sum[x2][y1-1][k]+sum[x1-1][y1-1][k];
}
int GetCnt(int x1,int y1,int x2,int y2,int k)
{
return cnt[x2][y2][k]-cnt[x1-1][y2][k]-cnt[x2][y1-1][k]+cnt[x1-1][y1-1][k];
}
void Work1()
{
for(RI i=1;i<=n;i++)
for(RI j=1;j<=m;j++)
val[i][j]=read();
for(RI k=1;k<=MaxV;k++)
for(RI i=1;i<=n;i++)
for(RI j=1;j<=m;j++)
{
sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+(val[i][j]>=k?val[i][j]:0);
cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(val[i][j]>=k?1:0);
}
while(Q--)
{
int x1=read(),y1=read(),x2=read(),y2=read(),h=read();
if(GetSum(x1,y1,x2,y2,1)<h)
{
puts("Poor QLW");
continue;
}
int l=1,r=MaxV;
while(l<r)
{
int mid=(l+r+1)/2;
if(GetSum(x1,y1,x2,y2,mid)<h)
r=mid-1;
else
l=mid;
}
printf("%d\n",GetCnt(x1,y1,x2,y2,l)-(GetSum(x1,y1,x2,y2,l)-h)/l);
}
}
int seq[N2];
int tot,root[N2];
struct SegmentTree{
int lc,rc;
int cnt;
int sum;
}t[MLOGN];
int New()
{
tot++;
t[tot].lc=t[tot].rc=t[tot].cnt=t[tot].sum=0;
return tot;
}
void insert(int &p,int now,int l,int r,int delta,int val1,int val2)
{
p=New();
t[p]=t[now];
t[p].cnt+=val1;
t[p].sum+=val2;
if(l==r)return;
int mid=(l+r)/2;
if(delta<=mid)
insert(t[p].lc,t[now].lc,l,mid,delta,val1,val2);
else
insert(t[p].rc,t[now].rc,mid+1,r,delta,val1,val2);
}
int ask(int p,int q,int l,int r,int h)
{
if(l==r)return (h-1)/l+1;
int mid=(l+r)/2;
int rcnt=t[t[q].rc].cnt-t[t[p].rc].cnt,
rsum=t[t[q].rc].sum-t[t[p].rc].sum;
if(h<=rsum)
return ask(t[p].rc,t[q].rc,mid+1,r,h);
else
return ask(t[p].lc,t[q].lc,l,mid,h-rsum)+rcnt;
}
void Work2()
{
n=m;
for(RI i=1;i<=n;i++)
seq[i]=read();
for(RI i=1;i<=n;i++)
insert(root[i],root[i-1],1,MaxV,seq[i],1,seq[i]);
while(Q--)
{
int l,r,h;
read(),l=read(),read(),r=read(),h=read();
if(t[root[r]].sum-t[root[l-1]].sum<h)
{
puts("Poor QLW");
continue;
}
printf("%d\n",ask(root[l-1],root[r],1,MaxV,h));
}
}
int main()
{
n=read(),m=read(),Q=read();
if(n>1)
Work1();
else
Work2();
return 0;
}
\[Thanks \ for \ watching
\]
\]