P2468 [SDOI2010] 粟粟的书架
题意简述:
给你一个矩阵,每次给定一个矩形和一个值 \(h\) ,让你在这个矩形中选 $ k$ 个数使得这 \(k\) 个数的和 \(\ge h\) 且最小化这个 \(k\)
对于 \(50\%\) 的数据,满足 \(R, C\le 200\),\(M\le 2\times 10^5\)。
另有 \(50\%\) 的数据,满足 \(R=1\),\(C\le 5\times 10^5\),\(M\le 2\times 10^4\)。
对于 \(100\%\) 的数据,满足 \(1\le P_{i,j}\le 1000\),\(1\le H_i\le 2\times 10^9\)。
Solution:
看到这个猎奇的数据范围我们就知道这题肯定不简单,首先我们来看一下后50分怎么拿:
不难想到我们可以建一颗可持久化权值线段树,然后在主席树上查询在 \([-rt_{l-1}+rt[r]]\) 的答案,具体实现就是权值线段树上尽量往右子树跳,\(k \ge t[x].val\) 就全部取。
然后再来说一下前50分怎么拿,注意到:
满足 \(1\le P_{i,j}\le 1000\),\(R, C\le 200\)
我们可以开一个$ sum[R][C][inf] $ 一个二维前缀和\(sum{i,j,k}\)来存
\((1,1)(i,j)\) 这个矩形内权值等于 \(k\) 的数量
然后对于每个查询,直接暴力从 \(1000 -> 1\) 扫一遍然后统计答案就好了
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
struct Solve1
{
#define N 500005
#define inf 2000000000
//Segment_Tree
struct Segment_Tree{
int rt[N],cnt=0;
struct Tree{
int ls,rs,val,cnt;
}t[N*40];
void insert(int &x,int y,int l,int r,int k)
{
t[x=++cnt] = t[y];
t[x].val+=k;t[x].cnt++;
if(l==r)return;
int mid=l+r>>1;
if(k<=mid)insert(t[x].ls,t[y].ls,l,mid,k);
if(mid<k)insert(t[x].rs,t[y].rs,mid+1,r,k);
}
void query(int x,int y,int l,int r,int L,int R,int &k,int &cnt)
{
if(k<=0)return ;
int Val=-t[x].val+t[y].val,Cnt=-t[x].cnt+t[y].cnt;
if(L<=l&&r<=R&&k>=Val)
{
k-=Val;
cnt+=Cnt;
return;
}
if(l==r)
{
int val=Val/Cnt;
cnt+=(k/val);
k-=(k/val)*val;
if(k){cnt++;k-=val;}
return;
}
int mid=l+r>>1;
if(mid<R)query(t[x].rs,t[y].rs,mid+1,r,L,R,k,cnt);
if(L<=mid) query(t[x].ls,t[y].ls,l,mid,L,R,k,cnt);
}
}T;
void work()
{
for(int i=1,x;i<=m;i++)
{
scanf("%d",&x);
T.insert(T.rt[i],T.rt[i-1],1,inf,x);
}
for(int i=1;i<=q;i++)
{
int l,r,x,y,k;
scanf("%d%d%d%d%d",&x,&l,&y,&r,&k);
int ans=0;
if(-T.t[T.rt[l-1]].val+T.t[T.rt[r]].val<k){printf("Poor QLW\n");continue;}
T.query(T.rt[l-1],T.rt[r],1,inf,1,inf,k,ans);
printf("%d\n",ans);
}
}
#undef N
#undef inf
}S_1;
struct Solve_2{
#define N 205
#define inf 1005
int sum[N][N][inf],a[N][N];
void work()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
sum[i][j][a[i][j]]++;
}
}
for(int i=2;i<=n;i++)for(int k=1;k<=1000;k++)sum[i][1][k]+=sum[i-1][1][k];
for(int j=2;j<=m;j++)for(int k=1;k<=1000;k++)sum[1][j][k]+=sum[1][j-1][k];
for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)for(int k=1;k<=1000;k++)
{
sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+sum[i][j][k];
}
for(int i=1;i<=q;i++)
{
int x_0,y_0,x_1,y_1,h,ans=0;
scanf("%d%d%d%d%d",&x_0,&y_0,&x_1,&y_1,&h);
for(int k=1000;k;k--)
{
int cnt=sum[x_1][y_1][k]-sum[x_1][y_0-1][k]-sum[x_0-1][y_1][k]+sum[x_0-1][y_0-1][k];
if(h>(k*cnt))
{
ans+=cnt;
h-=(k*cnt);
}
else
{
ans+=(h/k);
h-=((h/k)*k);
while(h>0)
{
ans++;
h-=k;
}
break;
}
}
if(h>0)printf("Poor QLW\n");
else printf("%d\n",ans);
}
}
#undef N
#undef inf
}S_2;
int main()
{
//freopen("P2468.in","r",stdin);freopen("P2468.out","w",stdout);
cin>>n>>m>>q;
if(n==1)S_1.work();
else S_2.work();
return 0;
}
标签:粟粟,cnt,le,return,val,int,SDOI2010,P2468
From: https://www.cnblogs.com/LG017/p/18590477