明显的二合一问题。贪心的想,要个数最少,那么久从页数多的开始选。于是对于前50%的数据,可以直接预处理(1~x,1~y)矩阵内大于等于k的元素个数、元素之和的前缀和,然后二分k值来验证;对于后50%的数据,已经退化为一维情形,若再使用前面的方法会mle(5e51e34),那么考虑使用主席树来维护:每个节点建一棵权值线段树,查询时区间内优先选择有区间即可。
可知两种方法的时间复杂度都是o(qlog1000)
#include <bits/stdc++.h> using namespace std; int n,m,q; namespace sofeerdure { const int n=207; int p[201][201]; int f[1001][201][201]; int g[1001][201][201]; #define sum (f[mid][c][d]-f[mid][a-1][d]-f[mid][c][b-1]+f[mid][a-1][b-1]) #define num (g[mid][c][d]-g[mid][a-1][d]-g[mid][c][b-1]+g[mid][a-1][b-1]) static void main() { for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { scanf("%d",&p[i][j]); } } for(int k=1; k<=1000; ++k) { for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { f[k][i][j]=f[k][i-1][j]+f[k][i][j-1]-f[k][i-1][j-1]; g[k][i][j]=g[k][i-1][j]+g[k][i][j-1]-g[k][i-1][j-1]; if(p[i][j]>=k) f[k][i][j]+=p[i][j], g[k][i][j]++; } } } for(int a,b,c,d,h; q--; ) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&h); int l=1,r=1000,mid,ans=-1; while(l<=r) { mid=(l+r)>>1; if(sum>=h) ans=mid, l=mid+1; else r=mid-1; } if((mid=ans)<0) puts("poor qlw"); else printf("%dn",num-(sum-h)/mid); } } #undef sum #undef num } namespace haibaradure { const int n=5e5+10; struct node { int ls,rs,sum,num; } t[n*20]; int root[n],tot; int build(int l,int r) { int x=++tot; if(l==r) return x; int mid=(l+r)>>1; t[x].ls=build(l,mid); t[x].rs=build(mid+1,r); return x; } int insert(int x,int l,int r,int p) { int y=++tot; t[y]=t[x]; t[y].sum+=p; t[y].num++; if(l==r) return y; int mid=(l+r)>>1; if(p<=mid) t[y].ls=insert(t[x].ls,l,mid,p); else t[y].rs=insert(t[x].rs,mid+1,r,p); return y; } int query(int x,int y,int l,int r,int k) { if(l==r) return (k-1)/l+1; int mid=(l+r)>>1; int dif=t[t[y].rs].sum-t[t[x].rs].sum; if(k<=dif) return query(t[x].rs,t[y].rs,mid+1,r,k); else return query(t[x].ls,t[y].ls,l,mid,k-dif)+t[t[y].rs].num-t[t[x].rs].num; } static void main() { root[0]=build(1,1000); for(int i=1,x; i<=m; ++i) { scanf("%d",&x); root[i]=insert(root[i-1],1,1000,x); } for(int a,b,c,d,h; q--; ) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&h); if(t[root[d]].sum-t[root[b-1]].sum<h) puts("poor qlw"); else printf("%dn", query(root[b-1],root[d],1,1000,h)); } } } int main() { scanf("%d%d%d",&n,&m,&q); if(n>1) sofeerdure::main(); else haibaradure::main(); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605733.html