幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j页厚。

粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。不过她发现，如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第i天指定的那个苹果，只要她脚下放置书的总页数之和不低于Hi，就一定能够摘到。

由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形，第i天给定区域的左上角是上数第x1i行的左数第y1i本书，右下角是上数第x2i行的左数第y2i本书。换句话说，粟粟在这一天，只能在这﹙x2i－x1i＋1﹚×﹙y2i－y1i＋1﹚本书中挑选若干本垫在脚下，摘取苹果。

粟粟每次取书时都能及时放回原位，并且她的书架不会再撤下书目或换上新书，摘苹果的任务会一直持续M天。给出每本书籍的页数和每天的区域限制及采摘要求，请你告诉粟粟，她每天至少拿取多少本书，就可以摘到当天指定的苹果。

 

对于50%的数据，满足R, C≤200，M≤200,000；

另有50%的数据，满足R＝1，C≤500,000，M≤20,000；

不看数据范围我怕不是就要想二维主席树了……

首先我们有一个很简单的贪心：取书从大到小取的话书的数量最小。

然后先考虑后50%就是一个区间，主席树维护一下查询后缀比h大的最小数字个数即可，做法很经典就不讲了。

对于前50%的数据我们可以二分取书的最小页数，这样有a[i][j][k],b[i][j][k]分别表示(i,j)前缀和矩阵中大于等于k页的书的个数和页数和为多少。

根据贪心原则处理出最小页数之后利用a和b数组搞搞就行了。

PS：请注意可能多算/少算的书。query的最后一行和前50%最后的sum1就是起这个作用的。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=5e5+5;const int M=205;const int MAX=1000;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct tree{ int l,r,size,sum;}tr[N*20];int rt[N],pool;inline void insert(int &y,int &x,int l,int r,int p){ tr[x=++pool]=tr[y]; if(l==r){ tr[x].size++;tr[x].sum+=p; return; } int mid=(l+r)>>1; if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p); else insert(tr[y].r,tr[x].r,mid+1,r,p); tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum; tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size;}inline int query(int nl,int nr,int l,int r,int k){ int ans=0; while(l
           
            >1; int delta=tr[tr[nr].r].sum-tr[tr[nl].r].sum; if(delta
            
             =k)a[i][j][k]++,b[i][j][k]+=p[i][j]; } } } for(int i=1;i<=m;i++){ int x1=read(),y1=read(),x2=read(),y2=read(),h=read(); int l=0,r=1000;x1--;y1--; while(l
             
              >1; if(b[x1][y1][mid]+b[x2][y2][mid]-b[x2][y1][mid]-b[x1][y2][mid]>=h) l=mid; else r=mid-1; } if(!l)puts("Poor QLW"); else{ int sum1=b[x1][y1][l]+b[x2][y2][l]-b[x2][y1][l]-b[x1][y2][l]-h; int sum2=a[x1][y1][l]+a[x2][y2][l]-a[x2][y1][l]-a[x1][y2][l]; printf("%d\n",sum2-sum1/l); } } } return 0;}
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++