粟粟专题

【bzoj1926】【sdoi2010】【粟粟的书架】【二分+主席树】

Description Input 第一行是三个正整数R, C, M。 接下来是一个 R行C 列的矩阵,从上到下、从左向右依次给出了每本书的 页数Pi,j。 接下来 M行,第 i 行给出正整数x1i, y1i, x2i, y2i, Hi,表示第i 天的指定区域 是﹙x1i, y1i﹚与﹙x2i, y2i﹚间的矩形,总页数之和要求不低于 Hi。 保证 1≤x1i≤x2i≤R,1≤y1i

#二分,主席树#洛谷 2468 粟粟的书架

题目 给出一个矩阵,问一个子矩阵中至少要多少个数才能使和 ≥ h \geq h ≥h,多组数据,分成 1 ≤ r , c ≤ 200 和 r = 1 , 1 ≤ c ≤ 500000 1\leq r,c\leq 200和r=1,1\leq c\leq 500000 1≤r,c≤200和r=1,1≤c≤500000 分析 这显然是一道以二分为核心的题目,但是这道题目二合一,对于 r ≠ 1