
计蒜客 – 黑白石头
沙滩上有一些石头,石头的颜色是白色或者黑色。小羊会魔法,它能把连续一段的石头,黑色变成白色,白色变成黑色。小羊喜欢黑色,她想知道某些区间中最长的连续黑石头是多少个。
输入格式
第一行一个整数 $n(1\leq n\leq 100000)$。
第二行 $n$ 个整数,表示石头的颜色,$0$ 是白色,$1$ 是黑色。
第三行一个整数 $m(1\leq m\leq 100000)$。
接下来 $m$ 行,每行三个整数 $x,i,j$。
$x = 1$ 表示改变 [i,j]
石头的颜色。
$x = 0$ 表示询问 [i,j]
最长连续黑色石头的长度。
4 1 0 1 0 5 0 1 4 1 2 3 0 1 4 1 3 3 0 4 4
输出格式
当 $x = 0$ 时,输出答案。
1 2 0
这道题算比较难的了,主要是需要维护最左端和最右端的连续黑白石头个数。
private void pushUp(NODE node) throws Exception { NODE leftChild = getLeftChild(node); NODE rightChild = getRightChild(node); int tmp; // 左孩子 // 左边黑色石头的长度 tmp = leftChild.getCache(NODE.identifier.LEFT_BLACK); if (leftChild.getRange() == tmp) { // 如果左孩子全是黑的,就加上右孩子的左边黑色 tmp += rightChild.getCache(NODE.identifier.LEFT_BLACK); } node.setCache(NODE.identifier.LEFT_BLACK, tmp); // 左边白色石头的长度 tmp = leftChild.getCache(NODE.identifier.LEFT_WHITE); if (leftChild.getRange() == tmp) { tmp += rightChild.getCache(NODE.identifier.LEFT_WHITE); } node.setCache(NODE.identifier.LEFT_WHITE, tmp); // 右孩子 // 右边黑色石头的长度 tmp = rightChild.getCache(NODE.identifier.RIGHT_BLACK); if (rightChild.getRange() == tmp) { // 如果左孩子全是黑的,就加上右孩子的左边黑色 tmp += leftChild.getCache(NODE.identifier.RIGHT_BLACK); } node.setCache(NODE.identifier.RIGHT_BLACK, tmp); // 白色石头的长度 tmp = rightChild.getCache(NODE.identifier.RIGHT_WHITE); if (rightChild.getRange() == tmp) { tmp += leftChild.getCache(NODE.identifier.RIGHT_WHITE); } node.setCache(NODE.identifier.RIGHT_WHITE, tmp); // 取最大的,要么是左孩子最大的,要么是右孩子最大的,要么是跨越左右的 tmp = Math.max(leftChild.getCache(NODE.identifier.MAX_BLACK), rightChild.getCache(NODE.identifier.MAX_BLACK)); tmp = Math.max(tmp, leftChild.getCache(NODE.identifier.RIGHT_BLACK) + rightChild.getCache(NODE.identifier.LEFT_BLACK)); node.setCache(NODE.identifier.MAX_BLACK, tmp); tmp = Math.max(leftChild.getCache(NODE.identifier.MAX_WHITE), rightChild.getCache(NODE.identifier.MAX_WHITE)); tmp = Math.max(tmp, leftChild.getCache(NODE.identifier.RIGHT_WHITE) + rightChild.getCache(NODE.identifier.LEFT_WHITE)); node.setCache(NODE.identifier.MAX_WHITE, tmp); }
理解起来还是很容易的,基本就是 if-else 的堆叠。
需要注意在 build()
和 update()
的时候都需要 pushUp()
,即重新维护左右端连续石头的个数。
其他的都和普通线段树是一样的。
查询也是一个难点。
首先,查询也需要 pushUp()
。
其次,连续黑色石头的长度,由于我们在上面维护的时候是可以跨越区域的,所以这里必须做一次校验,是不是等于给定区间的长度,不能直接 leftChild.RIGHT_BLACK + rightChild.LEFT_BLACK
,这可能是会超过 from -> to
的范围的。
int l = Math.min(node.getMid() - from + 1, getLeftChild(node).getCache(NODE.identifier.RIGHT_BLACK)); int r = Math.min(to - node.getMid(), getRightChild(node).getCache(NODE.identifier.LEFT_BLACK)); // 坑,注意左右连续黑色块可能会超过下标的范围 result = Math.max(result, l + r);
还有需要注意的是,这里不再是 if (to < mid) then (query(left))
,而是采用了 3 个 if 并排的方式,一旦出现左边或者右边,则递归地调用。
public int query(int from, int to, int index) throws Exception { NODE node = data[index]; if (node.isCompletelyCovered(from, to)) { return node.getCache(NODE.identifier.MAX_BLACK); } pullDownLazy(node); int result = 0; // 查询结果 if (from <= node.getMid()) result = Math.max(result, query(from, to, node.getLeftChildIndex())); if (to > node.getMid()) result = Math.max(result, query(from, to, node.getRightChildIndex())); if (from <= node.getMid() && to > node.getMid()) { int l = Math.min(node.getMid() - from + 1, getLeftChild(node).getCache(NODE.identifier.RIGHT_BLACK)); int r = Math.min(to - node.getMid(), getRightChild(node).getCache(NODE.identifier.LEFT_BLACK)); // 坑,注意左右连续黑色块可能会超过下标的范围 result = Math.max(result, l + r); } pushUp(node); return result; }
最后的完整代码只通过了 4 组数据,最后一组数据内存超限,想来是 Java 的锅。
可能把有些类直接开成数组,就可以解决这个问题,但是我也懒的搞了。
import java.util.Scanner; public class OJ { static Scanner in = new Scanner(System.in); public static void main(String[] args) throws Exception { int numbers = in.nextInt(); SegmentTree st = new SegmentTree(in, numbers); int queries = in.nextInt(); int begin; int end; for (int i = 0; i < queries; ++i) { int command = in.nextInt(); begin = in.nextInt(); end = in.nextInt(); switch (command) { case 0: System.out.println(st.query(begin, end, 1)); break; case 1: st.update(begin, end, 1); break; } } } } class SegmentTree { private NODE[] data; Scanner in; public SegmentTree(Scanner in, int length) throws Exception { this.in = in; data = new NODE[length * 4]; build(1, 1, length); } private boolean isPrimarySegment(int left, int right) { return left == right; } public void build(int nodeIndex, int left, int right) throws Exception { NODE node; if (isPrimarySegment(left, right)) { boolean black = in.nextInt() == 1; node = new NODE(nodeIndex, left, right, black); } else { int mid = (left + right) >>> 1; build(nodeIndex * 2, left, mid); build(nodeIndex * 2 + 1, mid + 1, right); node = new NODE(nodeIndex, left, right); pushUp(node); } data[nodeIndex] = node; } private NODE getLeftChild(NODE node) { return data[node.getLeftChildIndex()]; } private NODE getRightChild(NODE node) { return data[node.getRightChildIndex()]; } private void pushUp(NODE node) throws Exception { NODE leftChild = getLeftChild(node); NODE rightChild = getRightChild(node); int tmp; // 左孩子 // 左边黑色石头的长度 tmp = leftChild.getCache(NODE.identifier.LEFT_BLACK); if (leftChild.getRange() == tmp) { // 如果左孩子全是黑的,就加上右孩子的左边黑色 tmp += rightChild.getCache(NODE.identifier.LEFT_BLACK); } node.setCache(NODE.identifier.LEFT_BLACK, tmp); // 左边白色石头的长度 tmp = leftChild.getCache(NODE.identifier.LEFT_WHITE); if (leftChild.getRange() == tmp) { tmp += rightChild.getCache(NODE.identifier.LEFT_WHITE); } node.setCache(NODE.identifier.LEFT_WHITE, tmp); // 右孩子 // 右边黑色石头的长度 tmp = rightChild.getCache(NODE.identifier.RIGHT_BLACK); if (rightChild.getRange() == tmp) { // 如果左孩子全是黑的,就加上右孩子的左边黑色 tmp += leftChild.getCache(NODE.identifier.RIGHT_BLACK); } node.setCache(NODE.identifier.RIGHT_BLACK, tmp); // 白色石头的长度 tmp = rightChild.getCache(NODE.identifier.RIGHT_WHITE); if (rightChild.getRange() == tmp) { tmp += leftChild.getCache(NODE.identifier.RIGHT_WHITE); } node.setCache(NODE.identifier.RIGHT_WHITE, tmp); // 取最大的,要么是左孩子最大的,要么是右孩子最大的,要么是跨越左右的 tmp = Math.max(leftChild.getCache(NODE.identifier.MAX_BLACK), rightChild.getCache(NODE.identifier.MAX_BLACK)); tmp = Math.max(tmp, leftChild.getCache(NODE.identifier.RIGHT_BLACK) + rightChild.getCache(NODE.identifier.LEFT_BLACK)); node.setCache(NODE.identifier.MAX_BLACK, tmp); tmp = Math.max(leftChild.getCache(NODE.identifier.MAX_WHITE), rightChild.getCache(NODE.identifier.MAX_WHITE)); tmp = Math.max(tmp, leftChild.getCache(NODE.identifier.RIGHT_WHITE) + rightChild.getCache(NODE.identifier.LEFT_WHITE)); node.setCache(NODE.identifier.MAX_WHITE, tmp); } public void update(int from, int to, int index) throws Exception { NODE node = data[index]; if (node.isCompletelyCovered(from, to)) { node.change(); return; } pullDownLazy(node); if (to > node.getMid()) { update(from, to, node.getRightChildIndex()); } if (from < node.getMid() + 1) { update(from, to, node.getLeftChildIndex()); } pushUp(node); } private void pullDownLazy(NODE node) { if (node.shouldChange()) { getLeftChild(node).change(); getRightChild(node).change(); node.clearChange(); } } public int query(int from, int to, int index) throws Exception { NODE node = data[index]; if (node.isCompletelyCovered(from, to)) { return node.getCache(NODE.identifier.MAX_BLACK); } pullDownLazy(node); int result = 0; // 查询结果 if (from <= node.getMid()) result = Math.max(result, query(from, to, node.getLeftChildIndex())); if (to > node.getMid()) result = Math.max(result, query(from, to, node.getRightChildIndex())); if (from <= node.getMid() && to > node.getMid()) { int l = Math.min(node.getMid() - from + 1, getLeftChild(node).getCache(NODE.identifier.RIGHT_BLACK)); int r = Math.min(to - node.getMid(), getRightChild(node).getCache(NODE.identifier.LEFT_BLACK)); // 坑,注意左右连续黑色块可能会超过下标的范围 result = Math.max(result, l + r); } pushUp(node); return result; } } class NODE { private int index; private int left; private int right; private int[] cache = new int[6]; private boolean askToChange = false; public enum identifier {LEFT_WHITE, LEFT_BLACK, RIGHT_WHITE, RIGHT_BLACK, MAX_BLACK, MAX_WHITE} public NODE(int index, int left, int right) { this.index = index; this.left = left; this.right = right; } public NODE(int index, int left, int right, boolean black) throws Exception { this(index, left, right); assert left == right; // 必须在叶子节点 setCache(identifier.LEFT_BLACK, black ? 1 : 0); setCache(identifier.RIGHT_BLACK, black ? 1 : 0); setCache(identifier.MAX_BLACK, black ? 1 : 0); setCache(identifier.LEFT_WHITE, black ? 0 : 1); setCache(identifier.RIGHT_WHITE, black ? 0 : 1); setCache(identifier.MAX_WHITE, black ? 0 : 1); } public int getRange() { return right - left + 1; } public int getMid() { return (left + right) >>> 1; } public boolean isCompletelyCovered(int from, int to) { return from <= left && to >= right; } public int getLeftChildIndex() { return index * 2; } public int getRightChildIndex() { return index * 2 + 1; } public int getCache(identifier idx) throws Exception { switch (idx) { case LEFT_BLACK: return cache[0]; case LEFT_WHITE: return cache[1]; case RIGHT_BLACK: return cache[2]; case RIGHT_WHITE: return cache[3]; case MAX_BLACK: return cache[4]; case MAX_WHITE: return cache[5]; } throw new Exception("Unexpected identifier"); } public void setCache(identifier idx, int value) throws Exception { switch (idx) { case LEFT_BLACK: cache[0] = value; return; case LEFT_WHITE: cache[1] = value; return; case RIGHT_BLACK: cache[2] = value; return; case RIGHT_WHITE: cache[3] = value; return; case MAX_BLACK: cache[4] = value; return; case MAX_WHITE: cache[5] = value; return; } throw new Exception("Unexpected identifier"); } private void setChange() { askToChange = !askToChange; // 延迟标记叠加 } public void clearChange() { askToChange = false; } public boolean shouldChange() { return askToChange; } public void change() { int tmp; tmp = cache[0]; cache[0] = cache[1]; cache[1] = tmp; tmp = cache[2]; cache[2] = cache[3]; cache[3] = tmp; tmp = cache[4]; cache[4] = cache[5]; cache[5] = tmp; setChange(); } }
更多线段树的题目