USACO 08 Feb. Gold C Hotel

POJ3667　BZOJ1593　洛谷2894
线段树
学线段树时，过了惰性标记后的下一个坎：区间合并与拆分。
每个结点上，除了要存该区间内空闲区间的最大长度，还要多维护两个值：从左/右端数起的空闲区间的长度。

查找最左端的长度≥x的区间时：

1. 如果该结点的

程序中有大量重复，所以有多处重构。

#include <cstdio> const int MAXN = 5e4; char ch; int integer; int readint() { while ((ch = getchar()) < '0' || ch > '9'); integer = 0; do { integer = (integer << 3) + (integer << 1) + ch - '0'; } while ((ch = getchar()) >= '0' && ch <= '9'); return integer; } int max(const int &a, const int &b, const int &c) { if (a > b) return a > c ? a : c; return b > c ? b : c; } struct TreeNode { int lb, rb, size, cmax, lmax, rmax; TreeNode *lc, *rc; TreeNode() {} TreeNode(int lb, int rb, int sz, TreeNode *lc, TreeNode *rc) : lb(lb), rb(rb), size(sz), cmax(sz), lmax(sz), rmax(sz), lc(lc), rc(rc) {} }tree[1 << 17], *new_node = tree; TreeNode* build_tree(int l, int r) { if (l == r) *new_node = TreeNode(l, r, r - l + 1, NULL, NULL); else { TreeNode *tmplc = build_tree(l, l + r >> 1); TreeNode *tmprc = build_tree((l + r >> 1) + 1, r); *new_node = TreeNode(l, r, r - l + 1, tmplc, tmprc); } return new_node++; } int x, d; bool is_full(TreeNode *node) { return node->cmax == 0; } bool is_empty(TreeNode *node) { return node->cmax == node->size; } void node_fill(TreeNode *node) { node->cmax = node->lmax = node->rmax = 0; } void node_empty(TreeNode *node) { node->cmax = node->lmax = node->rmax = node->size; } void propagate(TreeNode *node) { //标记下传 if (is_empty(node)) { node_empty(node->lc); node_empty(node->rc); } else if (is_full(node)) { node_fill(node->lc); node_fill(node->rc); } } void inherit(TreeNode *node) { //标记上传+合并 if (is_full(node->lc) && is_full(node->rc)) { node_fill(node); return; } if (is_empty(node->lc) && is_empty(node->rc)) { node_empty(node); return; } node->lmax = is_empty(node->lc) ? node->lc->size + node->rc->lmax : node->lc->lmax; node->rmax = is_empty(node->rc) ? node->rc->size + node->lc->rmax : node->rc->rmax; node->cmax = max(node->lc->cmax, node->rc->cmax, node->lc->rmax + node->rc->lmax); } int query(TreeNode *node) { propagate(node); if (node->lc->cmax >= d) return query(node->lc); if (node->lc->rmax + node->rc->lmax >= d) return node->lc->rb - node->lc->rmax + 1; if (node->rc->cmax >= d) return query(node->rc); return 0; } void checkin(TreeNode *node) { if (node->rb < x || d < node->lb) return; if (x <= node->lb && node->rb <= d) { node_fill(node); return; } propagate(node); checkin(node->lc); checkin(node->rc); inherit(node); } void checkout(TreeNode *node) { if (node->rb < x || d < node->lb) return; if (x <= node->lb && node->rb <= d) { node_empty(node); return; } propagate(node); checkout(node->lc); checkout(node->rc); inherit(node); } int main() { int N = readint(); TreeNode *root = build_tree(1, N); int M = readint(); while (M--) if (readint() == 1) { d = readint(); x = query(root); printf("%d\n", x); if (x) { d += x - 1; checkin(root); } } else { x = readint(); d = x + readint() - 1; checkout(root); } return 0; } 

转载于:https://www.cnblogs.com/P6174/p/7381384.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95838411

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。