前言
どうしたら
究竟要怎样
あなたに爱を刻めるんだろう?
才能将这份爱意铭刻在你心上？
自我介绍
我是一个优雅的女孩，偶尔会有些"粗暴"。
我有一把传说中的圣剑--瑟尼欧里斯 (区间赋值)。
参考文章（详见）
Pecco 算法学习笔记(15): 珂朵莉树
5cm/s 🌸 珂朵莉树，区间染色 + 单点查询
代码模板分析
Java版做了改动，把区间R值/V值，后置于Node节点中， 用Java的TreeMap(非TreeSet)代替了C++的Set。
Java
class ODTTree {
static class Node {
int l, r, v;
public Node(int l, int r, int v) {
this.l = l;
this.r = r;
this.v = v;
}
}
TreeMap<Integer, Node> tree = new TreeMap<>();
public ODTTree() {
}
public ODTTree(int l, int r, int v) {
tree.put(l, new Node(l, r, v));
}
public void split(int l) {
Map.Entry<Integer, Node> prev = tree.floorEntry(l);
if (prev == null || prev.getKey() == l || prev.getValue().r < l) return;
Node cur = prev.getValue();
int r = cur.r, v = cur.v;
tree.remove(prev.getKey());
tree.put(prev.getKey(), new Node(cur.l, l - 1, v));
tree.put(l, new Node(l, r, v));
}
public void merge(int l, int r, int v) {
this.split(l);
this.split(r + 1);
// l闭区间, r+1开区间
tree.subMap(l, r + 1).clear();
// 再做一个合并
// 和前一个元素进行合并
Map.Entry<Integer, Node> prev = tree.floorEntry(l - 1);
if (prev != null && prev.getValue().v == v && prev.getValue().r == l - 1) {
tree.remove(prev.getKey());
l = prev.getKey();
}
// 和后一个区间进行合并
Map.Entry<Integer, Node> next = tree.ceilingEntry(r + 1);
if (next != null && next.getValue().v == v && next.getKey() == r + 1) {
tree.remove(next.getKey());
r = next.getValue().r;
}
tree.put(l, new Node(l, r, v));
}
}注: 可以根据需求，扩展查询接口
案列分析和实践
LCP 52. 二叉搜索树染色
Java
class Solution {
static
class ODTTree {
static class Node {
int l, r, v;
public Node(int l, int r, int v) {
this.l = l;
this.r = r;
this.v = v;
}
}
TreeMap<Integer, Node> tree = new TreeMap<>();
public ODTTree() {
}
public ODTTree(int l, int r, int v) {
tree.put(l, new Node(l, r, v));
}
public void split(int l) {
Map.Entry<Integer, Node> prev = tree.floorEntry(l);
if (prev == null || prev.getKey() == l || prev.getValue().r < l) return;
Node cur = prev.getValue();
int r = cur.r, v = cur.v;
tree.remove(prev.getKey());
tree.put(prev.getKey(), new Node(cur.l, l - 1, v));
tree.put(l, new Node(l, r, v));
}
public void merge(int l, int r, int v) {
this.split(l);
this.split(r + 1);
// l闭区间, r+1开区间
tree.subMap(l, r + 1).clear();
// 再做一个合并
// 和前一个元素进行合并
Map.Entry<Integer, Node> prev = tree.floorEntry(l - 1);
if (prev != null && prev.getValue().v == v && prev.getValue().r == l - 1) {
tree.remove(prev.getKey());
l = prev.getKey();
}
// 和后一个区间进行合并
Map.Entry<Integer, Node> next = tree.ceilingEntry(r + 1);
if (next != null && next.getValue().v == v && next.getKey() == r + 1) {
tree.remove(next.getKey());
r = next.getValue().r;
}
tree.put(l, new Node(l, r, v));
}
// 这边属于扩展
int query(int p) {
Map.Entry<Integer, Node> e = tree.floorEntry(p);
return e.getValue().v;
}
}
public int getNumber(TreeNode root, int[][] ops) {
final int BLUE = 0, RED = 1;
ODTTree odt = new ODTTree(0, 10_0000_0000, BLUE);
for (int[] op: ops) {
if (op[0] == BLUE) {
odt.merge(op[1], op[2], BLUE);
} else {
odt.merge(op[1], op[2], RED);
}
}
Deque<TreeNode> deq = new LinkedList<>();
deq.offer(root);
int ans = 0;
while (!deq.isEmpty()) {
TreeNode cur = deq.poll();
if (odt.query(cur.val) == RED) {
ans++;
}
if (cur.left != null) deq.offer(cur.left);
if (cur.right != null) deq.offer(cur.right);
}
return ans;
}
}最终的执行效率，好像比线段树要好一丢丢。
2276. 统计区间中的整数数目
Java
class CountIntervals {
static
class ODTTree {
static class Node {
int l, r, v;
public Node(int l, int r, int v) {
this.l = l;
this.r = r;
this.v = v;
}
}
TreeMap<Integer, Node> tree = new TreeMap<>();
Map<Integer, Integer> cnt = new HashMap<>();
public ODTTree() {
}
public ODTTree(int l, int r, int v) {
tree.put(l, new Node(l, r, v));
cnt.put(v, r - l + 1);
}
public void split(int l) {
Map.Entry<Integer, Node> prev = tree.floorEntry(l);
if (prev == null || prev.getKey() == l || prev.getValue().r < l) return;
Node cur = prev.getValue();
int r = cur.r, v = cur.v;
tree.remove(prev.getKey());
tree.put(prev.getKey(), new Node(cur.l, l - 1, v));
tree.put(l, new Node( l, r, v));
}
public void merge(int l, int r, int v) {
this.split(l);
this.split(r + 1);
// l闭区间, r+1开区间
// java的TreeMap，这边需要扩展开，方便统计
Integer k = l;
Map.Entry<Integer, Node> e = null;
while ((e = tree.ceilingEntry(k)) != null && e.getKey() <= r) {
Node cur = e.getValue();
cnt.put(cur.v, cnt.getOrDefault(cur.v, 0) - (cur.r - cur.l + 1));
tree.remove(e.getKey());
k = e.getValue().r + 1;
}
// 再做一个合并
// 和前一个元素进行合并
Map.Entry<Integer, Node> prev = tree.floorEntry(l - 1);
if (prev != null && prev.getValue().v == v && prev.getValue().r == l - 1) {
Node cur = prev.getValue();
cnt.put(cur.v, cnt.getOrDefault(cur.v, 0) - (cur.r - cur.l + 1));
tree.remove(prev.getKey());
l = prev.getKey();
}
// 和后一个区间进行合并
Map.Entry<Integer, Node> next = tree.ceilingEntry(r + 1);
if (next != null && next.getValue().v == v && next.getKey() == r + 1) {
Node cur = next.getValue();
cnt.put(cur.v, cnt.getOrDefault(cur.v, 0) - (cur.r - cur.l + 1));
tree.remove(next.getKey());
r = next.getValue().r;
}
tree.put(l, new Node(l, r, v));
cnt.put(v, cnt.getOrDefault(v, 0) + (r - l + 1));
}
// 这边属于扩展
public int count(int v) {
return cnt.getOrDefault(v, 0);
}
}
private ODTTree odt = new ODTTree();
public CountIntervals() {
}
public void add(int left, int right) {
odt.merge(left, right, 1);
}
public int count() {
return odt.count(1);
}
}
这边需要注意，额外扩展了对v值数量统计.
715. Range 模块
Java
class RangeModule {
static
class ODTTree {
static class Node {
int l, r, v;
public Node(int l, int r, int v) {
this.l = l;
this.r = r;
this.v = v;
}
}
TreeMap<Integer, Node> tree = new TreeMap<>();
public ODTTree() {
}
public ODTTree(int l, int r, int v) {
tree.put(l, new Node(l, r, v));
}
public void split(int l) {
Map.Entry<Integer, Node> prev = tree.floorEntry(l);
if (prev == null || prev.getKey() == l || prev.getValue().r < l) return;
Node cur = prev.getValue();
int r = cur.r, v = cur.v;
tree.remove(prev.getKey());
tree.put(prev.getKey(), new Node(cur.l, l - 1, v));
tree.put(l, new Node(l, r, v));
}
public void merge(int l, int r, int v) {
this.split(l);
this.split(r + 1);
// l闭区间, r+1开区间
tree.subMap(l, r + 1).clear();
// 再做一个合并
// 和前一个元素进行合并
Map.Entry<Integer, Node> prev = tree.floorEntry(l - 1);
if (prev != null && prev.getValue().v == v && prev.getValue().r == l - 1) {
tree.remove(prev.getKey());
l = prev.getKey();
}
// 和后一个区间进行合并
Map.Entry<Integer, Node> next = tree.ceilingEntry(r + 1);
if (next != null && next.getValue().v == v && next.getKey() == r + 1) {
tree.remove(next.getKey());
r = next.getValue().r;
}
tree.put(l, new Node(l, r, v));
}
// 扩展的接口
boolean queryRange(int l, int r, int v) {
Map.Entry<Integer, Node> e = tree.floorEntry(l);
if (e == null) return false;
Node cur = e.getValue();
return cur.r >= r && cur.v == v;
}
}
private ODTTree odt = new ODTTree();
public RangeModule() {
}
public void addRange(int left, int right) {
// 赋值为1
odt.merge(left, right - 1, 1);
}
public boolean queryRange(int left, int right) {
return odt.queryRange(left, right - 1, 1);
}
public void removeRange(int left, int right) {
// 赋值为0, 等价于删除
odt.merge(left, right - 1, 0);
}
}
2213. 由单个字符重复的最长子字符串
Java
class Solution {
// 在珂朵莉树的基础上，添加查询最长子串操作, 使用 优先队列+懒惰删除策略
static
class ODTTree {
static class Node {
int l, r, v;
public Node(int l, int r, int v) {
this.l = l;
this.r = r;
this.v = v;
}
}
TreeMap<Integer, Node> tree = new TreeMap<>();
// 大顶堆 三元组(l, r, v)
PriorityQueue<Node> pp = new PriorityQueue<>((a, b) -> -Integer.compare(a.r - a.l, b.r - b.l));
public ODTTree() {
}
public ODTTree(int l, int r, int v) {
tree.put(l, new Node(l, r, v));
pp.offer(new Node(l, r, v));
}
public void split(int l) {
Map.Entry<Integer, Node> prev = tree.floorEntry(l);
if (prev == null || prev.getKey() == l || prev.getValue().r < l) return;
Node cur = prev.getValue();
int r = cur.r, v = cur.v;
tree.remove(prev.getKey());
tree.put(prev.getKey(), new Node(cur.l, l - 1, v));
tree.put(l, new Node(l, r, v));
pp.offer(new Node(cur.l, l - 1, v));
pp.offer(new Node(l, r, v));
}
public void merge(int l, int r, int v) {
this.split(l);
this.split(r + 1);
// l闭区间, r+1开区间
tree.subMap(l, r + 1).clear();
// 再做一个合并
// 和前一个元素进行合并
Map.Entry<Integer, Node> prev = tree.floorEntry(l - 1);
if (prev != null && prev.getValue().v == v && prev.getValue().r == l - 1) {
tree.remove(prev.getKey());
l = prev.getKey();
}
// 和后一个区间进行合并
Map.Entry<Integer, Node> next = tree.ceilingEntry(r + 1);
if (next != null && next.getValue().v == v && next.getKey() == r + 1) {
tree.remove(next.getKey());
r = next.getValue().r;
}
tree.put(l, new Node(l, r, v));
pp.offer(new Node(l, r, v));
}
public int queryMax() {
while (!pp.isEmpty()) {
Node cur = pp.peek();
// 如果能查询到并匹配，则就是非过期的
Node q = tree.get(cur.l);
if (q != null && q.l == cur.l && q.r == cur.r && q.v == cur.v) {
return q.r - q.l + 1;
}
pp.poll();
}
// unreachable
return 0;
}
}
public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
ODTTree odt = new ODTTree();
char[] buf = s.toCharArray();
int i = 0;
while (i < buf.length) {
char c = buf[i];
int j = i + 1;
while (j < buf.length && buf[j] == c) {
j++;
}
odt.merge(i, j - 1, (int)(c - 'a'));
i = j;
}
int m = queryIndices.length;
int[] res = new int[m];
for (int k = 0; k < m; k++) {
int idx = queryIndices[k];
int v = (int)(queryCharacters.charAt(k) - 'a');
odt.merge(idx, idx, v);
res[k] = odt.queryMax();
}
return res;
}
}
评论 (20)
