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


0 0 投票数
评分

最大重叠点

测试数据下载

假设存在一个点x,是最大覆盖点,被a个区间覆盖,但是,不是某个区间的端点

下面证明一定有一个点y,也和x一样,被这a个区间覆盖,且 y 是某个区间的端点

因为x被a个区间覆盖,所以x一定大于等于这a个区间的左端点在最大值,小于等于这a个区间的右端点的最小值

取这a个区间的左端点的最大值为y

下面说明这个y也同样被这a个区间覆盖

即需要证明y也是小于等于这个a个区间的右端点的最小值

反证法

假设存在一个区间的右端点,k,k比y小

那么y就被小于a个区间覆盖

y就不是最大重叠点,最大重叠点只有x

但是如果k小于y成立

y是所有左端点中最大值

这意味着k小于了这a个区间中左端点在最大值

但是由上面的分析

x一定大于等于这a个区间的左端点在最大值,小于等于这a个区间的右端点的最小值

那么这a个区间的左端点在最大值一定小于等于这a个区间的右端点的最小值

所以不可能存在一个右端点,比左端点的最大值要更小

与假设矛盾

这样的k不存在

所以y不可能被小于a个区间覆盖

所以y也同样被这a个区间覆盖

由于y是这a个区间的左端点的最大值

显然y是端点

这道题解题的关键已经在题目中明确了

使红黑树记录所有的端点

左端点关联+1值,右端点关联-1值

并且给树中的每个结点扩张一个额外的信息来维护最大重叠点

把这段话理解了,这道题也就好做了

意思是每个key关联的value,不是1就是-1

然后要维护额外的信息

首先分析这道题的做法

简单说就是差分、前缀和

只要把每个结点的信息维护好,做起来还是很快的

主要就是说,遇到一个区间的左端点,加1,意味着后面每个点的覆盖次数就比原来多了1,比如从0变成1,然后遇到右端点,减1,意味着右端点以后的每个点的重叠次数从1变成了0

同样的,如果有多个区间,从1变成2、变成3……

那么这个就相当于是最大的重叠次数了

后面只要维护好这个sum和,以及最大重叠次数(需要用到sum),以及最大重叠点(根据最大重叠次数)

当然我做的时候还是遇到了各种问题,下面的代码我会一一列出我踩过的坑

对每个结点增加以下拓展数据域

sum表示前缀和,表示从第1个结点到当前结点的value的和

maxOverlapTimesmaxOverlapPoint分别记录当前的最大重叠次数和最大重叠点坐标

parent表示这个结点的父亲,只是为了方便维护而设置的

显然这些数据域都是需要维护的

新建结点的时候可以不考虑结点的维护,但是当插入、旋转、删除的时候,就不得不维护

因为maintain只维护拓展数据域成员,不会维护红黑树的颜色

同样对红黑树的维护只维护颜色等,不会改变数据域成员信息

所以维护数据域和维护红色黑色的前后顺序是无所谓的

这里在插入新结点以后就直接对新结点的数据域进行了维护

h.left = put(h.left, key, val);
h.left.parent = h; // 设置父节点
maintainAllOverlapInformation(h.left); // 从左孩子一路维护到树根

因为数据会出现对同一个点的多次操作

所以这里要保证key一样的节点也能够被插入

两种做法

  • 第一种是允许树中出现key一样的节点有多个

但是这样做就要特别注意维护key一样的节点插入在哪儿、每次信息(插入、删除)的操作的前后顺序

  • 第二种做法是还是保留key唯一

如果插入的key已经存在,直接在原来的value上加减修改

int cmp = key.compareTo(h.key);
if (cmp < 0) {
    h.left = put(h.left, key, val);
    h.left.parent = h; // 设置父节点
    maintainAllOverlapInformation(h.left); // 从左孩子一路维护到树根
} else if (cmp > 0) {
    h.right = put(h.right, key, val);
    h.right.parent = h;
    maintainAllOverlapInformation(h.right);
} else {
    h.val += val;
}

分析完了插入

下面分析删除的时候需要维护什么信息

事实上这道题不需要删除操作,这一点在下面会详细说明

一开始我考虑的是需要删除的

那么删除的时候需要维护的信息是balance的时候

在删除操作最后,有一个重新调整平衡度的函数,在调整平衡度的时候,要同步维护拓展数据域

如果是对结点hbalance操作,显然要做

maintainAllOverlapInformation(h.left);
maintainAllOverlapInformation(h.right);

也就是说要从h的左右孩子一路维护到树根

最后是旋转操作

旋转操作首先要维护父结点的正确性

以右旋转为例

