[SDOI2010] 粟粟的书架

题意

给出一个矩阵 ,要求回答 个以下询问:

x1,y1,x2,y2,h 在以 为左上角,以 为右下角的子矩阵中找出 数使得这些数的和大于等于 .

要求最小化 ,如果无解输出 Poor QLW.

对于一半的数据 ;对于另一半的数据 .

对于所有数据, .

Subtask1

对于前半部分的数据,矩阵二维前缀和+二分即可

定义

然后二分判断,输出 即可。最后要减掉多余的相同的书

#include<cstdio>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=1003,G=202,LST=1<<22;
int r,c,m;
int p[N][N];
//sbt1
int sum[G][G][N],tot[G][G][N];
int x,y,a,b,h;
int calc1(int k){return sum[a][b][k]-sum[x-1][b][k]-sum[a][y-1][k]+sum[x-1][y-1][k];}
int calc2(int k){return tot[a][b][k]-tot[x-1][b][k]-tot[a][y-1][k]+tot[x-1][y-1][k];}
bool check(int k){return calc1(k)>=h;}
void solve1(){FOR(i,1,r)FOR(j,1,c)FOR(k,1,1000){sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+(p[i][j]>=k?p[i][j]:0);
        tot[i][j][k]=tot[i-1][j][k]+tot[i][j-1][k]-tot[i-1][j-1][k]+(p[i][j]>=k);
    }
    FOR(i,1,m){scanf("%d%d%d%d%d",&x,&y,&a,&b,&h);
        int l=1,r=1000;
        while(l<r){int mid=(l+r+1)>>1;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        if(calc1(l)<h)puts("Poor QLW");
        else printf("%d\n",calc2(l)-(calc1(l)-h)/l);// 删掉多余的书
    }
}

Subtask2

退化为一维序列,那么直接主席树维护即可

//sbt2
int totcnt;
int lc[LST],rc[LST],L[LST],R[LST],rt[LST];
int cnt[LST],su[LST];
void build(int &u,int l,int r){u=++totcnt,L[u]=l,R[u]=r;
    int mid=(l+r)>>1;
    if(l<r)build(lc[u],l,mid),build(rc[u],mid+1,r);
}
void pushup(int u){cnt[u]=cnt[lc[u]]+cnt[rc[u]];
    su[u]=su[lc[u]]+su[rc[u]];
}
int modify(int u,int v){
    int u2=++totcnt;
    L[u2]=L[u],R[u2]=R[u];
    if(L[u]==R[u])return cnt[u2]=cnt[u]+1,su[u2]=su[u]+v,u2;
    if(v<=R[lc[u]])lc[u2]=modify(lc[u],v),rc[u2]=rc[u];
    else lc[u2]=lc[u],rc[u2]=modify(rc[u],v);
    pushup(u2);
    return u2;
}
int query(int tl,int tr,int h){// 返回第 k 大数的编号
    if(L[tl]==R[tl])return h/L[tl]+(h%L[tl]!=0);
    int rsum=su[rc[tr]]-su[rc[tl]],rcnt=cnt[rc[tr]]-cnt[rc[tl]];
    if(h<rsum)return query(rc[tl],rc[tr],h);
    else return query(lc[tl],lc[tr],h-rsum)+rcnt;// 排名
}
void solve2(){build(rt[0],1,1000);
    FOR(i,1,c)rt[i]=modify(rt[i-1],p[1][i]);
    FOR(i,1,m){scanf("%d%d%d%d%d",&x,&y,&a,&b,&h);
        if(su[rt[b]]-su[rt[y-1]]<h)puts("Poor QLW");
        else printf("%d\n",query(rt[y-1],rt[b],h));
    }
}

int main(){scanf("%d%d%d",&r,&c,&m);
    FOR(i,1,r)FOR(j,1,c)scanf("%d",&p[i][j]);
    if(r>1)solve1();
    else solve2();
    return 0;
}

两段代码拼一下就行啦


 上一篇
[CQOI2011] 动态逆序对 [CQOI2011] 动态逆序对
题意给出一个 的排列 ,要求做 次删除操作,每次删掉一个数 ,求每次删除操作前整个序列的逆序对。 . 教训这道题告诉我永远不要相信 $
2019.01.24
下一篇 
可持久化数据结构(二) 可持久化数据结构(二)
引言本文上接《可持久化数据结构(一)》,简单介绍了动态主席树。然后主要讲解了各类求第 K 小值的算法。 权值线段树的运算仍然是主席树的部分,我们先系统讲解权值线段树的运算 考虑两颗结构相同的权值线段树 ,那么定义有如下运算:
2019.01.23
  目录