自动搬运

查看原文

来自洛谷，原作者为

	凌幽 愿君得偿所愿（顺便凌幽是无忧的同音诶

搬运于2025-08-24 21:38:02，当前版本为作者最后更新于2017-11-20 10:35:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

应该算是一道二合一的题吧

观察数据范围

前50%的R,C均小于等于200,求给定矩阵中至少要取几个数加起来可以大于给定的值

可以搞一搞前缀和,二分最小值,变成一个判定性问题

value[i][j][k] 从(1,1)到(i,j)的矩阵中数值>=k的数的总和

num[i][j][k] 从(1,1)到(i,j)的矩阵中数值>=k的数的个数

后50%的R=1,C<=5*10^5,求给定序列中至少要取几个数加起来可以大于给定的值

依旧是二分最小值,可以用主席树维护

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
#define re register
#define no printf("Poor QLW\n")
int n,m,t; // n hang m lie t tian
int a1,b1,a2,b2,h;
int page[202][202];
int value[202][202][1002];
int num[202][202][1002];
inline int get_value(int a1,int b1,int a2,int b2,int k){
    return value[a2][b2][k]-value[a1-1][b2][k]+value[a1-1][b1-1][k]-value[a2][b1-1][k];
}
inline int get_num(int a1,int b1,int a2,int b2,int k){
    return num[a2][b2][k]-num[a1-1][b2][k]+num[a1-1][b1-1][k]-num[a2][b1-1][k];
}
inline void work1(){
    re int maxn=0;
    for(re int i=1;i<=n;++i)
        for(re int j=1;j<=m;++j){
            scanf("%d",&page[i][j]);
            if(page[i][j]>maxn) maxn=page[i][j];
        }
    for(re int k=0;k<=maxn;++k) // 前缀和,容斥原理
        for(re int i=1;i<=n;++i)
            for(re int j=1;j<=m;++j){
                value[i][j][k]=value[i-1][j][k]+value[i][j-1][k]-value[i-1][j-1][k]+(page[i][j]>=k?page[i][j]:0);
                num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+(page[i][j]>=k?1:0);
                // value[i][j][k] 从(1,1)到(i,j)的矩阵中数值>=k的数的总和
                // num[i][j][k] 从(1,1)到(i,j)的矩阵中数值>=k的数的个数
        }
    while(t--){
        scanf("%d%d%d%d%d",&a1,&b1,&a2,&b2,&h);
        if(get_value(a1,b1,a2,b2,0)<h) {no;continue;}
        re int l=0,r=maxn+1,ans=-1;
        while(l+1<r){
            re int mid=l+r>>1;
            if(get_value(a1,b1,a2,b2,mid)>=h) l=mid,ans=mid;
            else r=mid;
        }
        if(ans==-1) no;
        else printf("%d\n",get_num(a1,b1,a2,b2,ans)-(get_value(a1,b1,a2,b2,ans)-h)/ans);
    }    
}
#define N 5500002
int L[N],R[N],size[N],sum[N],root[N],cnt;
inline void update(int A,int &B,int l,int r,int x){
    B=++cnt;
    size[B]=size[A]+1;
    sum[B]=sum[A]+x;
    re int mid=l+r>>1;
    if(l==r) return;
    if(x<=mid) update(L[A],L[B],l,mid,x),R[B]=R[A];
    else update(R[A],R[B],mid+1,r,x),L[B]=L[A];        
}
inline int query(int A,int B,int l,int r,int k){
    re int ans=0;
    while(l<r){
        re int mid=l+r>>1;
        re int lch=sum[R[B]]-sum[R[A]];
        if(lch<k) ans+=size[R[B]]-size[R[A]],k-=lch,r=mid,B=L[B],A=L[A];
        else l=mid+1,B=R[B],A=R[A];
    }
    ans+=(k+l-1)/l;
    return ans;
}
inline void work2(){
    for(re int i=1;i<=m;++i){
        re int a; scanf("%d",&a);
        update(root[i-1],root[i],1,1000,a);
    }
    while(t--){
        scanf("%d%d%d%d%d",&a1,&b1,&a2,&b2,&h);
        if(sum[root[b2]]-sum[root[b1-1]]<h) {no;continue;}
        printf("%d\n",query(root[b1-1],root[b2],1,1000,h));
    }    
}
inline int dy(){
    scanf("%d%d%d",&n,&m,&t);
    if(n==1) work2();
    else work1();
    return 0;
}
int QAQ = dy();
int main(){;}