if (x.right != null) x.right.parent = h;
x.parent = h.parent;
if (h.parent == null)
    root = x;
else if (h == h.parent.left)
    h.parent.left = x;
else
    h.parent.right = x;
x.right = h;
h.parent = x;

如果只是一个结点指向自己的孩子

这部分代码是简单的

但是要维护双向的指向,也就是父亲指向孩子,孩子也要指向父亲,那么在处理的时候就要多一些判断,比如判断是不是为空、判断是左孩子还是右孩子

这部分父结点如果维护正确了,对下面的maintain实现是有帮助的,因为后面的代码就会简单很多

这部分的调试花了我很长的时间,一开始总是维护错误,导致各种NullPointer异常

但是调试对了以后,仔细想想还是能想明白的

画张图,连几个箭头,上面的关系是显然的

在旋转的时候,不需要把x和h结点从自己开始一路维护到树根

因为不会影响其他部分的信息,所以只要修改自己相关的信息就可以了

// 左旋转、右旋转,只需要维护涉及到的这两个可以了
maintainOverlapInformation(h);
maintainOverlapInformation(x);

维护数据域

这里的思路是这样的

sum表示前缀和,表示从第1个结点到当前结点的value的和

maxOverlapTimesmaxOverlapPoint分别记录当前的最大重叠次数和最大重叠点坐标

首先要计算x的sum,令x的sum先等于x的value,因这部分肯定是要加的

分别看左右孩子是不是为空,不为空就加上他们的sum

x.sum = (x.val);
if (x.left != null)
    x.sum += x.left.sum;

if (x.right != null)
    x.sum += x.right.sum;

然后最大重叠点可能出现在左边,可能就是x自己,可能出现在右边

分别计算这三种情况的最大重叠次数

int maxInLeft = 0;
if (x.left != null)
    maxInLeft = x.left.maxOverlapTimes;

如果出现在左边,那么记最大重叠次数在左子树的次数为左子树的最大重叠次数(如果存在)

int maxInX = x.val;
if (x.left != null)
    maxInX += x.left.sum;

如果就是x的本身,那么就是左子树的前缀和(如果存在),加上x的value

int maxInRight = x.val;
if (x.left != null)
    maxInRight += x.left.sum;
if (x.right != null)
    maxInRight += x.right.maxOverlapTimes;

如果在右边,那么就是x自己的value、左子树的前缀和(如果存在)、右子树的最大重叠次数(如果存在)的和

x.maxOverlapTimes = Math.max(Math.max(maxInLeft, maxInX), maxInRight);

取三者最大值为最大重叠次数

因为考虑到有可能其中两个或者三个的最大值是一样的

那么按照题目要求,输出最前面的

所以下面的这个if条件句是有前后顺序的

首先看是不是在左边,然后看x,最后看右边

if (x.left != null && x.maxOverlapTimes == maxInLeft) {
    x.maxOverlapPoint = x.left.maxOverlapPoint;
} else if (x.maxOverlapTimes == maxInX) {
    x.maxOverlapPoint = x.key;
} else if (x.right != null) {
    x.maxOverlapPoint = x.right.maxOverlapPoint;
}

当满足条件的时候,就设置最大重叠点为对应的最大重叠点

有人说这样的写法不够好看,因为代码中充斥着大量的 if ( x != null)的判断

一种更加优雅的做法是,新建一个结点表示null,例如叫做nil(或者叫node a)

当某个结点为null的时候,不是真的令他为null,而是令他为那个表示null的结点nil(或者叫node a)

而这个结点,仅仅表示他是null,其实也是有数据域的,例如它的size为0,它的sum为0,它的maxOverlapPoint为0(或者-1等)

如果需要判断子树是不是为空,就看是不是指向这个特殊的结点

如果需要子树的某个数据域,也不需要特殊判断,直接拿来用就好了

所以,在进行

x.sum = (x.val);
if (x.left != null) x.sum += x.left.sum;
if (x.right != null) x.sum += x.right.sum;

的时候,可以直接写成

x.sum = x.val + x.left.sum + x.right.sum;

这时候,完全不用担心x的左子树为空而导致NullPointerException

x的左子树就算为空,它指向的也是那个表示空而实际上是一个对象的结点

所以不会出现x的left是null而没有x.left.sum这种事

并且,它也有数据域成员sum,而sum就等于0,所以直接这样加,不需要做任何特判。反正加0和不加是一样的

上面给出的是单点维护

如果是要维护到树根

就是一个循环

void maintainAllOverlapInformation(Node x) {
    while (x != null) {
        maintainOverlapInformation(x);
        x = x.parent;
    }
}

