最大重叠点

测试数据下载

假设存在一个点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的和

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

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的时候

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

如果是对结点h做balance操作，显然要做

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的和

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

首先要计算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;
        }
    }

}