competitive::data_structure::partially_retroactive_priority_queue

Struct PartiallyRetroactivePriorityQueue

pub struct PartiallyRetroactivePriorityQueue<T>where
    T: Clone + Ord + Bounded,{
    n: usize,
    in_edges: SegmentTree<MaxOperation<(T, Reverse<usize>)>>,
    out_edges: SegmentTree<MinOperation<(T, usize)>>,
    flow: SegmentTree<SumMinimum>,
}

Expand description

max-heap

Fields§

§n: usize§in_edges: SegmentTree<MaxOperation<(T, Reverse<usize>)>>§out_edges: SegmentTree<MinOperation<(T, usize)>>§flow: SegmentTree<SumMinimum>

Implementations§

Source §

impl<T> PartiallyRetroactivePriorityQueue<T>
where T: Clone + Ord + Bounded,

Source

pub fn new(n: usize) -> Self

Source

fn update_flow(&mut self, l: usize, r: usize, x: i32)

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 113)

97    pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T> {
98        assert!(i < self.n);
99        let p = self.flow.fold(i..self.n).sum;
100        let j = if p < 0 {
101            self.flow
102                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
103                .unwrap_or(0)
104        } else {
105            i
106        };
107        let (min, k) = self.out_edges.fold(j..self.n);
108        if x <= min {
109            self.in_edges.set(i, (x.clone(), Reverse(i)));
110            return Some(x);
111        }
112        if i <= k {
113            self.update_flow(i, k, 1);
114        } else {
115            self.update_flow(k, i, -1);
116        }
117        self.out_edges.set(i, (x.clone(), i));
118        self.out_edges.clear(k);
119        self.in_edges.set(k, (min.clone(), Reverse(k)));
120        if min == T::minimum() { None } else { Some(min) }
121    }
122    pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T> {
123        assert!(i < self.n);
124        if self.out_edges.get(i) == (T::minimum(), i) {
125            self.out_edges.clear(i);
126            return None;
127        }
128        let p = self.flow.fold(i..self.n).sum;
129        let j = if p < 0 {
130            self.flow
131                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
132                .unwrap_or(0)
133        } else {
134            i
135        };
136        let (min, k) = self.out_edges.fold(j..self.n);
137        assert_ne!(k, !0);
138        if i <= k {
139            self.update_flow(i, k, 1);
140        } else {
141            self.update_flow(k, i, -1);
142        }
143        self.in_edges.clear(i);
144        self.out_edges.clear(k);
145        self.in_edges.set(k, (min.clone(), Reverse(k)));
146        if min == T::minimum() { None } else { Some(min) }
147    }
148    pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T> {
149        assert!(i < self.n);
150        let p = self.flow.fold(0..=i).sum;
151        let j = if p > 0 {
152            self.flow
153                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
154                .unwrap_or(self.n - 1)
155        } else {
156            i
157        };
158        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
159        if max == T::minimum() {
160            self.out_edges.set(i, (T::minimum(), i));
161            return None;
162        }
163        if k <= i {
164            self.update_flow(k, i, 1);
165        } else {
166            self.update_flow(i, k, -1);
167        }
168        self.in_edges.set(i, (T::minimum(), Reverse(i)));
169        self.in_edges.clear(k);
170        self.out_edges.set(k, (max.clone(), k));
171        Some(max)
172    }
173    pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T> {
174        assert!(i < self.n);
175        let (max, Reverse(k)) = self.in_edges.get(i);
176        if k == i && max != T::minimum() {
177            self.in_edges.clear(i);
178            return Some(max);
179        }
180        let p = self.flow.fold(0..=i).sum;
181        let j = if p > 0 {
182            self.flow
183                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
184                .unwrap_or(self.n - 1)
185        } else {
186            i
187        };
188        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
189        if k <= i {
190            self.update_flow(k, i, 1);
191        } else {
192            self.update_flow(i, k, -1);
193        }
194        self.out_edges.clear(i);
195        self.in_edges.clear(k);
196        self.out_edges.set(k, (max.clone(), k));
197        if max == T::minimum() { None } else { Some(max) }
198    }

Source

pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T>

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 217)

214    pub fn set_push(&mut self, i: usize, x: T) -> Changed<T> {
215        assert!(i < self.n);
216        let mut changed = self.set_no_op(i);
217        changed.inserted[1] = unsafe { self.set_push_unchecked(i, x) };
218        changed
219    }

Source

pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T>

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 208)

199    pub fn set_no_op(&mut self, i: usize) -> Changed<T> {
200        assert!(i < self.n);
201        let mut changed = Changed::default();
202        let (max, Reverse(k)) = self.in_edges.get(i);
203        let (min, kk) = self.out_edges.get(i);
204        if k != i && kk != i {
205            return changed;
206        }
207        if i == k && max == T::minimum() || i == kk && min == T::minimum() {
208            changed.inserted[0] = unsafe { self.unset_pop_unchecked(i) };
209        } else {
210            changed.removed[0] = unsafe { self.unset_push_unchecked(i) };
211        }
212        changed
213    }

Source

pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T>

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 223)

220    pub fn set_pop(&mut self, i: usize) -> Changed<T> {
221        assert!(i < self.n);
222        let mut changed = self.set_no_op(i);
223        changed.removed[1] = unsafe { self.set_pop_unchecked(i) };
224        changed
225    }

Source

pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T>

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 210)

199    pub fn set_no_op(&mut self, i: usize) -> Changed<T> {
200        assert!(i < self.n);
201        let mut changed = Changed::default();
202        let (max, Reverse(k)) = self.in_edges.get(i);
203        let (min, kk) = self.out_edges.get(i);
204        if k != i && kk != i {
205            return changed;
206        }
207        if i == k && max == T::minimum() || i == kk && min == T::minimum() {
208            changed.inserted[0] = unsafe { self.unset_pop_unchecked(i) };
209        } else {
210            changed.removed[0] = unsafe { self.unset_push_unchecked(i) };
211        }
212        changed
213    }

Source

pub fn set_no_op(&mut self, i: usize) -> Changed<T>

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 216)

214    pub fn set_push(&mut self, i: usize, x: T) -> Changed<T> {
215        assert!(i < self.n);
216        let mut changed = self.set_no_op(i);
217        changed.inserted[1] = unsafe { self.set_push_unchecked(i, x) };
218        changed
219    }
220    pub fn set_pop(&mut self, i: usize) -> Changed<T> {
221        assert!(i < self.n);
222        let mut changed = self.set_no_op(i);
223        changed.removed[1] = unsafe { self.set_pop_unchecked(i) };
224        changed
225    }