计蒜客 – 黑白石头

1544 0 2020年3月6日

本文写于 2020年03月06日，距今已超过 1 年，距 2020年03月26日 的最后一次修改也已超过 3 个月，部分内容可能已经过时，您可以按需阅读。如果图片无法显示或者下载链接失效，请给我反馈，谢谢！


0 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] 最长连续黑色石头的长度。

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

更多线段树的题目

计蒜客 – 公告板

2020-3-5 0

计蒜客 – 最甜的苹果

2020-3-4 1

计蒜客 – 斑点蛇

2020-3-4 0
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时，网络请求的数据包含浏览器版本、操作系统版本和 IP 地址；您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动；根据浏览器默认行为、操作系统设置和安全防护软件的设置不同，您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
（可选）如果您也有个人网站，不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论