所有的部分都处理完了,下面就是main函数

  • 如果读入的是1,那么要把区间[l,r]加入到红黑树
  • 如果读入的是2,那么要把区间[l,r]从树中删除
  • 如果读入的是3,那么直接输出root的maxOverlapPoint
case 1:
l = ni();
r = ni();
tree.put(l, 1);
tree.put(r + 1, -1);
case 2:
l = ni();
r = ni();
tree.put(l, -1);
tree.put(r + 1, 1);
case 3:
System.out.printf("%d\n", tree.findPom());
break;
public int findPom() {
    return root.maxOverlapPoint;
}

这里有2个坑

要说明一下

一开始我做的时候,对操作2是做delete(l)和delete(r)操作

但是这样是不对的

试考虑这样一种情况

如果第一次插入的区间是[1,2]

然后插入一个区间[2,3]

对于点2,有+1,也有-1

仅仅考虑插入部分的代码是可以实现的

只要保证红黑树中允许插入key相同的结点就行了

红黑树中有多个key一样的结点

但是!

这时候如果要删除[2,3]

如果仅仅以key=2来做检查

会有2个结点

到底删掉哪一个?

显然是做不到的

没有办法知哪个才是和[2,3]配对的那个

我不知道那个是+1还是-1

同样的,如果插入[1,5]、[5,8]、[5,20]、[3,5],删除[1,5]

我也不知道到底删掉哪个5

所以是不行的

因此才会出现上文说的,其实不能用delete,而要反向插入

也就是说,正经的插入,是l做+1,r做-1

那么删除的时候,就只要插入一个l为-1,r为+1,相当于抵消了呀

这样做的话,甚至连key相同的结点的插入都省略了

只要看这个key是不是有过

有过,直接在原来的value上加减现在新的这个value就行了

else {
    h.val += val;
}

第二个坑

我一直做的是

put(l);
put(r);

这里的r是要加1的

原因是因为这里维护的是差分

语文不好,表述不清这里的逻辑,反正,维护差分,大家就都是这么写的,加1

put(l);
put(r + 1);

至此,所有代码完成

给出完整代码

import java.io.ByteArrayInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

public class Main {

    static InputStream is;
    static PrintWriter out;
    static String INPUT = "";

    private static byte[] inbuf = new byte[1024];
    static int lenbuf = 0, ptrbuf = 0;

    private static int readByte() {
        if (lenbuf == -1)
            throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0)
                return -1;
        }
        return inbuf[ptrbuf++];
    }

    private static int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        RedBlackBST tree = new RedBlackBST();
        // Java读入加速
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        int q = ni();
        while (q-- != 0) {
            int cmd = ni();
            int l, r;
            switch (cmd) {
            case 1:
                // 插入区间
                l = ni();
                r = ni();
                tree.put(l, 1);
                tree.put(r + 1, -1); // 差分加1
                break;
            case 2:
                // 删除区间不能用delete
                l = ni();
                r = ni();
                tree.put(l, -1);
                tree.put(r + 1, 1);
                break;
            case 3:
                System.out.printf("%d\n", tree.findPom());
                break;
            default:
                break;
            }
        }
    }
}

class RedBlackBST {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    private class Node {
        private Integer key;
        private Integer val;
        private Node left, right;
        private boolean color;
        private int size;
        private int sum;
        private int maxOverlapTimes;
        private int maxOverlapPoint;
        private Node parent;

        public Node(Integer key, Integer val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }
    }

    public RedBlackBST() {
    }

    public int findPom() {
        return root.maxOverlapPoint;
    }

    public void debug() {
        if (root == null) {
            System.out.println("null");
            return;
        }
        System.out.println("mop: " + root.maxOverlapPoint);
        System.out.println("mot: " + root.maxOverlapTimes);
    }

    private boolean isRed(Node x) {
        if (x == null)
            return false;
        return x.color == RED;
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        return x.size;
    }

    public int size() {
        return size(root);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public Integer get(Integer key) {
        if (key == null)
            throw new IllegalArgumentException("argument to get() is null");
        return get(root, key);
    }

    private Integer get(Node x, Integer key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x.val;
        }
        return null;
    }

    public boolean contains(Integer key) {
        return get(key) != null;
    }

    public void put(Integer key, Integer val) {
        root = put(root, key, val);
        root.color = BLACK;
    }

