| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
Hard |
2824 |
Weekly Contest 339 Q4 |
|
You are given an integer n and an integer p representing an array arr of length n where all elements are set to 0's, except position p which is set to 1. You are also given an integer array banned containing restricted positions. Perform the following operation on arr:
- Reverse a subarray with size
kif the single 1 is not set to a position inbanned.
Return an integer array answer with n results where the ith result is the minimum number of operations needed to bring the single 1 to position i in arr, or -1 if it is impossible.
Example 1:
Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,-1,-1,1]
Explanation:
- Initially 1 is placed at position 0 so the number of operations we need for position 0 is 0.
- We can never place 1 on the banned positions, so the answer for positions 1 and 2 is -1.
- Perform the operation of size 4 to reverse the whole array.
- After a single operation 1 is at position 3 so the answer for position 3 is 1.
Example 2:
Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,-1,-1,-1,-1]
Explanation:
- Initially 1 is placed at position 0 so the number of operations we need for position 0 is 0.
- We cannot perform the operation on the subarray positions
[0, 2]because position 2 is in banned. - Because 1 cannot be set at position 2, it is impossible to set 1 at other positions in more operations.
Example 3:
Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [-1,-1,0,-1]
Explanation:
Perform operations of size 1 and 1 never changes its position.
Constraints:
1 <= n <= 1050 <= p <= n - 10 <= banned.length <= n - 10 <= banned[i] <= n - 11 <= k <= nbanned[i] != p- all values in
bannedare unique
We notice that for any index
If the subarray moves one position to the right, then
Similarly, if the subarray moves one position to the left, then
Therefore, for a specific index
Next, we consider the range of values of the index
- If the boundary is not considered, the range of values of
$j$ is$[i - k + 1, i + k - 1]$ . - If the subarray is on the left, then
$[l, r] = [0, k - 1]$ , so the flipped index$j$ of$i$ is$0 + k - 1 - i$ , that is,$j = k - i - 1$ , so the left boundary$mi = max(i - k + 1, k - i - 1)$ . - If the subarray is on the right, then
$[l, r] = [n - k, n - 1]$ , so the flipped index$j= n - k + n - 1 - i$ is$j = n \times 2 - k - i - 1$ , so the right boundary of$j$ is$mx = min(i + k - 1, n \times 2 - k - i - 1)$ .
We use two ordered sets to store all the odd indices and even indices to be searched, here we need to exclude the indices in the array
Then we use BFS to search, each time searching all the flipped indices
When the search is over, the answer to all indices can be obtained.
The time complexity is
from sortedcontainers import SortedSet
class Solution:
def minReverseOperations(
self, n: int, p: int, banned: List[int], k: int
) -> List[int]:
ans = [-1] * n
ans[p] = 0
ts = [SortedSet() for _ in range(2)]
for i in range(n):
ts[i % 2].add(i)
ts[p % 2].remove(p)
for i in banned:
ts[i % 2].remove(i)
ts[0].add(n)
ts[1].add(n)
q = deque([p])
while q:
i = q.popleft()
mi = max(i - k + 1, k - i - 1)
mx = min(i + k - 1, n * 2 - k - i - 1)
s = ts[mi % 2]
j = s.bisect_left(mi)
while s[j] <= mx:
q.append(s[j])
ans[s[j]] = ans[i] + 1
s.remove(s[j])
j = s.bisect_left(mi)
return ansclass Solution {
public int[] minReverseOperations(int n, int p, int[] banned, int k) {
int[] ans = new int[n];
TreeSet<Integer>[] ts = new TreeSet[] {new TreeSet<>(), new TreeSet<>()};
for (int i = 0; i < n; ++i) {
ts[i % 2].add(i);
ans[i] = i == p ? 0 : -1;
}
ts[p % 2].remove(p);
for (int i : banned) {
ts[i % 2].remove(i);
}
ts[0].add(n);
ts[1].add(n);
Deque<Integer> q = new ArrayDeque<>();
q.offer(p);
while (!q.isEmpty()) {
int i = q.poll();
int mi = Math.max(i - k + 1, k - i - 1);
int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
var s = ts[mi % 2];
for (int j = s.ceiling(mi); j <= mx; j = s.ceiling(mi)) {
q.offer(j);
ans[j] = ans[i] + 1;
s.remove(j);
}
}
return ans;
}
}class Solution {
public:
vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
vector<int> ans(n, -1);
ans[p] = 0;
set<int> ts[2];
for (int i = 0; i < n; ++i) {
ts[i % 2].insert(i);
}
ts[p % 2].erase(p);
for (int i : banned) {
ts[i % 2].erase(i);
}
ts[0].insert(n);
ts[1].insert(n);
queue<int> q{{p}};
while (!q.empty()) {
int i = q.front();
q.pop();
int mi = max(i - k + 1, k - i - 1);
int mx = min(i + k - 1, n * 2 - k - i - 1);
auto& s = ts[mi % 2];
auto it = s.lower_bound(mi);
while (*it <= mx) {
int j = *it;
ans[j] = ans[i] + 1;
q.push(j);
it = s.erase(it);
}
}
return ans;
}
};func minReverseOperations(n int, p int, banned []int, k int) []int {
ans := make([]int, n)
ts := [2]*redblacktree.Tree{redblacktree.NewWithIntComparator(), redblacktree.NewWithIntComparator()}
for i := 0; i < n; i++ {
ts[i%2].Put(i, struct{}{})
ans[i] = -1
}
ans[p] = 0
ts[p%2].Remove(p)
for _, i := range banned {
ts[i%2].Remove(i)
}
ts[0].Put(n, struct{}{})
ts[1].Put(n, struct{}{})
q := []int{p}
for len(q) > 0 {
i := q[0]
q = q[1:]
mi := max(i-k+1, k-i-1)
mx := min(i+k-1, n*2-k-i-1)
s := ts[mi%2]
for x, _ := s.Ceiling(mi); x.Key.(int) <= mx; x, _ = s.Ceiling(mi) {
j := x.Key.(int)
s.Remove(j)
ans[j] = ans[i] + 1
q = append(q, j)
}
}
return ans
}function minReverseOperations(n: number, p: number, banned: number[], k: number): number[] {
const ans = new Array(n).fill(-1);
const ts = new Array(2).fill(0).map(() => new TreeSet<number>());
for (let i = 0; i < n; ++i) {
ts[i % 2].add(i);
}
ans[p] = 0;
ts[p % 2].delete(p);
for (const i of banned) {
ts[i % 2].delete(i);
}
ts[0].add(n);
ts[1].add(n);
let q = [p];
while (q.length) {
const t: number[] = [];
for (const i of q) {
const mi = Math.max(i - k + 1, k - i - 1);
const mx = Math.min(i + k - 1, n * 2 - k - i - 1);
const s = ts[mi % 2];
for (let j = s.ceil(mi)!; j <= mx; j = s.ceil(j)!) {
t.push(j);
ans[j] = ans[i] + 1;
s.delete(j);
}
}
q = t;
}
return ans;
}
type Compare<T> = (lhs: T, rhs: T) => number;
class RBTreeNode<T = number> {
data: T;
count: number;
left: RBTreeNode<T> | null;
right: RBTreeNode<T> | null;
parent: RBTreeNode<T> | null;
color: number;
constructor(data: T) {
this.data = data;
this.left = this.right = this.parent = null;
this.color = 0;
this.count = 1;
}
sibling(): RBTreeNode<T> | null {
if (!this.parent) return null; // sibling null if no parent
return this.isOnLeft() ? this.parent.right : this.parent.left;
}
isOnLeft(): boolean {
return this === this.parent!.left;
}
hasRedChild(): boolean {
return (
Boolean(this.left && this.left.color === 0) ||
Boolean(this.right && this.right.color === 0)
);
}
}
class RBTree<T> {
root: RBTreeNode<T> | null;
lt: (l: T, r: T) => boolean;
constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
this.root = null;
this.lt = (l: T, r: T) => compare(l, r) < 0;
}
rotateLeft(pt: RBTreeNode<T>): void {
const right = pt.right!;
pt.right = right.left;
if (pt.right) pt.right.parent = pt;
right.parent = pt.parent;
if (!pt.parent) this.root = right;
else if (pt === pt.parent.left) pt.parent.left = right;
else pt.parent.right = right;
right.left = pt;
pt.parent = right;
}
rotateRight(pt: RBTreeNode<T>): void {
const left = pt.left!;
pt.left = left.right;
if (pt.left) pt.left.parent = pt;
left.parent = pt.parent;
if (!pt.parent) this.root = left;
else if (pt === pt.parent.left) pt.parent.left = left;
else pt.parent.right = left;
left.right = pt;
pt.parent = left;
}
swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.color;
p1.color = p2.color;
p2.color = tmp;
}
swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.data;
p1.data = p2.data;
p2.data = tmp;
}
fixAfterInsert(pt: RBTreeNode<T>): void {
let parent = null;
let grandParent = null;
while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
parent = pt.parent;
grandParent = pt.parent.parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent === grandParent?.left) {
const uncle = grandParent.right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle && uncle.color === 0) {
grandParent.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent;
} else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt === parent.right) {
this.rotateLeft(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
this.rotateRight(grandParent);
this.swapColor(parent!, grandParent);
pt = parent!;
}
} else {
/* Case : B
Parent of pt is right child of Grand-parent of pt */
const uncle = grandParent!.left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle != null && uncle.color === 0) {
grandParent!.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent!;
} else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt === parent.left) {
this.rotateRight(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
this.rotateLeft(grandParent!);
this.swapColor(parent!, grandParent!);
pt = parent!;
}
}
}
this.root!.color = 1;
}
delete(val: T): boolean {
const node = this.find(val);
if (!node) return false;
node.count--;
if (!node.count) this.deleteNode(node);
return true;
}
deleteAll(val: T): boolean {
const node = this.find(val);
if (!node) return false;
this.deleteNode(node);
return true;
}
deleteNode(v: RBTreeNode<T>): void {
const u = BSTreplace(v);
// True when u and v are both black
const uvBlack = (u === null || u.color === 1) && v.color === 1;
const parent = v.parent!;
if (!u) {
// u is null therefore v is leaf
if (v === this.root) this.root = null;
// v is root, making root null
else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
this.fixDoubleBlack(v);
} else {
// u or v is red
if (v.sibling()) {
// sibling is not null, make it red"
v.sibling()!.color = 0;
}
}
// delete v from the tree
if (v.isOnLeft()) parent.left = null;
else parent.right = null;
}
return;
}
if (!v.left || !v.right) {
// v has 1 child
if (v === this.root) {
// v is root, assign the value of u to v, and delete u
v.data = u.data;
v.left = v.right = null;
} else {
// Detach v from tree and move u up
if (v.isOnLeft()) parent.left = u;
else parent.right = u;
u.parent = parent;
if (uvBlack) this.fixDoubleBlack(u);
// u and v both black, fix double black at u
else u.color = 1; // u or v red, color u black
}
return;
}
// v has 2 children, swap data with successor and recurse
this.swapData(u, v);
this.deleteNode(u);
// find node that replaces a deleted node in BST
function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
// when node have 2 children
if (x.left && x.right) return successor(x.right);
// when leaf
if (!x.left && !x.right) return null;
// when single child
return x.left ?? x.right;
}
// find node that do not have a left child
// in the subtree of the given node
function successor(x: RBTreeNode<T>): RBTreeNode<T> {
let temp = x;
while (temp.left) temp = temp.left;
return temp;
}
}
fixDoubleBlack(x: RBTreeNode<T>): void {
if (x === this.root) return; // Reached root
const sibling = x.sibling();
const parent = x.parent!;
if (!sibling) {
// No sibiling, double black pushed up
this.fixDoubleBlack(parent);
} else {
if (sibling.color === 0) {
// Sibling red
parent.color = 0;
sibling.color = 1;
if (sibling.isOnLeft()) this.rotateRight(parent);
// left case
else this.rotateLeft(parent); // right case
this.fixDoubleBlack(x);
} else {
// Sibling black
if (sibling.hasRedChild()) {
// at least 1 red children
if (sibling.left && sibling.left.color === 0) {
if (sibling.isOnLeft()) {
// left left
sibling.left.color = sibling.color;
sibling.color = parent.color;
this.rotateRight(parent);
} else {
// right left
sibling.left.color = parent.color;
this.rotateRight(sibling);
this.rotateLeft(parent);
}
} else {
if (sibling.isOnLeft()) {
// left right
sibling.right!.color = parent.color;
this.rotateLeft(sibling);
this.rotateRight(parent);
} else {
// right right
sibling.right!.color = sibling.color;
sibling.color = parent.color;
this.rotateLeft(parent);
}
}
parent.color = 1;
} else {
// 2 black children
sibling.color = 0;
if (parent.color === 1) this.fixDoubleBlack(parent);
else parent.color = 1;
}
}
}
}
insert(data: T): boolean {
// search for a position to insert
let parent = this.root;
while (parent) {
if (this.lt(data, parent.data)) {
if (!parent.left) break;
else parent = parent.left;
} else if (this.lt(parent.data, data)) {
if (!parent.right) break;
else parent = parent.right;
} else break;
}
// insert node into parent
const node = new RBTreeNode(data);
if (!parent) this.root = node;
else if (this.lt(node.data, parent.data)) parent.left = node;
else if (this.lt(parent.data, node.data)) parent.right = node;
else {
parent.count++;
return false;
}
node.parent = parent;
this.fixAfterInsert(node);
return true;
}
find(data: T): RBTreeNode<T> | null {
let p = this.root;
while (p) {
if (this.lt(data, p.data)) {
p = p.left;
} else if (this.lt(p.data, data)) {
p = p.right;
} else break;
}
return p ?? null;
}
*inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.inOrder(root.left!)) yield v;
yield root.data;
for (const v of this.inOrder(root.right!)) yield v;
}
*reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.reverseInOrder(root.right!)) yield v;
yield root.data;
for (const v of this.reverseInOrder(root.left!)) yield v;
}
}
class TreeSet<T = number> {
_size: number;
tree: RBTree<T>;
compare: Compare<T>;
constructor(
collection: T[] | Compare<T> = [],
compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const val of collection) this.add(val);
}
size(): number {
return this._size;
}
has(val: T): boolean {
return !!this.tree.find(val);
}
add(val: T): boolean {
const successful = this.tree.insert(val);
this._size += successful ? 1 : 0;
return successful;
}
delete(val: T): boolean {
const deleted = this.tree.deleteAll(val);
this._size -= deleted ? 1 : 0;
return deleted;
}
ceil(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(p.data, val) >= 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
floor(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(val, p.data) >= 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
higher(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(val, p.data) < 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
lower(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(p.data, val) < 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
first(): T | undefined {
return this.tree.inOrder().next().value;
}
last(): T | undefined {
return this.tree.reverseInOrder().next().value;
}
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
pop(): T | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
*[Symbol.iterator](): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*keys(): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*values(): Generator<T, undefined, void> {
for (const val of this.tree.inOrder()) yield val;
return undefined;
}
/**
* Return a generator for reverse order traversing the set
*/
*rvalues(): Generator<T, undefined, void> {
for (const val of this.tree.reverseInOrder()) yield val;
return undefined;
}
}
class TreeMultiSet<T = number> {
_size: number;
tree: RBTree<T>;
compare: Compare<T>;
constructor(
collection: T[] | Compare<T> = [],
compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const val of collection) this.add(val);
}
size(): number {
return this._size;
}
has(val: T): boolean {
return !!this.tree.find(val);
}
add(val: T): boolean {
const successful = this.tree.insert(val);
this._size++;
return successful;
}
delete(val: T): boolean {
const successful = this.tree.delete(val);
if (!successful) return false;
this._size--;
return true;
}
count(val: T): number {
const node = this.tree.find(val);
return node ? node.count : 0;
}
ceil(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(p.data, val) >= 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
floor(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(val, p.data) >= 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
higher(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(val, p.data) < 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
lower(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(p.data, val) < 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
first(): T | undefined {
return this.tree.inOrder().next().value;
}
last(): T | undefined {
return this.tree.reverseInOrder().next().value;
}
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
pop(): T | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
*[Symbol.iterator](): Generator<T, void, void> {
yield* this.values();
}
*keys(): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*values(): Generator<T, undefined, void> {
for (const val of this.tree.inOrder()) {
let count = this.count(val);
while (count--) yield val;
}
return undefined;
}
/**
* Return a generator for reverse order traversing the multi-set
*/
*rvalues(): Generator<T, undefined, void> {
for (const val of this.tree.reverseInOrder()) {
let count = this.count(val);
while (count--) yield val;
}
return undefined;
}
}function minReverseOperations(n: number, p: number, banned: number[], k: number): number[] {
const ans = new Array(n).fill(-1);
const ts = new Array(2).fill(0).map(() => new TreapMultiSet<number>());
for (let i = 0; i < n; ++i) {
ts[i % 2].add(i);
}
ans[p] = 0;
ts[p % 2].delete(p);
for (const i of banned) {
ts[i % 2].delete(i);
}
ts[0].add(n);
ts[1].add(n);
let q = [p];
while (q.length) {
const t: number[] = [];
for (const i of q) {
const mi = Math.max(i - k + 1, k - i - 1);
const mx = Math.min(i + k - 1, n * 2 - k - i - 1);
const s = ts[mi % 2];
for (let j = s.ceil(mi)!; j <= mx; j = s.ceil(j)!) {
t.push(j);
ans[j] = ans[i] + 1;
s.delete(j);
}
}
q = t;
}
return ans;
}
type CompareFunction<T, R extends 'number' | 'boolean'> = (
a: T,
b: T,
) => R extends 'number' ? number : boolean;
interface ITreapMultiSet<T> extends Iterable<T> {
add: (...value: T[]) => this;
has: (value: T) => boolean;
delete: (value: T) => void;
bisectLeft: (value: T) => number;
bisectRight: (value: T) => number;
indexOf: (value: T) => number;
lastIndexOf: (value: T) => number;
at: (index: number) => T | undefined;
first: () => T | undefined;
last: () => T | undefined;
lower: (value: T) => T | undefined;
higher: (value: T) => T | undefined;
floor: (value: T) => T | undefined;
ceil: (value: T) => T | undefined;
shift: () => T | undefined;
pop: (index?: number) => T | undefined;
count: (value: T) => number;
keys: () => IterableIterator<T>;
values: () => IterableIterator<T>;
rvalues: () => IterableIterator<T>;
entries: () => IterableIterator<[number, T]>;
readonly size: number;
}
class TreapNode<T = number> {
value: T;
count: number;
size: number;
priority: number;
left: TreapNode<T> | null;
right: TreapNode<T> | null;
constructor(value: T) {
this.value = value;
this.count = 1;
this.size = 1;
this.priority = Math.random();
this.left = null;
this.right = null;
}
static getSize(node: TreapNode<any> | null): number {
return node?.size ?? 0;
}
static getFac(node: TreapNode<any> | null): number {
return node?.priority ?? 0;
}
pushUp(): void {
let tmp = this.count;
tmp += TreapNode.getSize(this.left);
tmp += TreapNode.getSize(this.right);
this.size = tmp;
}
rotateRight(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const left = node.left;
node.left = left?.right ?? null;
left && (left.right = node);
left && (node = left);
node.right?.pushUp();
node.pushUp();
return node;
}
rotateLeft(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const right = node.right;
node.right = right?.left ?? null;
right && (right.left = node);
right && (node = right);
node.left?.pushUp();
node.pushUp();
return node;
}
}
class TreapMultiSet<T = number> implements ITreapMultiSet<T> {
private readonly root: TreapNode<T>;
private readonly compareFn: CompareFunction<T, 'number'>;
private readonly leftBound: T;
private readonly rightBound: T;
constructor(compareFn?: CompareFunction<T, 'number'>);
constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T);
constructor(
compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b,
leftBound: any = -Infinity,
rightBound: any = Infinity,
) {
this.root = new TreapNode<T>(rightBound);
this.root.priority = Infinity;
this.root.left = new TreapNode<T>(leftBound);
this.root.left.priority = -Infinity;
this.root.pushUp();
this.leftBound = leftBound;
this.rightBound = rightBound;
this.compareFn = compareFn;
}
get size(): number {
return this.root.size - 2;
}
get height(): number {
const getHeight = (node: TreapNode<T> | null): number => {
if (node == null) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
};
return getHeight(this.root);
}
/**
*
* @complexity `O(logn)`
* @description Returns true if value is a member.
*/
has(value: T): boolean {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): boolean => {
if (node == null) return false;
if (compare(node.value, value) === 0) return true;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
/**
*
* @complexity `O(logn)`
* @description Add value to sorted set.
*/
add(...values: T[]): this {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
node.count++;
node.pushUp();
} else if (compare(node.value, value) > 0) {
if (node.left) {
dfs(node.left, value, node, 'left');
} else {
node.left = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.left) > node.priority) {
parent[direction] = node.rotateRight();
}
} else if (compare(node.value, value) < 0) {
if (node.right) {
dfs(node.right, value, node, 'right');
} else {
node.right = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.right) > node.priority) {
parent[direction] = node.rotateLeft();
}
}
parent.pushUp();
};
values.forEach(value => dfs(this.root.left, value, this.root, 'left'));
return this;
}
/**
*
* @complexity `O(logn)`
* @description Remove value from sorted set if it is a member.
* If value is not a member, do nothing.
*/
delete(value: T): void {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
if (node.count > 1) {
node.count--;
node?.pushUp();
} else if (node.left == null && node.right == null) {
parent[direction] = null;
} else {
// 旋到根节点
if (
node.right == null ||
TreapNode.getFac(node.left) > TreapNode.getFac(node.right)
) {
parent[direction] = node.rotateRight();
dfs(parent[direction]?.right ?? null, value, parent[direction]!, 'right');
} else {
parent[direction] = node.rotateLeft();
dfs(parent[direction]?.left ?? null, value, parent[direction]!, 'left');
}
}
} else if (compare(node.value, value) > 0) {
dfs(node.left, value, node, 'left');
} else if (compare(node.value, value) < 0) {
dfs(node.right, value, node, 'right');
}
parent?.pushUp();
};
dfs(this.root.left, value, this.root, 'left');
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the left of) any existing values.
*/
bisectLeft(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the right of) any existing values.
*/
bisectRight(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left) + node.count;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the first occurrence of a value in the set, or -1 if it is not present.
*/
indexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the last occurrence of a value in the set, or -1 if it is not present.
*/
lastIndexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left) + node.count - 1;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the item located at the specified index.
* @param index The zero-based index of the desired code unit. A negative index will count back from the last item.
*/
at(index: number): T | undefined {
if (index < 0) index += this.size;
if (index < 0 || index >= this.size) return undefined;
const dfs = (node: TreapNode<T> | null, rank: number): T | undefined => {
if (node == null) return undefined;
if (TreapNode.getSize(node.left) >= rank) {
return dfs(node.left, rank);
} else if (TreapNode.getSize(node.left) + node.count >= rank) {
return node.value;
} else {
return dfs(node.right, rank - TreapNode.getSize(node.left) - node.count);
}
};
const res = dfs(this.root, index + 2);
return ([this.leftBound, this.rightBound] as any[]).includes(res) ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than `val`, return `undefined` if no such element found.
*/
lower(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than `val`, return `undefined` if no such element found.
*/
higher(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than or equal to `val`, return `undefined` if no such element found.
*/
floor(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than or equal to `val`, return `undefined` if no such element found.
*/
ceil(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned.
*/
first(): T | undefined {
const iter = this.inOrder();
iter.next();
const res = iter.next().value;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned .
*/
last(): T | undefined {
const iter = this.reverseInOrder();
iter.next();
const res = iter.next().value;
return res === this.leftBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Removes the first element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
/**
* @complexity `O(logn)`
* @description
* Removes the last element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
pop(index?: number): T | undefined {
if (index == null) {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
const toDelete = this.at(index);
if (toDelete == null) return;
this.delete(toDelete);
return toDelete;
}
/**
*
* @complexity `O(logn)`
* @description
* Returns number of occurrences of value in the sorted set.
*/
count(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) return node.count;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
*[Symbol.iterator](): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of keys in the set.
*/
*keys(): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of values in the set.
*/
*values(): Generator<T, any, any> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns a generator for reversed order traversing the set.
*/
*rvalues(): Generator<T, any, any> {
const iter = this.reverseInOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns an iterable of key, value pairs for every entry in the set.
*/
*entries(): IterableIterator<[number, T]> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let i = 0; i < steps; i++) {
yield [i, iter.next().value];
}
}
private *inOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.inOrder(root.left);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.inOrder(root.right);
}
private *reverseInOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.reverseInOrder(root.right);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.reverseInOrder(root.left);
}
}