c/c++语言开发共享[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("%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; }