锈化工具（rust实现的算法竞赛模板）
rust safe fast 动态长度 arraylist 实现
mod arraylist {
use std::collections::{HashSet, LinkedList};
use std::ops::{Index, IndexMut};
const NULL: usize = usize::MAX;
type Link = usize;
#[derive(Clone)]
pub struct Node<T> {
pub data: T,
next: Link,
prev: Link,
}
impl<T> Node<T> {
pub fn new(data: T) -> Self {
Self {
data,
next: NULL,
prev: NULL,
}
}
}
pub struct ArrayList<T> {
len: usize,
list: Vec<Node<T>>,
space: LinkedList<Link>,
space_set: HashSet<Link>,
head: Link,
tail: Link,
}
impl<T> ArrayList<T>
where
T: Clone + Default,
{
pub fn new() -> Self {
Self {
len: 0,
list: vec![],
space: LinkedList::new(),
space_set: HashSet::new(),
head: NULL,
tail: NULL,
}
}
pub fn with_capacity(capacity: usize) -> Self {
Self {
len: 0,
list: vec![Node::new(T::default()); capacity],
space: (0..capacity).collect(),
space_set: (0..capacity).collect(),
head: NULL,
tail: NULL,
}
}
fn new_node(&mut self, data: T) -> Link {
let node = Node::new(data);
if let Some(space) = self.space.pop_front() {
self.space_set.remove(&space);
self.list[space] = node;
space
} else {
self.list.push(node);
self.list.len() - 1
}
}
pub fn prev_link(&self, current: Link) -> Option<Link> {
let result = self.list[current].prev;
if result == NULL {
None
} else {
Some(result)
}
}
pub fn next_link(&self, current: Link) -> Option<Link> {
let result = self.list[current].next;
if result == NULL {
None
} else {
Some(result)
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn begin(&self) -> Link {
self.head
}
pub fn end(&self) -> Link {
self.tail
}
pub fn front(&self) -> Option<&T> {
if self.head == NULL {
None
} else {
Some(&self.list[self.head].data)
}
}
pub fn back(&self) -> Option<&T> {
if self.tail == NULL {
None
} else {
Some(&self.list[self.tail].data)
}
}
pub fn pop_front(&mut self) -> Option<T> {
if self.head == NULL {
return None;
}
let old_head = self.head;
self.head = self.list[self.head].next;
if self.head == NULL {
self.tail = NULL
} else {
self.list[self.head].prev = NULL
}
self.len -= 1;
self.space.push_back(old_head);
self.space_set.insert(old_head);
Some(self.list[old_head].data.clone())
}
pub fn pop_back(&mut self) -> Option<T> {
if self.tail == NULL {
return None;
}
let old_tail = self.tail;
self.tail = self.list[self.tail].prev;
if self.tail == NULL {
self.head = NULL
} else {
self.list[self.tail].next = NULL
}
self.len -= 1;
self.space.push_back(old_tail);
self.space_set.insert(old_tail);
Some(self.list[old_tail].data.clone())
}
pub fn push_front(&mut self, data: T) {
let node = self.new_node(data);
if self.head == NULL {
self.tail = node;
} else {
self.list[node].next = self.head;
self.list[self.head].prev = node;
}
self.len += 1;
self.head = node;
}
pub fn push_back(&mut self, data: T) {
let node = self.new_node(data);
if self.tail == NULL {
self.head = node;
} else {
self.list[node].prev = self.tail;
self.list[self.tail].next = node;
}
self.len += 1;
self.tail = node;
}
pub fn insert_before(&mut self, index: Link, data: T) -> Option<Link> {
if self.space.contains(&index) {
return None;
}
let node = self.new_node(data);
let prev = self.list[index].prev;
if prev != NULL {
self.list[prev].next = node;
self.list[node].prev = prev;
} else {
self.head = node;
}
self.list[node].next = index;
self.list[index].prev = node;
Some(node)
}
pub fn insert_after(&mut self, index: Link, data: T) -> Option<Link> {
if self.space.contains(&index) {
return None;
}
let node = self.new_node(data);
let next = self.list[index].next;
if next != NULL {
self.list[next].prev = node;
self.list[node].next = next;
} else {
self.tail = node;
}
self.list[node].prev = index;
self.list[index].next = node;
Some(node)
}
pub fn erase(&mut self, index: Link) -> bool {
if self.space_set.contains(&index) || index > self.list.len() {
return false;
}
let prev = self.list[index].prev;
let next = self.list[index].next;
if prev != NULL {
self.list[prev].next = next;
} else {
self.head = next
}
if next != NULL {
self.list[next].prev = prev;
} else {
self.tail = prev
}
self.space.push_back(index);
self.space_set.insert(index);
self.len -= 1;
true
}
}
impl<T> Index<Link> for ArrayList<T> {
type Output = T;
fn index(&self, index: Link) -> &Self::Output {
if self.space_set.contains(&index) || index > self.list.len() {
panic!("Index out of bounds");
} else {
&self.list.get(index).unwrap().data
}
}
}
impl<T> IndexMut<Link> for ArrayList<T> {
fn index_mut(&mut self, index: Link) -> &mut T {
if self.space_set.contains(&index) || index > self.list.len() {
panic!("Index out of bounds");
} else {
&mut self.list.get_mut(index).unwrap().data
}
}
}
}rust宏编程实现，pythonic风格用法io
mod fast_io {
pub use std::io::{BufRead, Write, BufReader, BufWriter};
use std::io::{StdinLock, StdoutLock};
pub static mut STDIN: Option<BufReader<StdinLock<'static>>> = None;
pub static mut STDOUT: Option<BufWriter<StdoutLock<'static>>> = None;
#[macro_export]
macro_rules! init_io {
() => {
unsafe {
STDIN.get_or_insert(BufReader::new(std::io::stdin().lock()));
STDOUT.get_or_insert(BufWriter::new(std::io::stdout().lock()));
}
};
}
#[macro_export]
macro_rules! readln {
() => {{
let mut line = String::new();
unsafe {
STDIN.as_mut().unwrap().read_line(&mut line).unwrap();
}
line
}};
}
#[macro_export]
macro_rules! parseln {
() => { readln!().trim().parse().unwrap() };
($t:ty) => { readln!().trim().parse::<$t>().unwrap() };
}
#[macro_export]
macro_rules! mapln {
($t:ty) => {
readln!()
.split_ascii_whitespace()
.flat_map(|s| s.parse::<$t>().ok())
.collect::<Vec<$t>>()
};
}
#[macro_export]
macro_rules! unpack {
($items:expr) => {
$items.try_into().unwrap()
};
}
#[macro_export]
macro_rules! has_next {
() => {
unsafe {
STDIN.as_mut().unwrap().fill_buf().unwrap().len() > 0
}
};
}
#[macro_export]
macro_rules! write {
($($arg:tt)*) => {
unsafe {
STDOUT.as_mut().unwrap().write(format!($($arg)*).as_bytes()).expect("Write failed")
}
};
}
#[macro_export]
macro_rules! writeln {
() => {
unsafe {
STDOUT.as_mut().unwrap().write(b"\n").expect("Writeln failed")
}
};
($($arg:tt)*) => {
unsafe {
STDOUT.as_mut().unwrap().write(format!($($arg)*).as_bytes()).expect("Writeln failed");
}
writeln!()
};
}
#[macro_export]
macro_rules! flush {
() => {
unsafe {
STDOUT.as_mut().unwrap().flush().expect("Writeln failed");
}
};
}
}纯rust实现，python风格快速io
mod fast_io { // 输出只要用BufWriter套一层就行，没必要设计了
use std::fmt::Debug;
pub use std::io::BufRead;
use std::io::BufReader;
use std::str::FromStr;
pub struct FastReader<R: BufRead> {
reader: BufReader<R>,
}
impl<R: BufRead> FastReader<R> {
pub fn new(stream: R) -> Self {
Self {
reader: BufReader::new(stream),
}
}
pub fn nextln(&mut self) -> String {
let mut line = String::new();
self.reader.read_line(&mut line).unwrap();
line.trim().to_string()
}
pub fn next<T: FromStr>(&mut self) -> T {
self.nextln().parse::<T>().ok().unwrap()
}
pub fn readln<T: FromStr>(&mut self) -> Vec<T> {
self.nextln()
.split_ascii_whitespace()
.flat_map(|s| s.parse::<T>().ok())
.collect()
}
pub fn has_next(&mut self) -> bool {
self.reader.fill_buf().unwrap().len() > 0
}
}
}利用 ffi 实现的，调用 C 语言 的 io 方法
mod ffi_c_io {
// region use ffi_c_io::*
pub use std::ffi::{c_char, c_int, CString};
pub enum FILE {}
#[link(name = "c")]
extern "C" {
pub static mut stdin: *mut FILE;
}
extern "C" {
pub fn scanf(format: *const c_char, ...) -> c_int;
pub fn getchar() -> c_int;
pub fn ungetc(c: c_int, stream: *mut FILE) -> c_int;
}
#[macro_export]
macro_rules! scan {
($format:expr, $($arg:expr),*) => {{
let format_cstr = CString::new($format).expect("CString::new failed");
unsafe {
let result = scanf(format_cstr.as_ptr(), $( &mut $arg as *mut _ as *mut _ ),*);
result as i32
}
}};
}
#[macro_export]
macro_rules! scanln {
() => {{
let mut result = Vec::new();
unsafe {
let mut c = getchar();
while (c != -1 && c != '\n' as c_int && c != '\r' as c_int) {
result.push(c as u8);
c = getchar();
}
}
if let Ok(str) = String::from_utf8(result) {
str
} else {
String::new()
}
}};
}
#[macro_export]
macro_rules! getc {
() => {{
unsafe {
let c = getchar();
char::from(c as u8)
}
}};
}
#[macro_export]
macro_rules! ignore {
() => {{
unsafe {
let mut c = getchar();
while c != -1
&& (c == ' ' as c_int
|| c == '\n' as c_int
|| c == '\t' as c_int
|| c == '\r' as c_int)
{
c = getchar();
}
ungetc(c, stdin);
}
}};
}
#[macro_export]
macro_rules! token {
() => {{
let mut result = Vec::new();
ignore!();
unsafe {
let mut c = getchar();
while c != -1
&& !(c == ' ' as c_int
|| c == '\n' as c_int
|| c == '\t' as c_int
|| c == '\r' as c_int)
{
result.push(c as u8);
c = getchar();
}
ungetc(c, stdin);
}
if let Ok(str) = String::from_utf8(result) {
str
} else {
String::new()
}
}};
}
// endregion
}仿照 java 设计，原生 scanner 设计
mod scanner {
use std::io::{Read};
// 输入用
pub struct Scanner {
stream: std::io::Stdin,
}
impl Scanner {
pub fn new(istream: std::io::Stdin) -> Self {
Self {
stream: istream,
}
}
pub fn skip_line(&mut self) {
let _ = self.stream.read_line(&mut String::new());
}
// bool => true, false
// enum Result { Ok(_), Err(_) }
// enum Option { Some(_), None }
pub fn read_char(&mut self) -> Option<char> {
let mut byte = [0; 1];
match self.stream.read(&mut byte) {
Ok(0) => None, // EOF
Ok(_) => Some(char::from(byte[0])),
Err(_) => None, // Error reading
}
}
pub fn next_char(&mut self) -> Option<char> {
let mut c = self.read_char()?;
while c.is_whitespace() {
c = self.read_char()?;
}
Some(c)
}
pub fn next(&mut self) -> Option<String> {
let mut c = self.read_char()?;
loop {
if !c.is_whitespace() {
break;
}
c = self.read_char()?;
}
let mut buffer = String::new();
loop {
buffer.push(c);
c = self.read_char()?;
if c.is_whitespace() {
break;
}
}
return if buffer.is_empty() { None } else { Some(buffer) };
}
pub fn next_line(&mut self) -> Option<String> {
let mut buffer = String::new();
match self.stream.read_line(&mut buffer) {
Ok(0) => None, // EOF
Ok(_) => Some(buffer.trim_end().to_string()),
Err(_) => None, // Error reading
}
}
pub fn read_line_i128(&mut self) -> Option<Vec<i128>> {
let line = self.next_line()?;
if line.is_empty() {
return None;
}
let inputs: Vec<i128> = line
.split_whitespace()
.map(|x| x.parse().ok())
.collect::<Option<Vec<i128>>>()?;
Some(inputs)
}
pub fn read_line_f64(&mut self) -> Option<Vec<f64>> {
let line = self.next_line()?;
if line.is_empty() {
return None;
}
let inputs: Vec<f64> = line
.split_whitespace()
.map(|x| x.parse().ok())
.collect::<Option<Vec<f64>>>()?;
Some(inputs)
}
pub fn next_i128(&mut self) -> Option<i128> {
let mut res = 0;
let mut is_negative = false;
let mut chr = self.read_char()?;
while !chr.is_ascii_digit() {
if chr == '-' {
is_negative = true;
}
chr = self.read_char()?;
}
while chr.is_ascii_digit() {
res = (res << 3) + (res << 1) + (chr as i128) - ('0' as i128);
let peek = self.read_char();
if peek == None {
break;
}
chr = peek.unwrap();
}
Some(if is_negative { -res } else { res })
}
pub fn next_f64(&mut self) -> Option<f64> {
let mut res = 0.0;
let mut i = 0.0;
let mut is_visited_dot = false;
let mut is_negative = false;
let mut chr = self.read_char()?;
while !chr.is_ascii_digit() {
if chr == '-' {
is_negative = true;
}
if chr == '.' {
is_visited_dot = true;
}
chr = self.read_char()?;
}
while chr.is_ascii_digit() && !is_visited_dot {
res = res * 10.0 + ((chr as i128) - ('0' as i128)) as f64;
let peek = self.read_char();
if peek == None {
return Some(if is_negative { -res - i } else { res + i });
}
chr = peek.unwrap();
}
if chr == '.' {
let peek = self.read_char();
if peek == None {
return Some(if is_negative { -res - i } else { res + i });
}
chr = peek.unwrap();
}
let mut power = 0.1;
while chr.is_ascii_digit() {
i += (((chr as i128) - ('0' as i128)) as f64) * power;
power *= 0.1;
let peek = self.read_char();
if peek == None {
return Some(if is_negative { -res - i } else { res + i });
}
chr = peek.unwrap();
}
return Some(if is_negative { -res - i } else { res + i });
}
pub fn next_f32(&mut self) -> Option<f32> {
self.next_f64().map(|v| v as f32)
}
pub fn next_usize(&mut self) -> Option<usize> {
self.next_i128().map(|v| v as usize)
}
pub fn next_i64(&mut self) -> Option<i64> {
self.next_i128().map(|v| v as i64)
}
pub fn next_i32(&mut self) -> Option<i32> {
self.next_i128().map(|v| v as i32)
}
pub fn next_i16(&mut self) -> Option<i16> {
self.next_i128().map(|v| v as i16)
}
}
}网络流，最大流和最小费用最大流
mod network_flow {
use std::collections::{BinaryHeap, HashMap, VecDeque};
use std::cmp::Reverse;
const INF: i32 = i32::MAX;
#[derive(Copy, Clone)]
struct Edge {
to: usize,
flow: i32,
}
pub struct NetworkFlow {
head: Vec<Vec<usize>>,
edges: Vec<Edge>,
depth: Vec<i32>,
current: Vec<usize>,
costs: Vec<i32>,
distance: Vec<i32>,
h: Vec<i32>,
visited: Vec<bool>,
gap: HashMap<i32, i32>,
}
impl NetworkFlow {
pub fn new(len: usize) -> Self {
Self {
head: vec![Vec::new(); len],
edges: vec![],
depth: vec![0; len],
current: vec![],
costs: vec![],
distance: vec![],
h: vec![],
visited: vec![],
gap: Default::default(),
}
}
pub fn with_capacity(len: usize, cnt: usize, use_cost: bool) -> Self {
Self {
head: vec![Vec::new(); len],
edges: Vec::with_capacity(cnt << 1),
depth: vec![0; len],
current: vec![],
costs: if use_cost {
Vec::with_capacity(len << 1)
} else {
vec![]
},
distance: vec![],
h: vec![],
visited: vec![],
gap: Default::default(),
}
}
pub fn connect(&mut self, from: usize, to: usize, flow: i32) {
self.head[from].push(self.edges.len());
self.edges.push(Edge { to, flow });
self.head[to].push(self.edges.len());
self.edges.push(Edge { to: from, flow: 0 });
}
pub fn connect_with_cost(&mut self, from: usize, to: usize, flow: i32, cost: i32) {
self.costs.push(cost);
self.costs.push(-cost);
self.connect(from, to, flow);
}
fn _isap_bfs(&mut self, end: usize) {
self.depth.fill(-1);
self.gap.clear();
self.depth[end] = 0;
self.gap.insert(end as i32, 1);
let mut queue = VecDeque::new();
queue.push_back(end);
while let Some(from) = queue.pop_front() {
for idx in self.head[from].iter() {
let edge = self.edges[*idx];
if self.depth[edge.to] != -1 {
continue;
}
self.depth[edge.to] = self.depth[from] + 1;
*self.gap.entry(self.depth[edge.to]).or_insert(0) += 1;
queue.push_back(edge.to);
}
}
}
fn _isap_dfs(&mut self, from: usize, flow: i32, start: &usize, end: &usize) -> i32 {
if from == *end {
return flow;
}
let mut used = 0;
let mut cur = self.current[from];
while cur < self.head[from].len() {
let idx = self.head[from][cur];
let edge = self.edges[idx];
if edge.flow < 1 || self.depth[from] != self.depth[edge.to] + 1 {
cur += 1;
self.current[from] = cur;
continue;
}
let spend = self._isap_dfs(edge.to, edge.flow.min(flow - used), start, end);
if spend == 0 {
cur += 1;
self.current[from] = cur;
continue;
}
self.edges[idx].flow -= spend;
self.edges[idx ^ 1].flow += spend;
used += spend;
if used == flow {
return used;
}
cur += 1;
self.current[from] = cur;
}
*self.gap.entry(self.depth[from]).or_insert(0) -= 1;
if self.gap[&self.depth[from]] == 0 {
self.depth[*start] = self.head.len() as i32 + 1;
}
self.depth[from] += 1;
*self.gap.entry(self.depth[from]).or_insert(0) += 1;
used
}
pub fn maximum_flow(&mut self, start: usize, end: usize) -> i64 {
let mut result = 0i64;
self._isap_bfs(end);
self.current.resize(self.head.len(), 0);
while self.depth[start] < self.head.len() as i32 {
self.current.fill(0);
result += self._isap_dfs(start, INF, &start, &end) as i64;
}
result
}
fn _dijkstra(&mut self, start: usize, end: usize) -> bool {
self.distance.fill(INF);
let mut heap = BinaryHeap::new();
self.distance[start] = 0;
heap.push(Reverse((self.distance[start], start)));
while let Some(Reverse((current_distance, from))) = heap.pop() {
if self.distance[from] < current_distance {
continue;
}
for idx in &self.head[from] {
let edge = &self.edges[*idx];
let cost = self.costs[*idx];
let new_distance = self.distance[from] + cost + self.h[from] - self.h[edge.to];
if edge.flow == 0 || self.distance[edge.to] <= new_distance {
continue;
}
self.distance[edge.to] = new_distance;
heap.push(Reverse((self.distance[edge.to], edge.to)));
}
}
return self.distance[end] != INF;
}
fn _dinic_dfs(&mut self, from: usize, flow: i32, start: &usize, end: &usize) -> i32 {
if from == *end {
return flow;
}
let mut used = 0;
self.visited[from] = true;
let mut cur = self.current[from];
while cur < self.head[from].len() {
let idx = self.head[from][cur];
let edge = self.edges[idx];
let cost = self.costs[idx];
let new_distance = self.distance[from] + cost + self.h[from] - self.h[edge.to];
if self.visited[edge.to] || edge.flow == 0 || self.distance[edge.to] != new_distance {
cur += 1;
self.current[from] = cur;
continue;
}
let spend = self._dinic_dfs(edge.to,
edge.flow.min(flow - used), start, end);
self.edges[idx].flow -= spend;
self.edges[idx ^ 1].flow += spend;
used += spend;
if flow == used {
break;
}
cur += 1;
self.current[from] = cur;
}
self.visited[from] = false;
return used;
}
pub fn minimum_cost_maximum_flow(&mut self, start: usize, end: usize) -> (i64, i64) {
let (mut cost, mut flow) = (0, 0);
self.h = vec![0; self.head.len()];
self.visited = vec![false; self.head.len()];
self.distance.resize(self.head.len(), INF);
self.current.resize(self.head.len(), 0);
while self._dijkstra(start, end) {
self.current.fill(0);
let result = self._dinic_dfs(start, INF, &start, &end);
for i in 0..self.head.len() {
self.h[i] += if self.distance[i] == INF { 0 } else { self.distance[i] };
}
flow += result as i64;
cost += result as i64 * self.h[end] as i64;
}
return (cost, flow);
}
pub fn clear_edges(&mut self) {
self.head.fill(Vec::new());
self.edges.clear();
self.costs.clear();
self.gap.clear();
}
pub fn head(&self) -> &Vec<Vec<usize>> {
&self.head
}
pub fn edges(&self) -> &Vec<Edge> {
&self.edges
}
pub fn costs(&self) -> &Vec<i32> {
&self.costs
}
}
}AVL树
SortedSet
mod avl_tree {
use std::cmp::{max, Ordering};
use std::iter::FromIterator;
use std::mem::swap;
use std::ops::Not;
pub type SortedSet<T> = AvlTree<T>;
pub struct AvlTree<T: Ord> {
root: Option<Box<AvlNode<T>>>,
length: usize,
}
impl<T: Ord> AvlTree<T> {
pub fn new() -> Self {
Self {
root: None,
length: 0,
}
}
pub fn contains(&self, value: &T) -> bool {
let mut curtrent = &self.root;
while let Some(node) = curtrent {
curtrent = match value.cmp(&node.value) {
Ordering::Less => &node.left,
Ordering::Equal => return true,
Ordering::Greater => &node.right,
}
}
false
}
pub fn insert(&mut self, value: T) -> bool {
let is_inserted = insert(&mut self.root, value);
if is_inserted {
self.length += 1;
}
is_inserted
}
pub fn remove(&mut self, value: &T) -> bool {
let is_remove = remove(&mut self.root, value);
if is_remove {
self.length -= 1;
}
is_remove
}
pub fn len(&self) -> usize {
self.length
}
pub fn is_empty(&self) -> bool {
self.length == 0
}
fn node_iter(&self) -> NodeIter<T> {
let cap = self.root.as_ref().map_or(0, |x| x.height);
let mut node_iter = NodeIter {
stack: Vec::with_capacity(cap)
};
// 迭代实现，中序遍历，这里先把左子树全部压进去
let mut current = &self.root;
while let Some(node) = current {
node_iter.stack.push(node.as_ref());
current = &node.left;
}
node_iter
}
pub fn iter(&self) -> Iter<T> {
Iter {
node_iter: self.node_iter(),
}
}
}
struct NodeIter<'a, T: Ord> {
stack: Vec<&'a AvlNode<T>>,
}
impl<'a, T: Ord> Iterator for NodeIter<'a, T> {
type Item = &'a AvlNode<T>;
fn next(&mut self) -> Option<Self::Item> {
// 中序遍历，后半段
if let Some(node) = self.stack.pop() {
let mut current = &node.right;
while let Some(subtree) = current {
self.stack.push(subtree.as_ref());
current = &subtree.left;
}
Some(node)
} else {
None
}
}
}
impl<T: Ord> FromIterator<T> for AvlTree<T> {
fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
let mut tree = AvlTree::new();
for value in iter {
tree.insert(value);
}
tree
}
}
fn insert<T: Ord>(tree: &mut Option<Box<AvlNode<T>>>, value: T) -> bool {
if let Some(node) = tree {
let is_inserted = match value.cmp(&node.value) {
Ordering::Less => insert(&mut node.left, value),
Ordering::Equal => false,
Ordering::Greater => insert(&mut node.right, value),
};
if is_inserted {
node.rebalance();
}
is_inserted
} else {
*tree = Some(Box::new(AvlNode {
value,
height: 1,
left: None,
right: None,
}));
true
}
}
fn remove<T: Ord>(tree: &mut Option<Box<AvlNode<T>>>, value: &T) -> bool {
if let Some(node) = tree {
let is_removed = match value.cmp(&node.value) {
Ordering::Less => remove(&mut node.left, value),
Ordering::Equal => {
*tree = match (node.left.take(), node.right.take()) {
(None, None) => None,
(Some(val), None) | (None, Some(val)) => Some(val),
(Some(left), Some(right)) => Some(merge(left, right)),
};
return true;
}
Ordering::Greater => remove(&mut node.right, value),
};
is_removed
} else {
false
}
}
fn merge<T: Ord>(left: Box<AvlNode<T>>, right: Box<AvlNode<T>>) -> Box<AvlNode<T>> {
let mut op_right = Some(right);
let mut root = take_min(&mut op_right).unwrap();
root.left = Some(left);
root.right = op_right;
root.rebalance();
root
}
fn take_min<T: Ord>(tree: &mut Option<Box<AvlNode<T>>>) -> Option<Box<AvlNode<T>>> {
if let Some(mut node) = tree.take() {
if let Some(small) = take_min(&mut node.left) {
node.rebalance();
*tree = Some(node);
Some(small)
} else {
*tree = node.right.take();
Some(node)
}
} else {
None
}
}
pub struct Iter<'a, T: Ord> {
node_iter: NodeIter<'a, T>,
}
impl<'a, T: Ord> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
match self.node_iter.next() {
Some(node) => Some(&node.value),
None => None
}
}
}
#[derive(Clone, Copy)]
enum Side {
Left,
Right,
}
impl Not for Side {
type Output = Side;
fn not(self) -> Self::Output {
match self {
Side::Left => Side::Right,
Side::Right => Side::Left,
}
}
}
struct AvlNode<T: Ord> {
value: T,
height: usize,
left: Option<Box<AvlNode<T>>>,
right: Option<Box<AvlNode<T>>>,
}
impl<T: Ord> AvlNode<T> {
fn child(&self, side: Side) -> &Option<Box<AvlNode<T>>> {
match side {
Side::Left => &self.left,
Side::Right => &self.right,
}
}
fn child_mut(&mut self, side: Side) -> &mut Option<Box<AvlNode<T>>> {
match side {
Side::Left => &mut self.left,
Side::Right => &mut self.right,
}
}
fn height(&self, side: Side) -> usize {
self.child(side).as_ref().map_or(0, |n| n.height)
}
fn balance_factor(&self) -> i8 {
let (left, right) = (self.height(Side::Left), self.height(Side::Right));
if left < right {
(right - left) as i8
} else {
-((left - right) as i8)
}
}
fn update_height(&mut self) {
self.height = 1 + max(self.height(Side::Left), self.height(Side::Right));
}
fn rotate(&mut self, side: Side) {
let mut subtree = self.child_mut(!side).take().unwrap();
*self.child_mut(!side) = subtree.child_mut(side).take();
self.update_height();
swap(self, subtree.as_mut());
*self.child_mut(side) = Some(subtree);
self.update_height();
}
fn rebalance(&mut self) {
self.update_height();
let side = match self.balance_factor() {
-2 => Side::Left,
2 => Side::Right,
_ => return,
};
let subtree = self.child_mut(side).as_mut().unwrap();
if let (Side::Left, 1) | (Side::Right, -1) = (side, subtree.balance_factor()) {
subtree.rotate(side);
}
self.rotate(!side);
}
}
impl<T: Ord> Default for AvlTree<T> {
fn default() -> Self {
Self::new()
}
}
}SortedList
mod avl_tree {
use std::cmp::{max, Ordering};
use std::fmt;
use std::fmt::Display;
use std::iter::FromIterator;
use std::mem::swap;
use std::ops::Not;
pub type SortedList<T> = AvlTree<T>;
pub struct AvlTree<T: Ord> {
root: Option<Box<AvlNode<T>>>,
length: usize,
}
impl<T: Ord> AvlTree<T> {
pub fn new() -> Self {
Self {
root: None,
length: 0,
}
}
pub fn contains(&self, value: &T) -> bool {
let mut current = &self.root;
while let Some(node) = current {
current = match value.cmp(&node.value) {
Ordering::Less => &node.left,
Ordering::Equal => return true,
Ordering::Greater => &node.right,
}
}
false
}
pub fn insert(&mut self, value: T) -> bool {
let is_inserted = insert(&mut self.root, value);
if is_inserted {
self.length += 1;
}
is_inserted
}
pub fn remove(&mut self, value: &T) -> bool {
let is_remove = remove(&mut self.root, value);
if is_remove {
self.length -= 1;
}
is_remove
}
// 还没调好
pub fn nth(&self, n: usize) -> Option<&T> {
nth(&self.root, n)
}
// 还没调好
pub fn get_rank(&self, value: &T) -> Result<usize, usize> {
if let Some(rank) = get_rank(&self.root, value) {
Ok(rank + 1)
} else {
if let Some(successor) = successor(&self.root, value) {
let mut result = get_rank(&self.root, successor).unwrap();
if predecessor(&self.root, value).is_some() {
result += 1;
}
Err(result)
} else {
Err(self.length + 1)
}
}
}
pub fn predecessor(&self, value: &T) -> Option<&T> {
predecessor(&self.root, value)
}
pub fn successor(&self, value: &T) -> Option<&T> {
successor(&self.root, value)
}
pub fn len(&self) -> usize {
self.length
}
pub fn is_empty(&self) -> bool {
self.length == 0
}
fn node_iter(&self) -> NodeIter<T> {
let cap = self.root.as_ref().map_or(0, |x| x.height);
let mut node_iter = NodeIter {
stack: Vec::with_capacity(cap)
};
// 迭代实现，中序遍历，这里先把左子树全部压进去
let mut current = &self.root;
while let Some(node) = current {
node_iter.stack.push((node.as_ref(), node.count.clone()));
current = &node.left;
}
node_iter
}
pub fn iter(&self) -> Iter<T> {
Iter {
node_iter: self.node_iter(),
}
}
}
impl<T: Ord + Display> Display for AvlTree<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if self.is_empty() {
writeln!(f, "Empty Tree")?
} else {
fmt_tree(&self.root, f, 0)?;
}
Ok(())
}
}
struct NodeIter<'a, T: Ord> {
stack: Vec<(&'a AvlNode<T>, usize)>,
}
impl<'a, T: Ord> Iterator for NodeIter<'a, T> {
type Item = &'a AvlNode<T>;
fn next(&mut self) -> Option<Self::Item> {
// 中序遍历，后半段
if let Some((node, count)) = self.stack.pop() {
if count == 1 {
let mut current = &node.right;
while let Some(subtree) = current {
self.stack.push((subtree.as_ref(), subtree.count.clone()));
current = &subtree.left;
}
} else {
self.stack.push((node, count - 1))
}
Some(node)
} else {
None
}
}
}
impl<T: Ord> FromIterator<T> for AvlTree<T> {
fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
let mut tree = AvlTree::new();
for value in iter {
tree.insert(value);
}
tree
}
}
fn fmt_tree<T: Ord + Display>(tree: &Option<Box<AvlNode<T>>>,
f: &mut fmt::Formatter, indent: usize) -> fmt::Result {
if let Some(node) = tree {
fmt_tree(&node.left, f, indent + 16)?;
writeln!(f, "{:>width$}[{}]({})", node.value, node.count, node.size, width = indent)?;
fmt_tree(&node.right, f, indent + 16)?;
} else {
writeln!(f, "{:>width$}", "None", width = indent)?;
}
Ok(())
}
fn insert<T: Ord>(tree: &mut Option<Box<AvlNode<T>>>, value: T) -> bool {
if let Some(node) = tree {
let is_inserted = match value.cmp(&node.value) {
Ordering::Less => insert(&mut node.left, value),
Ordering::Equal => {
node.count += 1;
node.size += 1;
true
}
Ordering::Greater => insert(&mut node.right, value),
};
if is_inserted {
node.rebalance();
}
is_inserted
} else {
*tree = Some(Box::new(AvlNode {
value,
height: 1,
size: 1,
count: 1,
left: None,
right: None,
}));
true
}
}
fn remove<T: Ord>(tree: &mut Option<Box<AvlNode<T>>>, value: &T) -> bool {
if let Some(node) = tree {
let is_removed = match value.cmp(&node.value) {
Ordering::Less => remove(&mut node.left, value),
Ordering::Equal => {
if node.count > 1 {
node.count -= 1;
} else {
*tree = match (node.left.take(), node.right.take()) {
(None, None) => None,
(Some(val), None) | (None, Some(val)) => Some(val),
(Some(left), Some(right)) => Some(merge(left, right)),
};
}
return true;
}
Ordering::Greater => remove(&mut node.right, value),
};
if is_removed {
node.rebalance();
}
is_removed
} else {
false
}
}
fn nth<T: Ord>(tree: &Option<Box<AvlNode<T>>>, n: usize) -> Option<&T> {
if let Some(node) = tree {
let left_size = node.size(Side::Left);
if n < left_size {
nth(&node.left, n)
} else if n == left_size || n < left_size + node.count {
Some(&node.value)
} else {
nth(&node.right, n - left_size - node.count)
}
} else {
None
}
}
fn get_rank<T: Ord>(tree: &Option<Box<AvlNode<T>>>, value: &T) -> Option<usize> {
if let Some(node) = tree {
let left_size = node.size(Side::Left);
let result = match value.cmp(&node.value) {
Ordering::Less => get_rank(&node.left, value),
Ordering::Equal => Some(left_size),
Ordering::Greater =>
get_rank(&node.right, value).map(|rank| left_size + node.count + rank)
};
result
} else {
None
}
}
fn predecessor<'a, T: Ord>(tree: &'a Option<Box<AvlNode<T>>>, value: &T) -> Option<&'a T> {
if let Some(node) = tree {
let result = match value.cmp(&node.value) {
Ordering::Less => predecessor(&node.left, value),
Ordering::Equal => find_extreme(&node.left, Side::Right),
Ordering::Greater => predecessor(&node.right, value).or(Some(&node.value)),
};
result
} else {
None
}
}
fn successor<'a, T: Ord>(tree: &'a Option<Box<AvlNode<T>>>, value: &T) -> Option<&'a T> {
if let Some(node) = tree {
let result = match value.cmp(&node.value) {
Ordering::Less => successor(&node.left, value).or(Some(&node.value)),
Ordering::Equal => find_extreme(&node.right, Side::Left),
Ordering::Greater => successor(&node.right, value),
};
result
} else {
None
}
}
fn merge<T: Ord>(left: Box<AvlNode<T>>, right: Box<AvlNode<T>>) -> Box<AvlNode<T>> {
let mut op_right = Some(right);
let mut root = take_min(&mut op_right).unwrap();
root.left = Some(left);
root.right = op_right;
root.rebalance();
root
}
fn take_min<T: Ord>(tree: &mut Option<Box<AvlNode<T>>>) -> Option<Box<AvlNode<T>>> {
if let Some(mut node) = tree.take() {
if let Some(small) = take_min(&mut node.left) {
node.rebalance();
*tree = Some(node);
Some(small)
} else {
*tree = node.right.take();
Some(node)
}
} else {
None
}
}
fn find_extreme<T: Ord>(tree: &Option<Box<AvlNode<T>>>, side: Side) -> Option<&T> {
let mut current = tree;
while let Some(node) = current {
if node.child(side).is_none() {
return Some(&node.value);
}
current = &node.child(side);
}
None
}
pub struct Iter<'a, T: Ord> {
node_iter: NodeIter<'a, T>,
}
impl<'a, T: Ord> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
match self.node_iter.next() {
Some(node) => Some(&node.value),
None => None
}
}
}
#[derive(Clone, Copy)]
enum Side {
Left,
Right,
}
impl Not for Side {
type Output = Side;
fn not(self) -> Self::Output {
match self {
Side::Left => Side::Right,
Side::Right => Side::Left,
}
}
}
struct AvlNode<T: Ord> {
value: T,
height: usize,
size: usize,
count: usize,
left: Option<Box<AvlNode<T>>>,
right: Option<Box<AvlNode<T>>>,
}
impl<T: Ord> AvlNode<T> {
fn child(&self, side: Side) -> &Option<Box<AvlNode<T>>> {
match side {
Side::Left => &self.left,
Side::Right => &self.right,
}
}
fn child_mut(&mut self, side: Side) -> &mut Option<Box<AvlNode<T>>> {
match side {
Side::Left => &mut self.left,
Side::Right => &mut self.right,
}
}
fn height(&self, side: Side) -> usize {
self.child(side).as_ref().map_or(0, |n| n.height)
}
fn size(&self, side: Side) -> usize {
self.child(side).as_ref().map_or(0, |n| n.size)
}
fn balance_factor(&self) -> i8 {
let (left, right) = (self.height(Side::Left), self.height(Side::Right));
if left < right {
(right - left) as i8
} else {
-((left - right) as i8)
}
}
fn update_height(&mut self) {
self.height = 1 + max(self.height(Side::Left), self.height(Side::Right));
}
fn update_size(&mut self) {
self.size = self.count + self.size(Side::Left) + self.size(Side::Right);
}
fn rotate(&mut self, side: Side) {
let mut subtree = self.child_mut(!side).take().unwrap();
*self.child_mut(!side) = subtree.child_mut(side).take();
self.update_height();
self.update_size();
swap(self, subtree.as_mut());
*self.child_mut(side) = Some(subtree);
self.update_height();
self.update_size();
}
fn rebalance(&mut self) {
self.update_height();
self.update_size();
let side = match self.balance_factor() {
-2 => Side::Left,
2 => Side::Right,
_ => return,
};
let subtree = self.child_mut(side).as_mut().unwrap();
if let (Side::Left, 1) | (Side::Right, -1) = (side, subtree.balance_factor()) {
subtree.rotate(side);
}
self.rotate(!side);
}
}
impl<T: Ord> Default for AvlTree<T> {
fn default() -> Self {
Self::new()
}
}
}SortedMap // TODO
素数筛
mod prime_table {
pub struct PrimeTable {
primes: Vec<usize>,
is_prime: Vec<bool>,
}
impl PrimeTable {
fn new(n: usize) -> Self {
let mut primes = Vec::new();
let mut is_prime = vec![true; n + 1];
for i in 2..=n {
if is_prime[i] {
primes.push(i);
}
for &_prime in &primes {
if i * _prime > n {
break;
}
is_prime[i * _prime] = false;
if i % _prime == 0 {
break;
}
}
}
Self {
primes,
is_prime,
}
}
fn get_primes(&self) -> &Vec<usize> {
&self.primes
}
fn is_primes(&self, val: usize) -> bool {
self.is_prime[val]
}
}
}树状数组
mod fenwick {
pub struct Fenwick {
tree: Vec<i128>,
}
impl Fenwick {
pub fn new(n: usize) -> Self {
Self {
tree: vec![0; n],
}
}
pub fn add_point(&mut self, idx: i128, k: i128) {
let mut idx = idx;
while (idx as usize) < (self.tree.len()) {
self.tree[idx as usize] += k;
idx += idx & -idx;
}
}
// 左闭右开 [4, 5)
pub fn add_range(&mut self, left: i128, right: i128, k: i128) {
self.add_point(left, k);
self.add_point(right, -k);
}
pub fn query_point(&mut self, idx: i128) -> i128 {
let mut answer = 0i128;
let mut idx = idx;
while idx > 0 {
answer += self.tree[idx as usize];
idx -= idx & -idx
}
return answer;
}
// 左闭右开 [4, 5)
pub fn query_range(&mut self, left: i128, right: i128) -> i128 {
if right < left {
return -1;
}
self.query_point(right - 1) - self.query_point(left - 1)
}
}
}线段树
mod segment_tree {
pub struct SegmentTree<T> {
tree: Vec<T>,
lazy: Vec<T>,
size: usize,
}
impl<T> SegmentTree<T>
where
T: Default + Eq + Copy + Add<Output=T> + Mul<Output=T> + From<u64>,
{
pub fn new(arr: &[T]) -> Self {
let size = arr.len();
let mut st = SegmentTree {
tree: vec![T::default(); size << 2],
lazy: vec![T::default(); size << 2],
size,
};
st.build(0, 0, size - 1, arr);
st
}
pub fn build(&mut self, node: usize, start: usize, end: usize, arr: &[T]) {
if start == end {
self.tree[node] = arr[start];
return;
}
let mid = (start + end) >> 1;
let left = node << 1 | 1;
let right = left + 1;
self.build(left, start, mid, arr);
self.build(right, mid + 1, end, arr);
self.tree[node] = self.tree[left] + self.tree[right];
}
pub fn update_range(&mut self, l: usize, r: usize, val: T) {
self.update_range_recursive(0, 0, self.size - 1, l, r, val);
}
fn update_range_recursive(&mut self, node: usize, start: usize, end: usize, left: usize, right: usize, data: T) {
if left <= start && end <= right {
self.tree[node] = self.tree[node] + T::from((end - start + 1) as u64) * data;
self.lazy[node] = self.lazy[node] + data;
return;
}
if start == end {
return;
}
let mid = (start + end) >> 1;
let left_child = node << 1 | 1;
let right_child = left_child + 1;
self.propagate(node, start, end);
if left <= mid {
self.update_range_recursive(left_child, start, mid, left, right, data);
}
if right > mid {
self.update_range_recursive(right_child, mid + 1, end, left, right, data);
}
self.tree[node] = self.tree[left_child] + self.tree[right_child];
}
pub fn query_point(&mut self, idx: usize) -> T {
self.query_range_recursive(0, 0, self.size - 1, idx, idx)
}
pub fn query_range(&mut self, l: usize, r: usize) -> T {
self.query_range_recursive(0, 0, self.size - 1, l, r)
}
fn query_range_recursive(&mut self, node: usize, start: usize, end: usize, left: usize, right: usize) -> T {
if left <= start && end <= right {
return self.tree[node];
}
if start == end {
return T::default()
}
let mid = (start + end) >> 1;
let left_child = node << 1 | 1;
let right_child = left_child + 1;
self.propagate(node, start, end);
let mut result = T::default();
if left <= mid {
result = result + self.query_range_recursive(left_child, start, mid, left, right);
}
if right > mid {
result = result + self.query_range_recursive(right_child, mid + 1, end, left, right);
}
return result;
}
fn propagate(&mut self, node: usize, start: usize, end: usize) {
if start == end {
return;
}
let mid = (start + end) >> 1;
let left = node << 1 | 1;
let right = left + 1;
self.tree[left] = self.tree[left] + T::from((mid - start + 1) as u64) * self.lazy[node];
self.tree[right] = self.tree[right] + T::from((end - mid) as u64) * self.lazy[node];
self.lazy[left] = self.lazy[left] + self.lazy[node];
self.lazy[right] = self.lazy[right] + self.lazy[node];
self.lazy[node] = T::default();
}
}
}ST表
mod sparse_table {
pub struct SparseTable {
data: Vec<Vec<i32>>,
prelog: Vec<usize>,
}
impl SparseTable {
pub fn with_capacity(n: usize) -> Self {
let mut prelog = vec![0; n + 1];
for i in 2..=n {
prelog[i] = prelog[i / 2] + 1;
}
Self {
data: vec![vec![0; 21]; n + 1],
prelog,
}
}
pub fn init(&mut self, vals: &Vec<i32>) {
let n = vals.len();
for i in 0..n {
self.data[i + 1][0] = vals[i];
}
for j in 1..=20 {
let mut i = 1;
while i + (1 << j) - 1 <= n {
self.data[i][j] = self.data[i][j - 1].max(self.data[i + (1 << j - 1)][j - 1]);
i += 1;
}
}
}
pub fn query(&self, l: usize, r: usize) -> i32 {
let k = self.prelog[r - l + 1];
self.data[l][k].max(self.data[r - (1 << k) + 1][k])
}
}
}并查集
mod dsu {
pub struct DisjointSetUnion {
fathers: Vec<usize>,
sizes: Vec<usize>,
}
impl DisjointSetUnion {
pub fn new(size: usize) -> Self {
Self {
fathers: (0..=size).collect(),
sizes: vec![1; size],
}
}
pub fn find(&mut self, x: usize) -> usize {
return if self.fathers[x] == x {
x
} else {
self.fathers[x] = self.find(self.fathers[x]);
self.fathers[x]
};
}
pub fn connect(&mut self, x: usize, y: usize) {
let mut fx = self.find(x);
let mut fy = self.find(y);
if fx == fy {
return;
}
if self.sizes[fx] > self.sizes[fy] {
swap(&mut fx, &mut fy);
}
self.fathers[fx] = fy;
self.sizes[fy] += self.sizes[fx];
}
pub fn are_connected(&mut self, x: usize, y: usize) -> bool {
return self.find(x) == self.find(y);
}
}
}指针实现，线段树
mod pointer_segment_tree {
use std::cell::RefCell;
use std::rc::Rc;
use std::ops::{Add, Mul};
struct SegmentTreeNode<T> {
data: T,
lazy: T,
start: usize,
end: usize,
left_child: Option<Rc<RefCell<SegmentTreeNode<T>>>>,
right_child: Option<Rc<RefCell<SegmentTreeNode<T>>>>,
}
impl<T> SegmentTreeNode<T>
where
T: Default,
{
fn new(data: T, start: usize, end: usize) -> Self {
SegmentTreeNode {
data,
lazy: T::default(),
start,
end,
left_child: None,
right_child: None,
}
}
}
pub struct SegmentTree<T> {
root: Option<Rc<RefCell<SegmentTreeNode<T>>>>,
// 可为空的 智能指针指向的 可以引用调用的 T类型的 线段树节点
size: usize,
}
impl<T> SegmentTree<T>
where
T: Default + Eq + Copy + Add<Output=T> + Mul<Output=T> + From<u64>,
{
pub fn new(arr: &[T]) -> Self {
let length = arr.len();
let mut st = SegmentTree {
root: None,
size: 0,
};
st.root = Some(Rc::new(RefCell::new(st.build(&arr, 0, length - 1))));
st
}
fn build(&mut self, arr: &[T], start: usize, end: usize) -> SegmentTreeNode<T> {
if start == end {
self.size += 1;
return SegmentTreeNode::new(arr[start], start, end);
}
let mid = (start + end) >> 1;
self.size += 1;
let mut node = SegmentTreeNode::new(T::default(), start, end);
if start <= mid {
let left_child = self.build(arr, start, mid);
node.data = node.data + left_child.data;
node.left_child = Some(Rc::new(RefCell::new(left_child)));
}
if end > mid {
let right_child = self.build(arr, mid + 1, end);
node.data = node.data + right_child.data;
node.right_child = Some(Rc::new(RefCell::new(right_child)));
}
node
}
fn push_down(&self, node: &Rc<RefCell<SegmentTreeNode<T>>>) {
let mut node_ref = node.borrow_mut();
if node_ref.start == node_ref.end {
return;
}
let mid = (node_ref.start + node_ref.end) >> 1;
if let Some(left_child) = &node_ref.left_child {
let mut left_ref = left_child.borrow_mut();
left_ref.data = left_ref.data + T::from((mid - node_ref.start + 1) as u64) * node_ref.lazy;
left_ref.lazy = left_ref.lazy + node_ref.lazy;
}
if let Some(right_child) = &node_ref.right_child {
let mut right_ref = right_child.borrow_mut();
right_ref.data = right_ref.data + T::from((node_ref.end - mid) as u64) * node_ref.lazy;
right_ref.lazy = right_ref.lazy + node_ref.lazy;
}
node_ref.lazy = T::default();
}
// 左闭右开 [left, right)
pub fn update_range(&mut self, left: usize, right: usize, data: T) {
if let Some(root) = &self.root {
self.update_range_recursive(Rc::clone(root), left, right - 1, data);
}
}
pub fn update_point(&mut self, index: usize, data: T) {
if let Some(root) = &self.root {
self.update_range_recursive(Rc::clone(root), index, index, data);
}
}
fn update_range_recursive(&mut self, node: Rc<RefCell<SegmentTreeNode<T>>>, left: usize, right: usize, data: T) {
let mut node_ref = node.borrow_mut();
if left <= node_ref.start && node_ref.end <= right {
node_ref.data = node_ref.data + T::from((node_ref.end - node_ref.start + 1) as u64) * data;
node_ref.lazy = node_ref.lazy + data;
return;
}
if node_ref.end < left || node_ref.start > right {
return;
}
drop(node_ref);
self.push_down(&node);
let mut node_ref = node.borrow_mut();
let mut result = T::default();
let mid = (node_ref.start + node_ref.end) >> 1;
if let Some(left_child) = &node_ref.left_child {
if left <= mid {
self.update_range_recursive(Rc::clone(left_child), left, right, data);
}
result = result + left_child.borrow().data;
}
if let Some(right_child) = &node_ref.right_child {
if mid < right {
self.update_range_recursive(Rc::clone(right_child), left, right, data);
}
result = result + right_child.borrow().data;
}
node_ref.data = result;
}
// 左闭右开 [left, right)
pub fn query_range(&self, left: usize, right: usize) -> T {
if let Some(root) = &self.root {
self.query_range_recursive(Rc::clone(root), left, right - 1)
} else {
T::default()
}
}
pub fn query_point(&self, index: usize) -> T {
if let Some(root) = &self.root {
self.query_range_recursive(Rc::clone(root), index, index)
} else {
T::default()
}
}
fn query_range_recursive(&self, node: Rc<RefCell<SegmentTreeNode<T>>>, left: usize, right: usize) -> T {
let node_ref = node.borrow();
if left <= node_ref.start && node_ref.end <= right {
return node_ref.data;
}
if node_ref.end < left || node_ref.start > right {
return T::default();
}
drop(node_ref);
self.push_down(&node);
let node_ref = node.borrow();
let mut result = T::default();
let mid = (node_ref.start + node_ref.end) >> 1;
if let Some(left_child) = &node_ref.left_child {
if left <= mid {
result = result + self.query_range_recursive(Rc::clone(left_child), left, right);
}
}
if let Some(right_child) = &node_ref.right_child {
if mid < right {
result = result + self.query_range_recursive(Rc::clone(right_child), left, right);
}
}
result
}
}
}锈化工具（rust实现的算法竞赛模板）
https://winterl-blog.netlify.app/2024/11/30/锈化工具/