(luogu2468)粟粟的书架(SDOI2010) 发表于 2021-03-28 | 分类于 solution , 数据结构 , 主席树 原题链接 思路:最多两百行可以直接对每行暴力构建主席树, 查询时将每行的结果加起来就行了. 代码:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include <cstdio>#include <algorithm>using namespace std;const int Mn(205),Mp(1050),Mc(500500);struct pnode { //主席树结点 long long sz,sum; //个数, 区间和 pnode *ls,*rs; //左右儿子}*roots[Mn][Mc],*nil; //根结点, 自定义空结点void init_nil() { //初始化nil nil = new pnode((pnode) {0,0,nil,nil});}void init_root0(pnode*& rt,int l,int r) { //每行第一个主席树初始化 rt = new pnode(); rt->sz = rt->sum = 0; if(l==r) { rt->ls = rt->rs = nil; return; } else { int mid((l+r)/2); init_root0(rt->ls,l,mid); init_root0(rt->rs,mid+1,r); }}void mdf(pnode*& lv,int mp,int l,int r) { //主席树添加 lv = new pnode(*lv); lv->sz += 1; lv->sum += mp; if(l==r) { return; } int mid((l+r)/2); if(mp<=mid) { mdf(lv->ls,mp,l,mid); } else { mdf(lv->rs,mp,mid+1,r); }}pnode *lrt[Mn], *rrt[Mn]; //查询每行的左右根结点int qry(int rtl,int l,int r,int h) { //查询(根的个数) if(l==r) { return h/l+(h%l!=0); //注意一种数可能有多个, 需要取一部分 } int mid((l+r)/2); int rsum(0); for(int i(1);i<=rtl;++i) { //计算右边和 rsum += rrt[i]->rs->sum - lrt[i]->rs->sum; } if(rsum<h) { int rsz(0); for(int i(1);i<=rtl;++i) { //更新根 rsz += rrt[i]->rs->sz - lrt[i]->rs->sz; lrt[i] = lrt[i]->ls; rrt[i] = rrt[i]->ls; } return rsz + qry(rtl,l,mid,h-rsum); } else { for(int i(1);i<=rtl;++i) { lrt[i] = lrt[i]->rs; rrt[i] = rrt[i]->rs; } return qry(rtl,mid+1,r,h); }}int main() { init_nil(); int r,c,m; scanf("%d %d %d",&r,&c,&m); /*<初始化>*/ for(int i(1);i<=r;++i) { init_root0(roots[i][0],1,Mp); for(int j(1);j<=c;++j) { roots[i][j] = roots[i][j-1]; int p; scanf("%d",&p); mdf(roots[i][j],p,1,Mp); } } /*</初始化>*/ while(m--) { int x1,y1,x2,y2,h; scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&h); int hsum(0); for(int i(x1);i<=x2;++i) { lrt[i-x1+1] = roots[i][y1-1]; rrt[i-x1+1] = roots[i][y2]; hsum += rrt[i-x1+1]->sum - lrt[i-x1+1]->sum; } if(hsum<h) { //若矩形内所有数加起来小于h则无解 printf("Poor QLW\n"); } else { printf("%d\n",qry(x2-x1+1,1,Mp,h)); } } return 0;}