CodeForces - 527C Glass Carving——线段树

CodeForces - 527C Glass Carving——线段树

题意：给定一个矩形，每次可以横向切割或纵向切割，求每次切割完后所有矩形的最大面积

思路：最大矩形的面积 = 最大的w * 最大的h，所以可以键两棵线段树，一棵维护最大的w，一棵维护最大的h，以维护最大的w为例：

我们可以把W - 1个划分点作为线段树的叶子，每个点如果被划分就设为1， 没有划分设为0，那么最长的w就是线段树统计出的最长的连续0的个数+1.

因为最长连续0不符合区间加法，所以要对线段树维护的区间信息进行扩充，即维护这个区间【从左边开始的连续0的数量】，【从右边开始的连续0的数量】，【是否全部为0】，【最大连续0四个量】。

为什么要这么扩充？，下面来看一下一个区间的最大连续0是如何通过两个子区间求出：

相信大家都接触过分治法求最大连续和，原理是一样的，一个区间的【最大连续0】 = max（左区间的最大连续0， 右区间的最大连续0，跨越中间的最大连续0）

左右区间的最大连续0递归就可以

跨越中间的最大连续0 = 左区间【从右边开始的连续0】 + 右区间【从左开始的连续0】，为了求跨越中间的最大连续0我们的线段树要维护这两个量

那么【是否全为0】这个信息是干什么的呢？他是用来更新【从左边开始的连续0】以及【从右边开始的连续0】的

一个区间【从左边开始的连续0】 = 左区间【从左边开始的连续0】 + （左区间是否全为0） ？ 右区间【从左边开始的连续0】 ： 0

一个区间【从右边开始的连续0】 = 右区间【从右边开始的连续0】 + （右区间是否全为0） ？ 左区间【从右边开始的连续0】 ： 0

至此区间信息就完全了，可以用线段树求解了

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 2 * 1e5 + 10;struct SegTree { ll ls, rs, max0; bool is_all0;}segTree[2][maxn<<2];void pushup(int root, int flag) { SegTree &cur = segTree[flag][root], &lc = segTree[flag][root<<1], &rc = segTree[flag][root<<1|1]; cur.ls = lc.ls + (lc.is_all0 ? rc.ls : 0); cur.rs = rc.rs + (rc.is_all0 ? lc.rs : 0); cur.max0 = max(lc.rs + rc.ls, max(lc.max0, rc.max0)); cur.is_all0 = lc.is_all0 && rc.is_all0;}void build(int L, int R, int root, int flag) { if (L == R) { segTree[flag][root].ls = segTree[flag][root].rs = segTree[flag][root].max0 = 1; segTree[flag][root].is_all0 = true; return; } int mid = (L + R)>>1; build(L, mid, root<<1, flag); build(mid + 1, R, root<<1|1, flag); pushup(root, flag);}void update_node(int L, int R, int root, int pos, int flag) { if (L == R) { segTree[flag][root].ls = segTree[flag][root].rs = segTree[flag][root].max0 = 0; segTree[flag][root].is_all0 = false; return; } int mid = (L + R)>>1; if (pos <= mid) { update_node(L, mid, root<<1, pos, flag); } else { update_node(mid + 1, R, root<<1|1, pos, flag); } pushup(root, flag);}ll query(int L, int R, int root, int qL, int qR, int flag) { if (qL <= L && R <= qR) { return segTree[flag][root].max0; } int mid = (L + R)>>1; ll temp = 0; if (qL <= mid) { temp = max(temp, query(L, mid, root<<1, qL, qR, flag)); } if (qR > mid) { temp = max(temp, query(mid + 1, R, root<<1|1, qL, qR, flag)); } return temp;}int main(){ int W, H, q, x; char c[5]; while (scanf("%d %d %d", &W, &H, &q) == 3) { build(1, W - 1, 1, 0); build(1, H - 1, 1, 1); while (q--) { scanf("%s %d", c, &x); if (c[0] == 'V') { update_node(1, W - 1, 1, x, 0); } else { update_node(1, H - 1, 1, x, 1); } printf("%I64d\n", (query(1, W - 1, 1, 1, W - 1, 0) + 1) * (query(1, H - 1, 1, 1, H - 1, 1) + 1)); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。