    private Node put(Node h, Integer key, Integer val) {
        if (h == null)
            return new Node(key, val, RED, 1);

        /*
         * 因为maintain只维护拓展数据域成员,不会维护红黑树的颜色 同样对红黑树的维护只维护颜色等,不会改变数据域成员信息
         * 所以维护数据域和维护红色黑色的前后顺序是无所谓的 这里在插入新结点以后就直接对新结点的数据域进行了维护
         */
        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, val);
            h.left.parent = h; // 设置父节点
            maintainAllOverlapInformation(h.left); // 从左孩子一路维护到树根
        } else if (cmp > 0) {
            h.right = put(h.right, key, val);
            h.right.parent = h;
            maintainAllOverlapInformation(h.right);
        } else {
            /*
             * 因为数据会出现对同一个点的多次操作 所以这里要保证key一样的节点也能够被插入 两种做法,第一种是允许树中出现key一样的节点有多个
             * 但是这样做就要特别注意维护key一样的节点插入在哪儿、每次信息(插入、删除)的操作的前后顺序 第二种做法是还是保留key唯一
             * 如果插入的key已经存在,直接在原来的value上加减修改
             */
            h.val += val;
        }

        if (isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right))
            flipColors(h);
        h.size = size(h.left) + size(h.right) + 1;

        return h;
    }

    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        if (x.right != null)
            x.right.parent = h;
        x.parent = h.parent;
        if (h.parent == null)
            root = x;
        else if (h == h.parent.left)
            h.parent.left = x;
        else
            h.parent.right = x;
        x.right = h;
        h.parent = x;
        x.color = x.right.color;
        x.right.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        // 左旋转、右旋转,只需要维护涉及到的这两个可以了
        maintainOverlapInformation(h);
        maintainOverlapInformation(x);
        return x;
    }

    private Node rotateLeft(Node h) {
        Node x = h.right;
        // 较大节点存在左子树的话,变成较小链接的右链接
        h.right = x.left;
        // 较大节点变成根节点
        if (x.left != null)
            x.left.parent = h;
        x.parent = h.parent;
        if (h.parent == null)
            root = x;
        else if (h == h.parent.left)
            h.parent.left = x;
        else
            h.parent.right = x;
        x.left = h;
        h.parent = x;
        // 较大节点的颜色与它左子树的颜色一样,并设置左子树颜色为红色
        x.color = x.left.color;
        x.left.color = RED;
        // 只是旋转,所以以x为根的子树的结点数不会变化,但是要重新计算h的子节点数
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        // 左旋转、右旋转,只需要维护涉及到的这两个可以了
        maintainOverlapInformation(h);
        maintainOverlapInformation(x);
        return x;
    }

    private void flipColors(Node h) {
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }

    void maintainOverlapInformation(Node x) {
        if (x != null) {
            x.sum = (x.val);
            if (x.left != null)
                x.sum += x.left.sum;

            if (x.right != null)
                x.sum += x.right.sum;

            int maxInLeft = 0;
            if (x.left != null)
                maxInLeft = x.left.maxOverlapTimes;
            int maxInX = x.val;
            if (x.left != null)
                maxInX += x.left.sum;
            int maxInRight = x.val;
            if (x.left != null)
                maxInRight += x.left.sum;
            if (x.right != null)
                maxInRight += x.right.maxOverlapTimes;
            x.maxOverlapTimes = Math.max(Math.max(maxInLeft, maxInX), maxInRight);

            if (x.left != null && x.maxOverlapTimes == maxInLeft) {
                x.maxOverlapPoint = x.left.maxOverlapPoint;
            } else if (x.maxOverlapTimes == maxInX) {
                x.maxOverlapPoint = x.key;
            } else if (x.right != null) {
                x.maxOverlapPoint = x.right.maxOverlapPoint;
            }
        }
    }

    void maintainAllOverlapInformation(Node x) {
        while (x != null) {
            maintainOverlapInformation(x);
            x = x.parent;
        }
    }

}

其他红黑树相关的问题

圆上相交弦

2018-4-11 61
0 0 投票数
评分
6条留言
订阅评论
提醒
guest

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

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
6 评论
内联反馈
查看所有评论
AAA
AAA (@guest_1966) Chrome 80.0.3987.122 Windows 10
游客
2020年3月3日 17:54

tql

Kuroko
Kuroko (@guest_784) Chrome 77.0.3865.90 Windows 10
游客
2019年10月13日 19:31

orz

a
a (@guest_697) Chrome 69.0.3497.100 Windows 10
游客
2019年9月28日 11:02

orz

elif
elif (@guest_654) Firefox 69.0 Windows 10
游客
2019年9月20日 18:24

youxiu

11
11 (@guest_99) Firefox 63.0 Windows 10
游客
2018年11月2日 18:53

orz

k
k(@673c1e5c150ad6406163daeb4a78ecdf) Firefox 62.0 Windows 10
2018年10月22日 19:15

orz