[SDOI2010] 粟粟的书架

明显的二合一问题。贪心的想，要个数最少，那么久从页数多的开始选。于是对于前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("%d\n",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("%d\n", 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;
}