本文共 2317 字，大约阅读时间需要 7 分钟。
粟粟的书架 bzoj-1926 Sdoi-2010
题目大意：
注释：略
想法：分成两个题
前面的我们可以二分，直接二分出来检验即可。
对于R=1的，相当一个数列，我们在上面建立主席树。
然后查询时，我们通过优先遍历右子树的方式使得拿的书最少。
最后，附上丑陋的代码... ...
#include#include #include #include #include #include #include #include using namespace std;int cnt;int n,m,q;int a,b,c,d,h;int f[500010];int s[210][210];int l[10000010];int r[10000010];int v[10000010];int root[500010];int sum[10000010];int val[210][210][1010];int num[210][210][1010];bool check(int x){ if(val[c][d][x]-val[a-1][d][x]-val[c][b-1][x]+val[a-1][b-1][x]>=h) { return true; } return false;}void partation(){ for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&s[i][j]); } } for(int k=0;k<=1000;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j]>=k) { val[i][j][k]=val[i-1][j][k]+val[i][j-1][k]-val[i-1][j-1][k]+s[i][j]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+1; } else { val[i][j][k]=val[i-1][j][k]+val[i][j-1][k]-val[i-1][j-1][k]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]; } } } } while(q--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&h); if(val[c][d][0]-val[a-1][d][0]-val[c][b-1][0]+val[a-1][b-1][0] >1; if(check(mid)==true) { l=mid; ans=mid; } else { r=mid; } } if(ans==-1) { printf("Poor QLW\n"); continue; } printf("%d\n",num[c][d][ans]-num[a-1][d][ans]-num[c][b-1][ans]+num[a-1][b-1][ans]-(val[c][d][ans]-val[a-1][d][ans]-val[c][b-1][ans]+val[a-1][b-1][ans]-h)/ans); }}int updata(int pre,int L,int R,int k){ int rt=++cnt; l[rt]=l[pre]; r[rt]=r[pre]; sum[rt]=sum[pre]+1; v[rt]=v[pre]+k; int mid=(L+R)/2; if(L==R) { return rt; } if(k<=mid) { l[rt]=updata(l[pre],L,mid,k); } else { r[rt]=updata(r[pre],mid+1,R,k); } return rt;}int query(int rr,int ll,int L,int R,int h){ int x=v[r[rr]]-v[r[ll]]; if(v[rr]-v[ll] =h) { return query(r[rr],r[ll],mid+1,R,h); } else { return query(l[rr],l[ll],L,mid,h-x)+sum[r[rr]]-sum[r[ll]]; }}int main(){ scanf("%d%d%d",&n,&m,&q); if(n>1) { partation(); } else { for(int i=1;i<=m;i++) { scanf("%d",&f[i]); root[i]=updata(root[i-1],0,1000,f[i]); } while(q--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&h); int ans=query(root[d],root[b-1],0,1000,h); if(ans<0) { printf("Poor QLW\n"); } else { printf("%d\n",ans); } } }}
小结：主席树... ...
转载于:https://www.cnblogs.com/ShuraK/p/9383729.html