[SDOI2010]粟粟的书架
题目大意：
给定一个(n imes m)的格子，每个格子有一个权值(p_{i,j})。(q)次询问，每次询问给定的子矩阵中，至少选取多少个数使得这些数权值和(le h)？
对于(50\%)的数据，(n,mle200,qle2 imes10^5)；
对于另外(50\%)的数据，(n=1,mle5 imes10^5,qle2 imes10^4)。
思路：
二合一题目。
对于前(50\%)的数据，预处理矩阵(1sim i,1sim j)中大于(p)的数的个数及权值和。二分答案判断可行性即可。
对于后(50\%)的数据，主席树套二分即可。
源代码：
#include<cstdio>
#include<cctype>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=201,M=5e5+1,P=1001,logP=11;
int sum[N][N][P],cnt[N][N][P];
inline int calc1(const int &x1,const int &y1,const int &x2,const int &y2,const int &k) {
return cnt[x2][y2][k]-cnt[x1][y2][k]-cnt[x2][y1][k]+cnt[x1][y1][k];
}
inline int calc2(const int &x1,const int &y1,const int &x2,const int &y2,const int &k) {
return sum[x2][y2][k]-sum[x1][y2][k]-sum[x2][y1][k]+sum[x1][y1][k];
}
inline bool check1(const int &x1,const int &y1,const int &x2,const int &y2,const int &k,const int &h) {
return calc2(x1,y1,x2,y2,k)>=h;
}
inline bool check2(const int &x1,const int &y1,const int &x2,const int &y2,const int &k,const int &c,const int &h) {
return calc2(x1,y1,x2,y2,k)-c*k>=h;
}
class FotileTree {
#define mid ((b+e)>>1)
private:
struct Node {
int sum,cnt,left,right;
};
Node node[M*logP];
int sz,new_node(const int &p) {
node[++sz]=node[p];
return sz;
}
public:
int root[M];
void insert(int &p,const int &b,const int &e,const int &x) {
p=new_node(p);
node[p].cnt++;
node[p].sum+=x;
if(b==e) return;
if(x<=mid) insert(node[p].left,b,mid,x);
if(x>mid) insert(node[p].right,mid+1,e,x);
}
int query(const int &p,const int &q,const int &b,const int &e,const int &x) const {
if(node[p].sum-node[q].sum<x) return -1;
if(b==e) {
int l=1,r=node[p].cnt;
while(l<=r) {
const int k=(l+r)>>1;
if(node[p].sum-k*b>=x) {
l=k+1;
} else {
r=k-1;
}
}
return node[p].cnt-(l-1);
}
const int tmp=node[node[p].right].sum-node[node[q].right].sum;
if(tmp>=x) return query(node[p].right,node[q].right,mid+1,e,x);
return query(node[p].left,node[q].left,b,mid,x-tmp)+node[node[p].right].cnt-node[node[q].right].cnt;
}
#undef mid
};
FotileTree t;
int main() {
const int n=getint(),m=getint(),q=getint();
if(n==1) {
for(register int i=1;i<=m;i++) {
t.insert(t.root[i]=t.root[i-1],1,P-1,getint());
}
for(register int i=0;i<q;i++) {
const int x1=getint(),y1=getint(),x2=getint(),y2=getint(),h=getint();
const int ans=t.query(t.root[y2],t.root[y1-1],1,P-1,h);
if(ans==-1) {
puts("Poor QLW");
continue;
}
printf("%d
",ans);
}
return 0;
}
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=m;j++) {
const int p=getint();
cnt[i][j][p]=cnt[i-1][j][p]+cnt[i][j-1][p]-cnt[i-1][j-1][p]+1;
sum[i][j][p]=sum[i-1][j][p]+sum[i][j-1][p]-sum[i-1][j-1][p]+p;
for(register int k=1;k<P;k++) {
if(k==p) continue;
cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k];
sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];
}
}
}
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=m;j++) {
for(register int p=P-2;p>=1;p--) {
cnt[i][j][p]+=cnt[i][j][p+1];
sum[i][j][p]+=sum[i][j][p+1];
}
}
}
for(register int i=0;i<q;i++) {
const int x1=getint()-1,y1=getint()-1,x2=getint(),y2=getint(),h=getint();
if(calc2(x1,y1,x2,y2,1)<h) {
puts("Poor QLW");
continue;
}
int l=1,r=P-1,ans=-1;
while(l<=r) {
const int mid1=(l+r)>>1;
if(check1(x1,y1,x2,y2,mid1,h)) {
l=mid1+1;
int b=1,e=calc1(x1,y1,x2,y2,mid1)-(mid1!=P-1?calc1(x1,y1,x2,y2,mid1+1):0);
while(b<=e) {
const int mid2=(b+e)>>1;
if(check2(x1,y1,x2,y2,mid1,mid2,h)) {
b=mid2+1;
} else {
e=mid2-1;
}
}
ans=calc1(x1,y1,x2,y2,mid1)-(b-1);
} else {
r=mid1-1;
}
}
printf("%d
",ans);
}
return 0;
}