计蒜客 - 黑白石头

作者: jxtxzzw | 来源:发表于2020-03-16 21:29 被阅读0次

计蒜客 - 黑白石头

沙滩上有一些石头，石头的颜色是白色或者黑色。小羊会魔法，它能把连续一段的石头，黑色变成白色，白色变成黑色。小羊喜欢黑色，她想知道某些区间中最长的连续黑石头是多少个。

输入格式

第一行一个整数 $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] 最长连续黑色石头的长度。

输出格式

当 $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();
    }
}

计蒜客 - 黑白石头

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读