﻿最大重叠点 – jxtxzzw个人博客

# 最大重叠点

4月11日 · 2018年

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

y是所有左端点中最大值

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

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

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

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

``````h.left = put(h.left, key, val);
h.left.parent = h; // 设置父节点
maintainAllOverlapInformation(欢迎访问jxtxzzw个人博客h.left); // 从左孩子一路维护到树根
``````

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

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

``````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;
}
``````

``````maintainAllOverlapInformation(h.left);
maintainAllOverlapInformation(h.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;
``````

``````// 左旋转、右旋转，只需要维护涉及到的这两欢迎访问jxtxzzw个人博客个可以了
maintainOverlapInformation(h);
maintainOverlapInformation(x);
``````

`sum`表示前缀和，表示从第1个结点到当前结点的`value`Copyright Reserved @jxtxzzw

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

``````x.sum = (x.val);
if (x.left != n反采集功能启动ull)
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.max欢迎访问jxtxzzw个人博客OverlapTimes;
``````

``````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;
}
``````

``````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的左子树就算为空，它指向的也是那个表示空而实际上是一个对象的结点

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

• 如果读入的是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() {欢迎访问jxtxzzw个人博客
return root.maxOverlapPoint;
}
``````

``````else {
h.val += val;
}
``````

``````put(l);
put(r);
``````

``````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;

if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
} 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;
}

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

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

}
``````

0 条回应