对于rust而言,其实可以发现很多C++玩家的写法其实都是采用数组开辟,数组元素为0之类的来替代空节点,这样一来相比于用类/结构体而言设计数据结构其实可以省略判断当前指针之类的是否为null/nil...
那么诸如像Python、Rust、Go这类具有代表性的语言该如何用面向对象的思维去书写好的debug的平衡树的代码呢?
平衡树的种类:
我们常说的平衡树为二叉平衡树,为了防止退化成链式我们常常有各种各样的优化方式诞生了众多著名的平衡树:AVL树,红黑树,Treap,Splay...甚至一些用的比较少的树,具体可以在oiwiki上的平衡树章节进行学习.(不然常用分块赌一赌~
手写平衡树的原因:
为什么要手写平衡树,其实在比赛时,如果遇到类似树套树、各种Kth的维护,我认为无论是认识还是书写至少一种平衡树是很有必要的,它与线段树一样其实都是很多人望而生畏的,然而其原理实际上是(不难的
关于平衡树的选择:
那么哪种平衡树是一个比较好的选择:红黑树?AVL树?还是SBT(谐音有点令人咯咯笑)?
以上几种平衡树码量长,不好debug,不太适合一些线下比赛.
个人推荐:旋转Treap、无旋转Treap、Splay(经典了),替罪羊,这三种是比较好书写debug了(当然有人认为SBT和红黑树挺好写的,因人而异了~)
Treap引入:
Treap算常数很小,然后又是很好写的一类平衡树,美中不足在于可能优先级涉及到了随机数,如果运气特别特别特别特别背,那么退化成链是(有可能的~,不过通常情况下不容易被卡,随机数还是有些令人不安呀~,这里treap=二叉平衡树+堆,堆好像是大家都比较熟悉的东西
堆
这里我们的堆实际上该拿出来说一说的,个人建议可以练习下两种可并堆:左偏树与配对堆,比较经典.因为后续涉及到分割和合并的操作是有点相似的.堆大部分人认为val就是比较数,实际不然.更准确的来讲堆比较的其实为"优先级",只是通常情况下我们把值作为优先级.这里不得不提一嘴C#的优先队列将优先级与存储值分开的设计是很正确的一种设计.优先级实际可以看做一种rank,这里我们的treap其实就是val与rank各论各的思想
Treap:
Treap分为两种:可旋转型/无旋转型,至于二者用途与区分,其实对于初学者来说可以不用太过区分,无非是持久化和支持一些其他操作上有些区别,好写还是不好写等等
关于随机数
为啥单独拿出来说呢,因为坑爹的rust除了乐扣以外自动导入了rand这个第三方库,本身标准库是不支持的.在灵茶山群佬的帮助下,提供了一份rust随机数的代码(应该,可能,大概是64位梅森旋转,我也不懂~)
Rust
pub mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN { res.mt[i] = F.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62)).wrapping_add(i as u64); }
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 { self.gen() % n }
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 { f + self.next(t - f + 1) }
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() { RAND = Some(Random::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF) as u64)); }
RAND.as_mut().unwrap()
}
}
pub trait Shuffle { fn shuffle(&mut self); }
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}旋转型Treap:
基于旋转来实现堆性质的方式,实际上这里面的旋转种数归类也就两种,是很easy的(甚至你可以死记硬背,但其实很简单的,画下图观察就知道).我们分为两种旋转:L与R分别左右旋.
然后旋转是什么情况下旋转呢,这个就要用到我们刚开始说的堆思想了.将每个树节点增加个rank表示优先级,这里优先级该为多少(随机数~),为啥随机数好呢,我们来思考两个节点Father->right,假如最开始Father作为根节点,并且这是一条链,那么如果我们随机数为fa.rank<right.rank,(以小根堆为例),其实这不影响任何效果.但假如fa.rank>right.rank,那么我们需要用左旋L,让right变为根节点,fa则变为它的左子树,这个时候我们会发现树的深度-1,Soga.引入随机数以后,我们可以让原本应该成接近链状的树更不容易形成链了(确实有随机的感觉了),具体证明可以参照oiwiki.
好了,那么该如何书写呢:
定义:
这里我们先采用rust里常见的一种方式:智能指针
使用智能指针定义Node的left和right:Option<Box<Node>>,为啥用Box智能指针呢,那是因为其实在不涉及到需要多个所有者同时拥有树节点时,一般是不需要Rc和Refcell,前者实现多个所有者,后者实现局部可变性.对此我们考虑使用Box就行了,类型名太长咯,type一下,这里为了让初学者更认识参数类型,就先不取别名了,后文取.泛型只需要实现Copy+Ord就行
常见的操作:增加一个元素,二叉搜索查找,空插入,在以上基础情况下插入的节点rank小于或大于当前父亲(二者都行,锁死就好了,反正相信随机数每次插入1/2的机会完成一次旋转,比根节点rank大/小,相等可转可不转,但随机数范围大点也不容易相等).
删除:删除可要分类讨论一下咯,讨论的是当前节点是否有左右子树,这里我们采用常见的dfs写法拼接即可.
查找value第几大、查找第k大的value、lower、upper正常的平衡树操作即可
智能指针Rust参照代码(顺便贴点其他的语言py、go的,比较具备代表性,至于c++的网上倒是挺多的了,我这里主要是叙述一下其他语言的):
Rust
Python
Go
pub mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN { res.mt[i] = F.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62)).wrapping_add(i as u64); }
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 { self.gen() % n }
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 { f + self.next(t - f + 1) }
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() { RAND = Some(Random::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF) as u64)); }
RAND.as_mut().unwrap()
}
}
pub trait Shuffle { fn shuffle(&mut self); }
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}
struct Node<T> where T: Copy + Ord {
val: T,
child: Vec<Option<Box<Node<T>>>>,
rank: u64,
cnt: usize,
size: usize,
}
impl<T> Node<T> where T: Copy + Ord {
pub fn new(v: T) -> Option<Box<Node<T>>> {
let rand = random();
Some(Box::new(Node { val: v, child: vec![None, None], rank: rand.gen(), cnt: 1, size: 1 }))
}
pub fn update(&mut self) {
self.size = self.cnt;
if let Some(left) = self.child[0].as_ref() {
self.size += left.size;
}
if let Some(right) = self.child[1].as_ref() {
self.size += right.size;
}
}
}
struct RotateTreap<T> where T: Copy + Ord {
root: Option<Box<Node<T>>>,
}
#[derive(Clone, Copy)]
enum RotateType {
L,
R,
}
fn rot(x: RotateType) -> usize {
match x {
RotateType::L => 1,
RotateType::R => 0,
}
}
impl<T> RotateTreap<T> where T: Copy + Ord {
pub fn new() -> Self {
Self { root: None }
}
pub fn insert(&mut self, x: T) {
self.root = RotateTreap::add(self.root.take(), x);
}
pub fn rotate(node: Option<Box<Node<T>>>, rotate_type: RotateType) -> Option<Box<Node<T>>> {
let rotate = rot(rotate_type);
if let Some(mut curr) = node {
let mut new_root = curr.child[rotate].take();
curr.child[rotate] = new_root.as_mut().unwrap().child[rotate ^ 1].take();
curr.update();
new_root.as_mut().unwrap().child[rotate ^ 1] = Some(curr);
new_root.as_mut().unwrap().update();
return new_root;
}
None
}
pub fn add(node: Option<Box<Node<T>>>, val: T) -> Option<Box<Node<T>>> {
match node {
None => Node::new(val),
Some(mut x) => {
match val.cmp(&x.val) {
Ordering::Equal => {
x.size += 1;
x.cnt += 1;
}
Ordering::Less => {
x.child[0] = RotateTreap::add(x.child[0].take(), val);
if x.child[0].as_ref().unwrap().rank < x.rank {
x = RotateTreap::rotate(Some(x), RotateType::R).unwrap();
}
}
Ordering::Greater => {
x.child[1] = RotateTreap::add(x.child[1].take(), val);
if x.child[1].as_ref().unwrap().rank < x.rank {
x = RotateTreap::rotate(Some(x), RotateType::L).unwrap();
}
}
}
x.update();
Some(x)
}
}
}
pub fn delete(&mut self, x: T) {
self.root = RotateTreap::remove(self.root.take(), x);
}
pub fn remove(node: Option<Box<Node<T>>>, val: T) -> Option<Box<Node<T>>> {
match node {
None => None,
Some(mut x) => {
match val.cmp(&x.val) {
Ordering::Less => {
x.child[0] = RotateTreap::remove(x.child[0].take(), val);
}
Ordering::Greater => {
x.child[1] = RotateTreap::remove(x.child[1].take(), val);
}
Ordering::Equal => {
if x.cnt > 1 {
x.cnt -= 1;
x.size -= 1;
return Some(x);
}
let mut state = 0;
if x.child[0].is_some() {
state |= 1;
}
if x.child[1].is_some() {
state |= 1 << 1;
}
match state {
0 => return None,
1 => return x.child[0].take(),
2 => return x.child[1].take(),
3 => {
let mut rota = RotateType::L;
if x.child[0].as_ref().unwrap().rank < x.child[1].as_ref().unwrap().rank {
rota = RotateType::R;
}
x = RotateTreap::rotate(Some(x), rota).unwrap();
let idx = rot(rota) ^ 1;
x.child[idx] = RotateTreap::remove(x.child[idx].take(), val);
}
_ => {}
}
}
}
x.update();
Some(x)
}
}
}
pub fn query_kth(&self, val: T) -> usize {
RotateTreap::q_kth(&self.root, val)
}
pub fn q_kth(node: &Option<Box<Node<T>>>, val: T) -> usize {
match node {
None => 0,
Some(x) => {
let mut size = 0;
if x.child[0].is_some() {
size = x.child[0].as_ref().unwrap().size;
}
match val.cmp(&x.val) {
Ordering::Equal => size + 1,
Ordering::Less => {
if x.child[0].is_some() {
return RotateTreap::q_kth(&x.child[0], val);
}
1
}
Ordering::Greater => {
if x.child[1].is_some() {
return RotateTreap::q_kth(&x.child[1], val) + x.cnt + size;
}
size + 1
}
}
}
}
}
pub fn kth_val(&self, k: usize) -> T {
RotateTreap::k_val(&self.root, k)
}
pub fn k_val(node: &Option<Box<Node<T>>>, k: usize) -> T {
let x = node.as_ref().unwrap();
let mut size = 0_usize;
if x.child[0].is_some() {
size = x.child[0].as_ref().unwrap().size;
}
if k <= size {
RotateTreap::k_val(&x.child[0], k)
} else if k <= size + x.cnt {
x.val
} else {
RotateTreap::k_val(&x.child[1], k - x.cnt - size)
}
}
pub fn pre(&self, val: T) -> T {
RotateTreap::pre_ans(&self.root, val)
}
pub fn pre_ans(mut node: &Option<Box<Node<T>>>, val: T) -> T {
let mut ans: T = node.as_ref().unwrap().val;
while node.is_some() {
let x = node.as_ref().unwrap().val;
if x < val {
ans = x;
node = &node.as_ref().unwrap().child[1];
} else {
node = &node.as_ref().unwrap().child[0];
}
}
ans
}
pub fn nxt(&self, val: T) -> T {
RotateTreap::nxt_ans(&self.root, val)
}
pub fn nxt_ans(mut node: &Option<Box<Node<T>>>, val: T) -> T {
let mut ans: T = node.as_ref().unwrap().val;
while node.is_some() {
let x = node.as_ref().unwrap().val;
if x > val {
ans = x;
node = &node.as_ref().unwrap().child[0];
} else {
node = &node.as_ref().unwrap().child[1];
}
}
ans
}
}由于是以前最开始学的时候的代码,还没思考过简化,参照下就行
无旋转Treap
这个实际上我个人认为是非常so easy的一种平衡树.具体差别其实就在于为了维护这个堆这里不采用旋转了,采用分割与合并的方式,可以学习左偏树、配对堆一些常见的可并堆了解.
分割:两种分割方式即可.
1、按value分割,通常按value分割为两棵树:左边<=value,右边>value,=放哪边都行,对应修改就好了.
2、按第k大的数分割,为三部分,左树<k,=k的节点,右树>k
合并没啥好说的,其实就是按上述两种分割以后再对应left和right进行操作就行
参考代码:(Rust智能指针)
Rust
Go
Python
pub mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN { res.mt[i] = F.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62)).wrapping_add(i as u64); }
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 { self.gen() % n }
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 { f + self.next(t - f + 1) }
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() { RAND = Some(Random::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF) as u64)); }
RAND.as_mut().unwrap()
}
}
pub trait Shuffle { fn shuffle(&mut self); }
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}
type TreeNode<T> = Option<Box<Node<T>>>;
struct Node<T> where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
val: T,
left: TreeNode<T>,
right: TreeNode<T>,
rank: u64,
size: usize,
cnt: usize,
}
impl<T> Node<T> where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
pub fn new(val: T) -> TreeNode<T> {
let rand = random();
Some(Box::new(Node { val, left: None, right: None, rank: rand.gen(), size: 1, cnt: 1 }))
}
pub fn update(&mut self) {
self.size = self.cnt;
if self.left.is_some() {
self.size += self.left.as_ref().unwrap().size;
}
if self.right.is_some() {
self.size += self.right.as_ref().unwrap().size;
}
}
}
struct NoRotateTreap<T> where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
root: TreeNode<T>,
one: T,
}
impl<T> NoRotateTreap<T> where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
pub fn new(val: T) -> Self {
Self { root: None, one: val }
}
pub fn insert(&mut self, val: T) {
let (mut l_tree, r_tree) = split_value(self.root.take(), val);
let (l_son, mut r_son) = split_value(l_tree.take(), val - self.one);
if r_son.is_none() {
r_son = Node::new(val);
} else {
r_son.as_mut().unwrap().size += 1;
r_son.as_mut().unwrap().cnt += 1;
}
l_tree = merge(l_son, r_son);
self.root = merge(l_tree, r_tree);
}
pub fn remove(&mut self, val: T) {
let (mut l_tree, r_tree) = split_value(self.root.take(), val);
let (l_son, mut r_son) = split_value(l_tree.take(), val - self.one);
if r_son.as_ref().unwrap().cnt > 1 {
r_son.as_mut().unwrap().cnt -= 1;
r_son.as_mut().unwrap().size -= 1;
} else {
r_son = None;
}
l_tree = merge(l_son, r_son);
self.root = merge(l_tree, r_tree);
}
pub fn query_kth(&mut self, val: T) -> usize {
let (left, right) = split_value(self.root.take(), val - self.one);
let mut ans = 1;
if left.is_some() {
ans = left.as_ref().unwrap().size + 1;
}
self.root = merge(left, right);
ans
}
pub fn kth(&mut self, node: Option<Box<Node<T>>>, k: usize) -> T {
let (left, mid, right) = split_kth(node, k);
let ans = mid.as_ref().unwrap().val;
self.root = merge(merge(left, mid), right);
ans
}
pub fn kth_value(&mut self, k: usize) -> T {
let t = self.root.take();
self.kth(t, k)
}
pub fn pre(&mut self, val: T) -> T {
let (mut left, right) = split_value(self.root.take(), val - self.one);
let size = left.as_ref().unwrap().size;
let ans = self.kth(left.take(), size);
self.root = merge(self.root.take(), right);
ans
}
pub fn nxt(&mut self, val: T) -> T {
let (left, mut right) = split_value(self.root.take(), val);
let ans = self.kth(right.take(), 1);
self.root = merge(left, self.root.take());
ans
}
}
fn split_value<T>(node: TreeNode<T>, val: T) -> (TreeNode<T>, TreeNode<T>) where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
if let Some(mut x) = node {
if x.val > val {
let (l, r) = split_value(x.left.take(), val);
x.left = r;
x.update();
(l, Some(x))
} else {
let (l, r) = split_value(x.right.take(), val);
x.right = l;
x.update();
(Some(x), r)
}
} else {
(None, None)
}
}
fn split_kth<T>(node: Option<Box<Node<T>>>, k: usize) -> (TreeNode<T>, TreeNode<T>, TreeNode<T>) where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
if let Some(mut x) = node {
let mut size = 0;
if x.left.is_some() {
size = x.left.as_ref().unwrap().size;
}
if k <= size {
let (l, mid, r) = split_kth(x.left.take(), k);
x.left = r;
x.update();
(l, mid, Some(x))
} else if k <= size + x.cnt {
let (l, r) = (x.left.take(), x.right.take());
(l, Some(x), r)
} else {
let (l, mid, r) = split_kth(x.right.take(), k - size - x.cnt);
x.right = l;
x.update();
(Some(x), mid, r)
}
} else {
(None, None, None)
}
}
fn merge<T>(x: TreeNode<T>, y: TreeNode<T>) -> TreeNode<T> where T: Copy + Ord + Sub<Output=T> + Add<Output=T> {
if let Some(mut l) = x {
if let Some(mut r) = y {
if l.rank < r.rank {
l.right = merge(l.right.take(), Some(r));
l.update();
Some(l)
} else {
r.left = merge(Some(l), r.left.take());
r.update();
Some(r)
}
} else {
Some(l)
}
} else {
y
}
}Splay树
伸展树是一个比较常见的平衡树,码量适中,核心操作:伸展
伸展是啥呢,就是把你当前访问的这个点通过"旋转"旋到根节点处.美其名曰:访问过的点很有可能再次访问,可以用来克服那种大量地反复查找同一个数的情况.其他操作类似.
这里要提一点的就是删除操作,当前节点如果要被删掉,那么很显然应该把两棵子树合并代替当前节点.合并其实很简单,两者不为空:
1、查找left的最大值(第left_size小),查找完以后由于有splay操作,它会被变为left的根节点(这里注意提前设置left和right的father为空防止转到整棵伸展树的根去).然后left.right=right更新返回left即可
2、也可以反过来查找right的最小的值(第1小),然后right.left=left,更新返回right即可
这里rust我们采用一种跑得快的方式书写:(裸指针)
裸指针将比智能指针跑得更快
Rust
Go
Python
#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
struct Node(*mut TreeNode);
#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
struct TreeNode {
fa: Node,
child: [Node; 2],
size: usize,
val: i64,
cnt: usize,
}
impl Node {
pub fn none() -> Self {
Self(std::ptr::null_mut())
}
pub fn new(val: i64, fa: Node) -> Self {
let mut ans = Self::none();
ans.0 = Box::into_raw(Box::new(TreeNode {
val,
fa,
child: [Self::none(), Self::none()],
cnt: 1,
size: 1,
}));
ans
}
#[inline]
pub fn clear(&mut self) {
let old = self.0;
self.0 = std::ptr::null_mut();
unsafe {
let _ = Box::from_raw(old);
}
}
#[inline]
pub fn fa(&self) -> &Node {
unsafe { &(*self.0).fa }
}
#[inline]
pub fn fa_mut(&mut self) -> &mut Node {
unsafe { &mut (*self.0).fa }
}
#[inline]
pub fn size(&self) -> usize {
unsafe { (*self.0).size }
}
#[inline]
pub fn cnt(&self) -> usize {
unsafe { (*self.0).cnt }
}
#[inline]
pub fn left(&self) -> &Node {
unsafe { &(*self.0).child[0] }
}
#[inline]
pub fn left_mut(&mut self) -> &Node {
unsafe { &mut (*self.0).child[0] }
}
#[inline]
pub fn right(&self) -> &Node {
unsafe { &(*self.0).child[1] }
}
#[inline]
pub fn right_mut(&mut self) -> &Node {
unsafe { &mut (*self.0).child[1] }
}
#[inline]
pub fn exist(&self) -> bool {
!self.0.is_null()
}
#[inline]
pub unsafe fn update(&mut self) {
(*self.0).size = self.cnt();
if self.left().exist() {
(*self.0).size += self.left().size();
}
if self.right().exist() {
(*self.0).size += self.right().size();
}
}
#[inline]
pub fn idx(&self) -> usize {
if self.fa().exist() && self.fa().right() == self {
return 1;
}
0
}
#[inline]
pub fn val(&self) -> i64 {
unsafe { (*self.0).val }
}
#[inline]
pub unsafe fn rotate(&mut self) {
let mut curr = *self;
let id = self.idx();
let mut fa = (*self.0).fa;
if fa.exist() {
let fa_id = fa.idx();
let faf = (*fa.0).fa;
if faf.exist() {
(*faf.0).child[fa_id] = curr;
}
*curr.fa_mut() = faf;
(*fa.0).child[id] = (*curr.0).child[id ^ 1];
if (*curr.0).child[id ^ 1].exist() {
*(*curr.0).child[id ^ 1].fa_mut() = fa;
}
(*curr.0).child[id ^ 1] = fa;
*fa.fa_mut() = curr;
fa.update();
curr.update();
*self = Node {
..curr
};
}
}
#[inline]
pub unsafe fn splay(&mut self) {
while self.fa().exist() {
if self.fa().fa().exist() {
if self.idx() == self.fa().idx() {
self.fa_mut().rotate();
} else {
self.rotate();
}
}
self.rotate();
}
}
#[inline]
pub unsafe fn query(&mut self, val: i64) -> usize {
let mut curr = *self;
let mut ans = 0;
loop {
if curr.0.is_null(){
return 0;
}
let mut size = 0;
if curr.left().exist() {
size = curr.left().size();
}
if val < curr.val() {
if !curr.left().exist() {
curr.splay();
*self = Node {
..curr
};
return ans;
}
curr = *curr.left();
} else if val == curr.val() {
curr.splay();
*self = Node {
..curr
};
return ans + size;
} else {
ans += curr.cnt() + size;
if !curr.right().exist() {
curr.splay();
*self = Node {
..curr
};
return ans;
}
curr = *curr.right();
}
}
}
#[inline]
pub unsafe fn kth(&mut self, mut k: usize) -> i64 {
let mut curr = *self;
loop {
let mut size = 0;
if curr.left().exist() {
size = curr.left().size();
}
if k <= size {
curr = *curr.left();
} else if k <= size + curr.cnt() {
curr.splay();
*self = Node {
..curr
};
return curr.val();
} else {
k -= size + curr.cnt();
curr = *curr.right();
}
}
}
}
unsafe fn merge(mut x: Node, mut y: Node) -> Node {
if !x.exist() {
if y.exist() {
*y.fa_mut() = Node::none();
}
return y;
}
if !y.exist() {
*x.fa_mut() = Node::none();
return x;
}
*x.fa_mut() = Node::none();
*y.fa_mut() = Node::none();
y.kth(1);
(*y.0).child[0] = x;
(*x.0).fa = y;
y.update();
y
}
struct SplayTree {
root: Node,
}
impl SplayTree {
pub fn new() -> Self {
Self { root: Node::none() }
}
#[inline]
pub unsafe fn insert(&mut self, val: i64) {
if !self.root.exist() {
self.root = Node::new(val, Node::none());
return;
}
let mut curr = self.root;
loop {
if curr.val() == val {
(*curr.0).cnt += 1;
(*curr.0).size += 1;
curr.splay();
self.root = Node {
..curr
};
return;
} else {
let mut i = 0;
if curr.val() < val {
i = 1;
}
if !(*curr.0).child[i].exist() {
(*curr.0).child[i] = Node::new(val, curr);
curr.update();
curr = (*curr.0).child[i];
curr.splay();
self.root = Node {
..curr
};
return;
} else {
curr = (*curr.0).child[i];
}
}
}
}
#[inline]
pub unsafe fn remove(&mut self, val: i64) {
self.root.query(val);
if self.root.val() == val {
if self.root.cnt() > 1 {
(*self.root.0).cnt -= 1;
(*self.root.0).size -= 1;
} else {
self.root = merge(*self.root.left(), *self.root.right());
}
}
}
#[inline]
pub unsafe fn query(&mut self, val: i64) -> usize {
self.root.query(val) + 1
}
#[inline]
pub unsafe fn kth(&mut self, k: usize) -> i64 {
self.root.kth(k)
}
#[inline]
pub unsafe fn pre(&mut self, val: i64) -> i64 {
let mut curr = self.root;
let mut ans = Node::none();
while curr.exist() {
if curr.val() < val {
ans = curr;
curr = *curr.right();
} else {
curr = *curr.left();
}
}
if !ans.exist() {
return -2147483647;
}
ans.splay();
self.root = Node {
..ans
};
ans.val()
}
#[inline]
pub unsafe fn nxt(&mut self, val: i64) -> i64 {
let mut curr = self.root;
let mut ans = Node::none();
while curr.exist() {
if curr.val() > val {
ans = curr;
curr = *curr.left();
} else {
curr = *curr.right();
}
}
if !ans.exist() {
return 2147483647;
}
ans.splay();
self.root = Node {
..ans
};
ans.val()
}
}(值得提一嘴的是,由于树存在大量递归操作,对py这种语言常数可以看做其他语言的xxx倍,在cf、洛谷等平台基本tle伺候)
替罪羊树
一个名字很陌生,但很优秀的暴力平衡树维护.
核心思想:(如果一棵树长得太高太瘦了,咱就把它拍平)
is_need_rebuild:当前子树是否需要拍平.这里是类似于加权平衡二叉树,如果左右两侧某侧过于重了,拍平,一般比例因子为0.6-0.8,0.75较为合适
rebuild:重建这棵树,其实这是很容易的,只需要两步.
1、中序遍历拿到序列
2、依次从mid往两边构建新树返回
rebuild是每次插入或者删除每一个Node都要判断是否需要rebuild,有的人要问,为啥不只判断根节点is_need_rebuild,这样rebuild次数少.是否有子树需要rebuild而根不用呢,有啊.让根保持比例边缘,子树成链即可.所以子树应该也需要判断.事实上rebuild并不是一个很频繁的操作,一般也只有小一点的树进行rebuild操作,很少整棵巨树重建
remove()这里remove是采用lazy操作,在rebuild的时候删掉cnt==0的点(不加入中序遍历序列)即可
两种Rust版本的替罪羊树:
Rust智能指针版本
Rust(裸指针版本)
Python
Go
use std::cell::RefCell;
use std::rc::Rc;
type Node<T> = Option<Rc<RefCell<TreeNode<T>>>>;
struct TreeNode<T> where T: Copy + Ord + Default {
left: Node<T>,
right: Node<T>,
val: T,
size1: usize,
size2: usize,
del_size: usize,
cnt: usize,
}
fn get_size1<T>(node: &Node<T>) -> usize where T: Copy + Ord + Default {
if node.is_none() {
return 0;
}
return node.as_ref().unwrap().borrow().size1;
}
fn get_size2<T>(node: &Node<T>) -> usize where T: Copy + Ord + Default {
if node.is_none() {
return 0;
}
return node.as_ref().unwrap().borrow().size2;
}
fn get_del_size<T>(node: &Node<T>) -> usize where T: Copy + Ord + Default {
if node.is_none() {
return 0;
}
return node.as_ref().unwrap().borrow().del_size;
}
impl<T> TreeNode<T> where T: Copy + Ord + Default {
pub fn new(val: T) -> Node<T> {
Some(Rc::new(RefCell::new(TreeNode { val, left: None, right: None, size1: 1, size2: 1, del_size: 1, cnt: 1 })))
}
pub fn update(&mut self) {
self.size1 = get_size1(&self.left) + get_size1(&self.right) + 1;
self.size2 = get_size2(&self.left) + get_size2(&self.right) + self.cnt;
self.del_size = get_del_size(&self.left) + get_del_size(&self.right);
if self.cnt > 0 {
self.del_size += 1;
}
}
}
fn is_need_rebuild<T>(node: &Node<T>) -> bool where T: Copy + Ord + Default {
let s = node.as_ref().unwrap().borrow();
s.cnt > 0 && (s.size1 * 3 <= get_size1(&s.left).max(get_size1(&s.right)) * 4 ||
3 * s.size1 >= s.del_size * 4)
}
fn get_mid<T>(node: Node<T>) -> Vec<Node<T>> where T: Copy + Ord + Default {
let mut ans: Vec<Node<T>> = Vec::new();
if let Some(t) = node {
ans.append(&mut get_mid(t.borrow_mut().left.take()));
if t.borrow().cnt > 0 {
ans.push(Some(t.clone()));
}
ans.append(&mut get_mid(t.borrow_mut().right.take()));
}
ans
}
fn build<T>(l: usize, r: usize, NODES: &mut Vec<Node<T>>) -> Node<T> where T: Ord + Copy + Default {
if l == r {
return None;
}
let mid = (l + r) >> 1;
let mut root = NODES[mid].clone();
root.as_mut().unwrap().borrow_mut().left = build(l, mid, NODES);
root.as_mut().unwrap().borrow_mut().right = build(mid + 1, r, NODES);
root.as_mut().unwrap().borrow_mut().update();
root
}
fn rebuild<T>(node: Node<T>) -> Node<T> where T: Copy + Ord + Default {
let mut ans = get_mid(node);
let l = 0_usize;
let r = ans.len();
build(l, r, &mut ans)
}
struct ScapegoatTree<T> where T: Copy + Ord + Default {
root: Node<T>,
}
fn insert<T>(node: Node<T>, val: T) -> Node<T> where T: Copy + Ord + Default {
if let Some(t) = node {
let m = t.borrow().val;
match m.cmp(&val) {
std::cmp::Ordering::Equal => t.borrow_mut().cnt += 1,
std::cmp::Ordering::Less => {
let r = t.borrow_mut().right.take();
t.borrow_mut().right = insert(r, val)
}
std::cmp::Ordering::Greater => {
let l = t.borrow_mut().left.take();
t.borrow_mut().left = insert(l, val)
}
}
t.borrow_mut().update();
let ans = Some(t);
if is_need_rebuild(&ans) {
return rebuild(ans);
}
ans
} else {
TreeNode::new(val)
}
}
fn remove<T>(node: Node<T>, val: T) -> Node<T> where T: Copy + Ord + Default {
if let Some(t) = node {
let m = t.borrow().val;
match m.cmp(&val) {
std::cmp::Ordering::Equal => if t.borrow().cnt > 0 {
t.borrow_mut().cnt -= 1;
},
std::cmp::Ordering::Less => {
let r = t.borrow_mut().right.take();
t.borrow_mut().right = remove(r, val)
}
std::cmp::Ordering::Greater => {
let l = t.borrow_mut().left.take();
t.borrow_mut().left = remove(l, val)
}
}
t.borrow_mut().update();
let ans = Some(t);
if is_need_rebuild(&ans) {
return rebuild(ans);
}
ans
} else {
None
}
}
fn upper<T>(node: &Node<T>, val: T) -> usize where T: Copy + Ord + Default {
if let Some(t) = node {
let v = t.borrow().val;
let c = t.borrow().cnt;
let s = get_size2(&t.borrow().left);
if v == val && c > 0 {
s + 1 + c
} else if v > val {
return upper(&t.borrow().left, val);
} else {
return upper(&t.borrow().right, val) + c + s;
}
} else {
1_usize
}
}
fn lower<T>(node: &Node<T>, val: T) -> usize where T: Copy + Ord + Default {
if let Some(t) = node {
let v = t.borrow().val;
let c = t.borrow().cnt;
let s = get_size2(&t.borrow().left);
if v == val && c > 0 {
s
} else if v < val {
return lower(&t.borrow().right, val) + c + s;
} else {
return lower(&t.borrow().left, val);
}
} else {
0_usize
}
}
fn at<T>(node: &Node<T>, k: usize) -> T where T: Ord + Copy + Default {
if let Some(t) = node {
let s = get_size2(&t.borrow().left);
let c = t.borrow().cnt;
return if k <= s {
at(&t.borrow().left, k)
} else if k <= s + c {
t.borrow().val
} else {
at(&t.borrow().right, k - s - c)
};
} else {
T::default()
}
}
impl<T> ScapegoatTree<T> where T: Copy + Ord + Default {
pub fn new() -> Self {
Self { root: None }
}
pub fn add(&mut self, val: T) {
self.root = insert(self.root.take(), val);
}
pub fn del(&mut self, val: T) {
self.root = remove(self.root.take(), val);
}
pub fn count(&self, val: T) -> usize {
lower(&self.root, val)
}
pub fn query_kth(&self, val: T) -> usize {
self.count(val) + 1
}
pub fn kth(&self, k: usize) -> T {
at(&self.root, k)
}
pub fn pre(&self, val: T) -> T {
at(&self.root, lower(&self.root, val))
}
pub fn nxt(&self, val: T) -> T {
at(&self.root, upper(&self.root, val))
}
}
impl Solution {
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![];
let mut seg = ScapegoatTree::new();
let k = k as usize;
for i in 0..n {
seg.add(nums[i] as i64);
if i >= k - 1 {
ans.push(seg.kth(k) as i32);
seg.del(nums[i + 1 - k] as i64);
}
}
return ans;
}
}板子题
关于树套树:
树套树
树套树算是平衡树一个广泛的应用之一,一般线段树维护区间,每个区间动态开点一棵其他树，外层套树状数组也可以.内层比较简单的就是平衡树了.＊＊＊树码量也比较小,也可以使用＊＊＊树
这题比较难以AC,卡的比较死,我写的几版AC代码仅供参考
C++与旋转Treap
C++
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
template<typename T, T N>
T ModInt(T value) { return (value % N + N) % N; }
#define mod(m, n) ModInt<int,n>(m);
struct Node {
ll val;
Node *child[2];
int rank;
ll size;
ll cnt;
Node(ll val) : val(val), size(1), cnt(1) {
rank = rand();
child[0] = child[1] = nullptr;
}
void update() {
size = cnt;
if (child[0] != nullptr)size += child[0]->size;
if (child[1] != nullptr)size += child[1]->size;
}
};
enum Rota {
L = 1, R = 0
};
struct RotateTreap {
Node *root;
RotateTreap() {
root = nullptr;
}
void insert(ll v) {
root = add(root, v);
}
static Node *rota(Node *node, Rota t) {
auto new_root = node->child[t];
node->child[t] = new_root->child[t ^ 1];
new_root->child[t ^ 1] = node;
node->update();
new_root->update();
return new_root;
}
Node *add(Node *node, ll val) {
if (node == nullptr)return new Node(val);
if (node->val > val) {
node->child[0] = add(node->child[0], val);
if (node->child[0]->rank < node->rank)node = rota(node, Rota::R);
} else if (node->val < val) {
node->child[1] = add(node->child[1], val);
if (node->child[1]->rank < node->rank)node = rota(node, Rota::L);
} else {
node->size++;
node->cnt++;
}
node->update();
return node;
}
void remove(ll val) {
root = del(root, val);
}
Node *del(Node *node, ll val) {
if (node == nullptr)return nullptr;
if (node->val > val) {
node->child[0] = del(node->child[0], val);
} else if (node->val < val) {
node->child[1] = del(node->child[1], val);
} else {
if (node->cnt > 1) {
node->cnt--;
node->size--;
return node;
}
int state = 0;
if (node->child[0] != nullptr)state |= 1;
if (node->child[1] != nullptr)state |= 1 << 1;
if (state == 0)return nullptr;
else if (state == 1)return node->child[0];
else if (state == 2)return node->child[1];
else {
auto t = node->child[0]->rank < node->child[1]->rank ? Rota::R : Rota::L;
node = rota(node, t);
node->child[t ^ 1] = del(node->child[t ^ 1], val);
}
}
node->update();
return node;
}
ll query_kth(ll val) {
return q_kth(root, val);
}
ll q_kth(Node *node, ll val) {
if(node== nullptr)return 0;
ll size = node->child[0] == nullptr ? 0 : node->child[0]->size;
if (val == node->val)return size;
else if (val < node->val) {
return q_kth(node->child[0], val);
} else {
return q_kth(node->child[1], val) + node->cnt + size;
}
}
ll kth_val(ll k) {
return k_val(root, k);
}
ll k_val(Node *node, ll k) {
if (node == nullptr)return -1;
auto size = node->child[0] == nullptr ? 0 : node->child[0]->size;
if (k <= size)return k_val(node->child[0], k);
else if (k <= size + node->cnt)return node->val;
else return k_val(node->child[1], k - node->cnt - size);
}
ll pre(ll v) {
return pre_ans(root, v);
}
ll pre_ans(Node *node, ll v) {
ll ans = -2147483647;
while (node != nullptr) {
if (node->val < v) {
ans = node->val;
node = node->child[1];
} else node = node->child[0];
}
return ans;
}
ll nxt(ll v) {
return nxt_ans(root, v);
}
ll nxt_ans(Node *node, ll v) {
ll ans = 2147483647;
while (node != nullptr) {
if (node->val > v) {
ans = node->val;
node = node->child[0];
} else node = node->child[1];
}
return ans;
}
};
struct Node2 {
Node2 *left;
Node2 *right;
RotateTreap *root;
int l, r, mid;
Node2(int l, int r) : l(l), r(r) {
mid = (l + r) >> 1;
left = right = nullptr;
root = new RotateTreap();
}
};
void push_down(Node2 *node) {
if (node->left == nullptr)node->left = new Node2(node->l, node->mid);
if (node->right == nullptr)node->right = new Node2(node->mid + 1, node->r);
}
struct Seg {
Node2 *root;
int *b;
Seg(int *a, int n) {
auto build = [&](auto d, Node2 *node) -> void {
push_down(node);
for (int i = node->l; i <= node->r; i++)node->root->insert(a[i]);
if (node->l == node->r) {
return;
}
d(d, node->left);
d(d, node->right);
};
root = new Node2(0, n - 1);
build(build, root);
b = a;
}
void update(int k, int val) {
u(b[k], k, val, root);
b[k] = val;
}
void u(int old, int x, int val, Node2 *node) {
node->root->remove(old);
node->root->insert(val);
if (node->l == x && node->r == x) {
return;
}
if (x <= node->mid)u(old, x, val, node->left);
else u(old, x, val, node->right);
}
ll query(int l, int r, int val) {
return q(l, r, val, root) + 1;
}
ll q(int l, int r, int val, Node2 *node) {
if (l <= node->l && node->r <= r) return node->root->query_kth(val);
ll ans = 0;
if (l <= node->mid)ans += q(l, r, val, node->left);
if (r > node->mid) ans += q(l, r, val, node->right);
return ans;
}
ll kth(int l, int r, int k) {
ll left = 0;
ll right = 1e8;
while (left < right) {
auto mid = (right + left + 1) >> 1;
if (query(l, r, (int) mid) <= k)left = mid;
else right = mid - 1;
}
return left;
}
ll pre(int l, int r, int val) {
return pre_ans(l, r, val, root);
}
ll pre_ans(int l, int r, int val, Node2 *node) {
if (l <= node->l && node->r <= r)return node->root->pre(val);
ll ans = -2147483647;
if (l <= node->mid)ans = max(ans, pre_ans(l, r, val, node->left));
if (r > node->mid)ans = max(ans, pre_ans(l, r, val, node->right));
return ans;
}
ll nxt(int l, int r, int val) {
return nxt_ans(l, r, val, root);
}
ll nxt_ans(int l, int r, int val, Node2 *node) {
if (l <= node->l && node->r <= r)return node->root->nxt(val);
ll ans = 2147483647;
if (l <= node->mid)ans = min(ans, nxt_ans(l, r, val, node->left));
if (r > node->mid)ans = min(ans, nxt_ans(l, r, val, node->right));
return ans;
}
};
void solve() {
int n, m;
cin >> n >> m;
int a[n];
for (int i = 0; i < n; i++)cin >> a[i];
auto tree = new Seg(a, n);
while (m--) {
int t;
cin >> t;
if (t == 1) {
int l, r, val;
cin >> l >> r >> val;
l--, r--;
cout << tree->query(l, r, val) << endl;
} else if (t == 2) {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
cout << tree->kth(l, r, k) << endl;
} else if (t == 3) {
int pos, k;
cin >> pos >> k;
pos--;
tree->update(pos, k);
} else if (t == 4) {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
cout << tree->pre(l, r, k) << endl;
} else {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
cout << tree->nxt(l, r, k) << endl;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//------------------------------------------------------
int t = 1;
// cin >> t;
while (t--)solve();
}Go与旋转Treap
Go
package main
import (
"bufio"
"fmt"
"io"
"math/rand"
"os"
"runtime/debug"
)
type Node struct {
child [2]*Node
val int
cnt int
rank int
size int
}
func NewNode(val int) *Node {
return &Node{child: [2]*Node{nil, nil}, val: val, cnt: 1, rank: rand.Intn(int(1e9)), size: 1}
}
func (t *Node) Update() {
t.size = t.cnt
if t.child[0] != nil {
t.size += t.child[0].size
}
if t.child[1] != nil {
t.size += t.child[1].size
}
}
type RotateTreap struct {
root *Node
L int
R int
}
func NewRotateTreap() *RotateTreap {
return &RotateTreap{root: nil, L: 1, R: 0}
}
func rota(node *Node, i int) *Node {
newRoot := node.child[i]
node.child[i] = newRoot.child[i^1]
newRoot.child[i^1] = node
node.Update()
newRoot.Update()
return newRoot
}
func (node *RotateTreap) insert(x int) {
var add func(node *Node) *Node
add = func(cur *Node) *Node {
if cur == nil {
return NewNode(x)
}
if cur.val > x {
cur.child[0] = add(cur.child[0])
if cur.child[0].rank < cur.rank {
cur = rota(cur, node.R)
}
} else if cur.val < x {
cur.child[1] = add(cur.child[1])
if cur.child[1].rank < cur.rank {
cur = rota(cur, node.L)
}
} else {
cur.cnt++
cur.size++
}
cur.Update()
return cur
}
node.root = add(node.root)
}
func (node *RotateTreap) delete(x int) {
var remove func(*Node) *Node
remove = func(cur *Node) *Node {
if cur == nil {
return nil
}
if cur.val > x {
cur.child[0] = remove(cur.child[0])
} else if cur.val < x {
cur.child[1] = remove(cur.child[1])
} else {
if cur.cnt > 1 {
cur.cnt--
cur.size--
return cur
}
state := 0
if cur.child[0] != nil {
state |= 1
}
if cur.child[1] != nil {
state |= 1 << 1
}
switch state {
case 0:
return nil
case 1:
return cur.child[0]
case 2:
return cur.child[1]
default:
var t = 0
if cur.child[0].rank < cur.child[1].rank {
t = node.R
} else {
t = node.L
}
cur = rota(cur, t)
cur.child[t^1] = remove(cur.child[t^1])
}
}
cur.Update()
return cur
}
node.root = remove(node.root)
}
func (node *RotateTreap) queryKth(x int) int {
var kth func(*Node) int
kth = func(cur *Node) int {
if cur == nil {
return 0
}
size := 0
if cur.child[0] != nil {
size = cur.child[0].size
}
if cur.val > x {
return kth(cur.child[0])
} else if cur.val == x {
return size
} else {
return kth(cur.child[1]) + size + cur.cnt
}
}
return kth(node.root)
}
func (node *RotateTreap) kthValue(k int) int {
var kth func(*Node, int) int
kth = func(cur *Node, x int) int {
if cur == nil {
return -1
}
size := 0
if cur.child[0] != nil {
size = cur.child[0].size
}
if size >= x {
return kth(cur.child[0], x)
} else if x <= size+cur.cnt {
return cur.val
} else {
return kth(cur.child[1], x-cur.cnt-size)
}
}
return kth(node.root, k)
}
func (node *RotateTreap) pre(x int) int {
var ans = func(cur *Node) int {
var res = -2147483647
for cur != nil {
if cur.val < x {
res = cur.val
cur = cur.child[1]
} else {
cur = cur.child[0]
}
}
return res
}
return ans(node.root)
}
func (node *RotateTreap) nxt(x int) int {
var ans = func(cur *Node) int {
var res = 2147483647
for cur != nil {
if cur.val > x {
res = cur.val
cur = cur.child[0]
} else {
cur = cur.child[1]
}
}
return res
}
return ans(node.root)
}
type TreeNode struct {
left, right *TreeNode
l, r, mid int
root *RotateTreap
}
func NewTreeNode(l int, r int) *TreeNode {
return &TreeNode{l: l, r: r, root: NewRotateTreap(), mid: (l + r) >> 1, left: nil, right: nil}
}
func pushDown(node *TreeNode) {
if node.left == nil {
node.left = NewTreeNode(node.l, node.mid)
}
if node.right == nil {
node.right = NewTreeNode(node.mid+1, node.r)
}
}
type Seg struct {
root *TreeNode
old []int
}
func NewSeg(a []int) *Seg {
var build func(node *TreeNode)
build = func(node *TreeNode) {
pushDown(node)
for i := node.l; i <= node.r; i++ {
node.root.insert(a[i])
}
if node.l == node.r {
return
}
build(node.left)
build(node.right)
}
root := NewTreeNode(0, len(a)-1)
build(root)
return &Seg{root: root, old: a}
}
func (node *Seg) Update(pos int, x int) {
var o = node.old[pos]
var modify func(curr *TreeNode)
modify = func(curr *TreeNode) {
curr.root.delete(o)
curr.root.insert(x)
if curr.l == pos && pos == curr.r {
return
}
if pos <= curr.mid {
modify(curr.left)
} else {
modify(curr.right)
}
}
modify(node.root)
node.old[pos] = x
}
func (node *Seg) Kth(l int, r int, val int) int {
var ans func(curr *TreeNode) int
ans = func(curr *TreeNode) int {
if l <= curr.l && curr.r <= r {
return curr.root.queryKth(val)
}
var res = 0
if l <= curr.mid {
res += ans(curr.left)
}
if r > curr.mid {
res += ans(curr.right)
}
return res
}
return ans(node.root) + 1
}
func (node *Seg) Query(l int, r int, k int) int {
left := 0
right := int(1e8)
for left < right {
mid := (left + right + 1) >> 1
if node.Kth(l, r, mid) <= k {
left = mid
} else {
right = mid - 1
}
}
return left
}
func (node *Seg) Pre(l int, r int, val int) int {
var p func(curr *TreeNode) int
p = func(curr *TreeNode) int {
if l <= curr.l && curr.r <= r {
return curr.root.pre(val)
}
ans := -2147483647
if l <= curr.mid {
ans = max(ans, p(curr.left))
}
if r > curr.mid {
ans = max(ans, p(curr.right))
}
return ans
}
return p(node.root)
}
func (node *Seg) Nxt(l int, r int, val int) int {
var n func(curr *TreeNode) int
n = func(curr *TreeNode) int {
if l <= curr.l && curr.r <= r {
return curr.root.nxt(val)
}
ans := 2147483647
if l <= curr.mid {
ans = min(ans, n(curr.left))
}
if r > curr.mid {
ans = min(ans, n(curr.right))
}
return ans
}
return n(node.root)
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func run(_r io.Reader, _w io.Writer) {
in := bufio.NewScanner(_r)
in.Split(bufio.ScanWords)
out := bufio.NewWriter(_w)
defer out.Flush()
read := func() (x int) {
in.Scan()
tmp := in.Bytes()
if tmp[0] == '-' {
for _, b := range tmp[1:] {
x = x*10 + int(b&15)
}
return -x
} else {
for _, b := range in.Bytes() {
x = x*10 + int(b&15)
}
}
return
}
var n, m int
n = read()
m = read()
var a = make([]int, n)
for i := range a {
a[i] = read()
}
seg := NewSeg(a)
for m > 0 {
m--
op := read()
switch op {
case 1:
var le, re, val int
le = read()
re = read()
val = read()
le--
re--
fmt.Fprintln(out, seg.Kth(le, re, val))
case 2:
var le, re, k int
le = read()
re = read()
k = read()
le--
re--
fmt.Fprintln(out, seg.Query(le, re, k))
case 3:
var pos, val int
pos = read()
val = read()
pos--
seg.Update(pos, val)
case 4:
var le, re, val int
le = read()
re = read()
val = read()
le--
re--
fmt.Fprintln(out, seg.Pre(le, re, val))
case 5:
var le, re, val int
le = read()
re = read()
val = read()
le--
re--
fmt.Fprintln(out, seg.Nxt(le, re, val))
}
}
}
func main() {
debug.SetGCPercent (-1)
run(os.Stdin, os.Stdout)
}Rust与红黑树(红黑树为找的板子)
Rust
#![allow(unused_variables)]
#![warn(clippy::large_stack_arrays)]
#![warn(unused_macros)]
use std::cell::RefCell;
use std::cmp::Ordering;
use crate::raw::in_out;
use crate::scanner::Scanner;
use std::io::{BufRead, Write};
use std::ops::{Add, AddAssign};
use std::rc::Rc;
use crate::random::random;
//----------------------------递归闭包---------------------------
// struct Func<'a, A, F>(&'a dyn Fn(Func<'a, A, F>, A) -> F);
//
// impl<'a, A, F> Clone for Func<'a, A, F> {
// fn clone(&self) -> Self {
// Self(self.0)
// }
// }
//
// impl<'a, A, F> Copy for Func<'a, A, F> {}
//
// impl<'a, A, F> Func<'a, A, F> {
// fn call(&self, f: Func<'a, A, F>, x: A) -> F {
// (self.0)(f, x)
// }
// }
//
// fn y<A, R>(g: impl Fn(&dyn Fn(A) -> R, A) -> R) -> impl Fn(A) -> R {
// move |x| (|f: Func<A, R>, x| f.call(f, x))(Func(&|f, x| g(&|x| f.call(f, x), x)), x)
// }
//Y组合子使用示例:(多参采用元组传参)
// let dfs = | f: & dyn Fn((usize, i32,bool)) -> bool, (i,sum,s): (usize,i32,bool) | -> bool{
// if i == n {
// return sum == 0 & & s;
// }
// return f((i + 1, sum + a[i], true)) | | f((i + 1, sum, s)) | |
// f((i + 1, sum - a[i], true));
// };
//----------------------------递归闭包---------------------------
//----------------------------常用函数----------------------------
#[allow(dead_code)]
// #[inline]
fn prefix_array<T>(a: &Vec<T>, start: T) -> Vec<T> where T: Add<Output=T> + Copy + AddAssign {
(0..=a.len()).scan(start, |x, y| if y == 0 { Some(start) } else {
*x += a[y - 1];
Some(*x)
}).collect::<Vec<T>>()
}
#[allow(dead_code)]
// #[inline]
fn suffix_array<T>(a: &Vec<T>, end: T) -> Vec<T> where T: Add<Output=T> + Copy + AddAssign {
let mut tmp = (0..=a.len()).rev().scan(end, |x, y| if y == a.len() { Some(end) } else {
*x += a[y];
Some(*x)
}).collect::<Vec<T>>();
tmp.reverse();
tmp
}
pub mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN { res.mt[i] = F.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62)).wrapping_add(i as u64); }
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 { self.gen() % n }
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 { f + self.next(t - f + 1) }
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() { RAND = Some(Random::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF) as u64)); }
RAND.as_mut().unwrap()
}
}
pub trait Shuffle { fn shuffle(&mut self); }
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}
//----------------------------常用函数----------------------------
//----------------------------Test----------------------------
struct NodeInner {
val: i64,
size: usize,
red: bool,
left: Node,
right: Node,
}
struct Node(*mut NodeInner);
impl Node {
fn none() -> Self {
Self(std::ptr::null_mut())
}
#[inline]
fn is_none(&self) -> bool {
self.0.is_null()
}
#[inline]
fn exists(&self) -> bool {
!self.0.is_null()
}
#[inline]
fn red(&self) -> bool {
if self.0.is_null() {
false
} else {
unsafe { (*self.0).red }
}
}
#[inline]
fn set_red(&mut self, red: bool) {
if self.exists() {
unsafe {
(*self.0).red = red;
}
}
}
#[inline]
fn val(&self) -> i64 {
unsafe { (*self.0).val }
}
#[inline]
fn set_val(&mut self, val: i64) {
unsafe {
(*self.0).val = val;
}
}
#[inline]
fn size(&self) -> usize {
if self.is_none() {
0
} else {
unsafe { (*self.0).size }
}
}
#[inline]
fn left(&self) -> &Node {
unsafe { &(*self.0).left }
}
#[inline]
fn right(&self) -> &Node {
unsafe { &(*self.0).right }
}
#[inline]
fn left_mut(&mut self) -> &mut Node {
unsafe { &mut (*self.0).left }
}
#[inline]
fn right_mut(&mut self) -> &mut Node {
unsafe { &mut (*self.0).right }
}
#[inline]
fn fix_size(&mut self) {
if self.exists() {
let node = unsafe { &mut *self.0 };
node.size = 1 + node.left.size() + node.right.size();
}
}
#[inline]
fn clear(&mut self) {
let old = self.0;
self.0 = std::ptr::null_mut();
unsafe {
Box::from_raw(old);
}
}
fn rotate_left(&mut self) {
unsafe {
let temp = (*self.0).right.0;
(*self.0).right.0 = (*temp).left.0;
(*temp).red = (*self.0).red;
(*self.0).red = true;
self.fix_size();
(*temp).left.0 = self.0;
self.0 = temp;
self.fix_size();
}
}
fn rotate_right(&mut self) {
unsafe {
let temp = (*self.0).left.0;
(*self.0).left.0 = (*temp).right.0;
(*temp).red = (*self.0).red;
(*self.0).red = true;
self.fix_size();
(*temp).right.0 = self.0;
self.0 = temp;
self.fix_size();
}
}
fn flip_color(&mut self) {
self.set_red(!self.red());
let left = self.left_mut();
left.set_red(!left.red());
let right = self.right_mut();
right.set_red(!right.red());
}
fn fix_up(&mut self) {
if self.right().red() {
self.rotate_left();
}
if self.left().red() && self.left().left().red() {
self.rotate_right();
}
if self.left().red() && self.right().red() {
self.flip_color();
}
}
fn insert_internal(&mut self, val: i64) {
if self.is_none() {
self.0 = Box::into_raw(Box::new(NodeInner {
val,
size: 1,
red: true,
left: Self::none(),
right: Self::none(),
}));
return;
}
if val < self.val() {
self.left_mut().insert_internal(val);
} else {
self.right_mut().insert_internal(val);
}
self.fix_size();
self.fix_up();
}
fn insert(&mut self, val: i64) {
self.insert_internal(val);
self.set_red(false);
}
fn move_red_left(&mut self) {
self.flip_color();
if self.right().exists() && self.right().left().red() {
self.right_mut().rotate_right();
self.rotate_left();
self.flip_color();
}
}
fn move_red_right(&mut self) {
self.flip_color();
if self.left().exists() && self.left().left().red() {
self.rotate_right();
self.flip_color();
self.right_mut().rotate_left();
}
}
fn delete_min(&mut self) -> i64 {
if self.left().is_none() {
let val = self.val();
self.clear();
return val;
}
if !self.left().red() && !self.left().left().red() {
self.move_red_left();
}
let ret = self.left_mut().delete_min();
self.fix_size();
self.fix_up();
ret
}
fn delete_internal(&mut self, val: i64) {
if val < self.val() {
if !self.left().red() && self.left().exists() && !self.left().left().red() {
self.move_red_left();
}
self.left_mut().delete_internal(val);
self.fix_size();
} else {
if self.left().red() {
self.rotate_right();
}
if val == self.val() && self.right().is_none() {
self.clear();
return;
}
if !self.right().red() && self.right().exists() && !self.right().left().red() {
self.move_red_right();
}
if val == self.val() {
let min = self.right_mut().delete_min();
self.set_val(min);
} else {
self.right_mut().delete_internal(val);
}
self.fix_size();
}
self.fix_up();
}
fn delete(&mut self, val: i64) {
self.delete_internal(val);
self.set_red(false);
}
fn rank(&self, val: i64) -> usize {
let mut node = self;
let mut ret = 0_usize;
while node.exists() {
if val <= node.val() {
node = node.left();
} else {
ret += node.left().size() + 1;
node = node.right();
}
}
ret
}
fn get(&self, mut rank: usize) -> i64 {
let mut node = self;
while node.exists() {
let left_size = node.left().size() + 1;
match rank.cmp(&left_size) {
Ordering::Less => node = node.left(),
Ordering::Equal => return node.val(),
Ordering::Greater => {
rank -= left_size;
node = node.right();
}
}
}
unreachable!()
}
fn pred(&self, val: i64) -> i64 {
let mut node = self;
let mut ret = Some(-2147483647);
while node.exists() {
match val.cmp(&node.val()) {
Ordering::Less => node = node.left(),
Ordering::Greater => {
ret = Some(node.val());
node = node.right();
}
Ordering::Equal => {
node = node.left();
while node.exists() {
node = if node.val() < val {
ret = Some(node.val());
node.right()
} else {
node.left()
}
}
}
}
}
ret.unwrap()
}
fn succ(&self, val: i64) -> i64 {
let mut node = self;
let mut ret = Some(2147483647);
while node.exists() {
match val.cmp(&node.val()) {
Ordering::Less => {
ret = Some(node.val());
node = node.left();
}
Ordering::Greater => node = node.right(),
Ordering::Equal => {
node = node.right();
while node.exists() {
node = if node.val() > val {
ret = Some(node.val());
node.left()
} else {
node.right()
}
}
}
}
}
ret.unwrap()
}
}
impl Drop for Node {
fn drop(&mut self) {
if self.exists() {
unsafe {
Box::from_raw(self.0);
}
}
}
}
fn read_one_number() -> i32 {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
s.trim_end().parse().unwrap()
}
fn read_two_numbers() -> (i32, i32) {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let s = s.trim_end();
let pos = s.find(' ').unwrap();
((&s[..pos]).parse().unwrap(), (&s[pos + 1..]).parse().unwrap())
}
type SegNode = Option<Rc<RefCell<Seg_Node>>>;
struct Seg_Node {
l: usize,
r: usize,
mid: usize,
val: Node,
left: SegNode,
right: SegNode,
}
impl Seg_Node {
pub fn new(l: usize, r: usize) -> SegNode {
Some(Rc::new(RefCell::new(Seg_Node { l, r, mid: (l + r) >> 1, val: Node::none(), left: None, right: None })))
}
}
fn push_down(node: &mut SegNode) {
let mut t = node.as_ref().unwrap().borrow_mut();
let l = t.l;
let mid = t.mid;
let r = t.r;
if t.left.is_none() {
t.left = Seg_Node::new(l, mid);
}
if t.right.is_none() {
t.right = Seg_Node::new(mid + 1, r);
}
}
struct SegTree {
root: SegNode,
old: Vec<i64>,
}
fn init(node: &mut SegNode, old: &Vec<i64>) {
let l = node.as_ref().unwrap().borrow().l;
let r = node.as_ref().unwrap().borrow().r;
for i in l..=r {
node.as_mut().unwrap().borrow_mut().val.insert(old[i]);
}
if l == r {
return;
}
push_down(node);
init(&mut node.as_mut().unwrap().borrow_mut().left, old);
init(&mut node.as_mut().unwrap().borrow_mut().right, old);
}
fn seg_query(l: usize, r: usize, node: &SegNode, val: i64) -> usize {
if let Some(t) = node {
if l <= t.borrow().l && t.borrow().r <= r {
return t.borrow().val.rank(val);
}
let mut ans = 0_usize;
if l <= t.borrow().mid {
ans += seg_query(l, r, &t.borrow().left, val);
}
if r > t.borrow().mid {
ans += seg_query(l, r, &t.borrow().right, val);
}
ans
} else {
0
}
}
fn seg_update(x: usize, old: i64, new_val: i64, node: &mut SegNode) {
let l = node.as_ref().unwrap().borrow().l;
let r = node.as_ref().unwrap().borrow().r;
let mid = node.as_ref().unwrap().borrow().mid;
node.as_mut().unwrap().borrow_mut().val.delete(old);
node.as_mut().unwrap().borrow_mut().val.insert(new_val);
if l == x && x == r {
return;
}
if x <= mid {
seg_update(x, old, new_val, &mut node.as_ref().unwrap().borrow_mut().left);
} else {
seg_update(x, old, new_val, &mut node.as_ref().unwrap().borrow_mut().right);
}
}
fn seg_pre(l: usize, r: usize, node: &SegNode, val: i64) -> i64 {
let ll = node.as_ref().unwrap().borrow().l;
let rr = node.as_ref().unwrap().borrow().r;
let mid = node.as_ref().unwrap().borrow().mid;
if l <= ll && rr <= r {
return node.as_ref().unwrap().borrow().val.pred(val);
}
let mut ans = -2147483647_i64;
if l <= mid {
ans = ans.max(seg_pre(l, r, &node.as_ref().unwrap().borrow().left, val));
}
if r > mid {
ans = ans.max(seg_pre(l, r, &node.as_ref().unwrap().borrow().right, val));
}
ans
}
fn seg_nxt(l: usize, r: usize, node: &SegNode, val: i64) -> i64 {
let ll = node.as_ref().unwrap().borrow().l;
let rr = node.as_ref().unwrap().borrow().r;
let mid = node.as_ref().unwrap().borrow().mid;
if l <= ll && rr <= r {
return node.as_ref().unwrap().borrow().val.succ(val);
}
let mut ans = 2147483647_i64;
if l <= mid {
ans = ans.min(seg_nxt(l, r, &node.as_ref().unwrap().borrow().left, val));
}
if r > mid {
ans = ans.min(seg_nxt(l, r, &node.as_ref().unwrap().borrow().right, val));
}
ans
}
impl SegTree {
pub fn new(old: Vec<i64>) -> Self {
let n = old.len();
let mut root = Seg_Node::new(0, n - 1);
init(&mut root, &old);
Self { root, old }
}
pub fn query(&self, l: usize, r: usize, val: i64) -> usize {
seg_query(l, r, &self.root, val) + 1
}
pub fn update(&mut self, pos: usize, new_val: i64) {
let old = self.old[pos];
seg_update(pos, old, new_val, &mut self.root);
self.old[pos] = new_val;
}
pub fn kth(&self, l: usize, r: usize, k: usize) -> i64 {
let mut left = 0_i64;
let mut right = 100000000;
while left < right {
let mid = (left + right + 1) >> 1;
if self.query(l, r, mid) <= k {
left = mid;
} else {
right = mid - 1;
}
}
left
}
pub fn pre(&self, l: usize, r: usize, val: i64) -> i64 {
seg_pre(l, r, &self.root, val)
}
pub fn nxt(&self, l: usize, r: usize, val: i64) -> i64 {
seg_nxt(l, r, &self.root, val)
}
}
//----------------------------Test----------------------------
pub fn solve<R: BufRead, W: Write>(mut scanner: Scanner<R>, out: &mut W) {
//---------------------------------------------常用宏---------------------------------------------
#[allow(unused_macros)]
macro_rules! puts {($($format:tt)*) => (let _ = writeln!(out,$($format)*););}
#[allow(unused_macros)]
macro_rules! read_type_usize {() => {scanner.next::<usize>()};}
#[allow(unused_macros)]
macro_rules! read_type_i32 {() => {scanner.next::<i32>()};}
#[allow(unused_macros)]
macro_rules! read_type_i64 {() => {scanner.next::<i64>()};}
#[allow(unused_macros)]
macro_rules! read_type_i128 {() => {scanner.next::<i128>()};}
#[allow(unused_macros)]
macro_rules! read_type_isize {() => {scanner.next::<isize>()};}
#[allow(unused_macros)]
macro_rules! read_string_u8 {() => {scanner.next::<String>().into_bytes()};}
#[allow(unused_macros)]
macro_rules! read_usize {($n:expr) => {(0..$n).map(|_|scanner.next::<usize>()).collect::<Vec<usize>>()};}
#[allow(unused_macros)]
macro_rules! read_i32 {($n:expr) => {(0..$n).map(|_|scanner.next::<i32>()).collect::<Vec<i32>>()};}
#[allow(unused_macros)]
macro_rules! read_i64 {($n:expr) => {(0..$n).map(|_|scanner.next::<i64>()).collect::<Vec<i64>>()};}
#[allow(unused_macros)]
macro_rules! read_i128 {($n:expr) => {(0..$n).map(|_|scanner.next::<i128>()).collect::<Vec<i128>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_usize {($n:expr,$m:expr) => {(0..$n).map(|_|read_usize!($m)).collect::<Vec<Vec<usize>>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_i32 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i32!($m)).collect::<Vec<Vec<i32>>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_i64 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i64!($m)).collect::<Vec<Vec<i64>>>()};}
#[allow(unused_macros)]
macro_rules! count_bit {($n:expr) => {{let(mut ans,mut k)=(0_usize,$n);while k>0{ans+=1;k&=k-1;}ans}};}
#[allow(unused_macros)]
macro_rules! print_all {($A:expr) => {{for &v in &$A{let _ = write!(out, "{} ", v);}puts!();}};}
//-----------------------------------------------------------------------------------------------
let n = read_type_usize!();
let m = read_type_usize!();
let a = read_i64!(n);
let mut s = SegTree::new(a);
for _ in 0..m {
let t = read_type_usize!();
match t {
1 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.query(l,r,val));
}
2 => {
let (l, r, k) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_usize!());
puts!("{}",s.kth(l,r,k));
}
3 => {
let (pos, val) = (read_type_usize!() - 1, read_type_i64!());
s.update(pos, val);
}
4 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.pre(l,r,val));
}
5 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.nxt(l,r,val));
}
_ => {}
}
}
}
//-----------------------------main-------------------------------------
fn main() {
let (stdin, mut stdout) = in_out();
solve(Scanner::new(stdin), &mut stdout);
}
// --------------------------- tools -----------------------------------
mod raw {
use std::fs::File;
use std::io::{BufRead, BufReader, BufWriter, stdin, stdout, Write};
#[cfg(windows)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::windows::prelude::{AsRawHandle, FromRawHandle};
unsafe {
let stdin = File::from_raw_handle(stdin().as_raw_handle());
let stdout = File::from_raw_handle(stdout().as_raw_handle());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
#[cfg(unix)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::unix::prelude::{AsRawFd, FromRawFd};
unsafe {
let stdin = File::from_raw_fd(stdin().as_raw_fd());
let stdout = File::from_raw_fd(stdout().as_raw_fd());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
}
mod scanner {
use std::io::BufRead;
pub struct Scanner<R> {
reader: R,
buf_str: Vec<u8>,
buf_iter: std::str::SplitAsciiWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Self { reader, buf_str: Vec::new(), buf_iter: "".split_ascii_whitespace() }
}
pub fn next<T: std::str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buf_iter.next() {
return token.parse().ok().expect("Failed parse");
}
unsafe { self.buf_str.set_len(0); }
self.reader.read_until(b'\n', &mut self.buf_str).expect("Failed read");
self.buf_iter = unsafe {
let slice = std::str::from_utf8_unchecked(&self.buf_str);
std::mem::transmute(slice.split_ascii_whitespace())
}
}
}
}
}Rust与替罪羊树
替罪羊树常数诡异,调整比例因子为0.78 AC
Rust
#![allow(unused_variables)]
#![warn(clippy::large_stack_arrays)]
#![warn(unused_macros)]
use crate::raw::in_out;
use crate::scanner::Scanner;
use std::io::{BufRead, Write};
use std::ops::{Add, AddAssign};
//----------------------------递归闭包---------------------------
// struct Func<'a, A, F>(&'a dyn Fn(Func<'a, A, F>, A) -> F);
//
// impl<'a, A, F> Clone for Func<'a, A, F> {
// fn clone(&self) -> Self {
// Self(self.0)
// }
// }
//
// impl<'a, A, F> Copy for Func<'a, A, F> {}
//
// impl<'a, A, F> Func<'a, A, F> {
// fn call(&self, f: Func<'a, A, F>, x: A) -> F {
// (self.0)(f, x)
// }
// }
//
// fn y<A, R>(g: impl Fn(&dyn Fn(A) -> R, A) -> R) -> impl Fn(A) -> R {
// move |x| (|f: Func<A, R>, x| f.call(f, x))(Func(&|f, x| g(&|x| f.call(f, x), x)), x)
// }
//Y组合子使用示例:(多参采用元组传参)
// let dfs = | f: & dyn Fn((usize, i32,bool)) -> bool, (i,sum,s): (usize,i32,bool) | -> bool{
// if i == n {
// return sum == 0 & & s;
// }
// return f((i + 1, sum + a[i], true)) | | f((i + 1, sum, s)) | |
// f((i + 1, sum - a[i], true));
// };
//----------------------------递归闭包---------------------------
//----------------------------常用函数----------------------------
#[allow(dead_code)]
#[inline]
fn prefix_array<T>(a: &Vec<T>, start: T) -> Vec<T> where T: Add<Output=T> + Copy + AddAssign {
(0..=a.len()).scan(start, |x, y| if y == 0 { Some(start) } else {
*x += a[y - 1];
Some(*x)
}).collect::<Vec<T>>()
}
#[allow(dead_code)]
#[inline]
fn suffix_array<T>(a: &Vec<T>, end: T) -> Vec<T> where T: Add<Output=T> + Copy + AddAssign {
let mut tmp = (0..=a.len()).rev().scan(end, |x, y| if y == a.len() { Some(end) } else {
*x += a[y];
Some(*x)
}).collect::<Vec<T>>();
tmp.reverse();
tmp
}
pub mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN { res.mt[i] = F.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62)).wrapping_add(i as u64); }
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 { self.gen() % n }
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 { f + self.next(t - f + 1) }
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() { RAND = Some(Random::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF) as u64)); }
RAND.as_mut().unwrap()
}
}
pub trait Shuffle { fn shuffle(&mut self); }
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}
//----------------------------常用函数----------------------------
//----------------------------Test----------------------------
struct Node(*mut TreeNode);
struct TreeNode {
left: Node,
right: Node,
val: i64,
size1: usize,
size2: usize,
del_size: usize,
cnt: usize,
}
#[inline]
fn get_size1(node: &Node) -> usize {
if node.0.is_null() {
return 0;
}
unsafe { (*node.0).size1 }
}
#[inline]
fn get_size2(node: &Node) -> usize {
if node.0.is_null() {
return 0;
}
unsafe { (*node.0).size2 }
}
#[inline]
fn get_del_size(node: &Node) -> usize {
if node.0.is_null() {
return 0;
}
unsafe { (*node.0).del_size }
}
impl Node {
pub unsafe fn none() -> Self {
Self(std::ptr::null_mut())
}
pub unsafe fn new(val: i64) -> Self {
let mut ans = Self::none();
ans.0 = Box::into_raw(Box::new(TreeNode {
left: Self::none(),
right: Self::none(),
val,
size1: 1,
size2: 1,
del_size: 1,
cnt: 1,
}));
ans
}
#[inline]
fn val(&self) -> i64 {
unsafe { (*self.0).val }
}
#[inline]
fn left(&self) -> &Node {
unsafe { &(*self.0).left }
}
#[inline]
fn right(&self) -> &Node {
unsafe { &(*self.0).right }
}
#[inline]
fn left_mut(&mut self) -> &mut Node {
unsafe { &mut (*self.0).left }
}
#[inline]
fn cnt(&self) -> usize {
unsafe { (*self.0).cnt }
}
#[inline]
fn size1(&self) -> usize {
unsafe { (*self.0).size1 }
}
#[inline]
fn size2(&self) -> usize {
unsafe { (*self.0).size2 }
}
#[inline]
fn del_size(&self) -> usize {
unsafe { (*self.0).del_size }
}
#[inline]
fn right_mut(&mut self) -> &mut Node {
unsafe { &mut (*self.0).right }
}
#[inline]
fn clear(&mut self) {
let old = self.0;
self.0 = std::ptr::null_mut();
unsafe {
let _ = Box::from_raw(old);
}
}
#[inline]
pub unsafe fn update(&mut self) {
(*self.0).size1 = get_size1(self.left()) + get_size1(self.right()) + 1;
(*self.0).size2 = get_size2(self.left()) + get_size2(self.right()) + self.cnt();
(*self.0).del_size = get_del_size(self.left()) + get_del_size(self.right());
if self.cnt() > 0 {
(*self.0).del_size += 1;
}
}
#[inline]
pub unsafe fn add(&mut self, val: i64) {
if self.val() == val {
(*self.0).cnt += 1;
} else if self.val() > val {
if self.left().0.is_null() {
(*self.0).left = Node::new(val);
} else {
self.left_mut().add(val);
}
} else if self.right().0.is_null() {
(*self.0).right = Node::new(val);
} else {
self.right_mut().add(val);
}
self.update();
if is_need_rebuild(self) {
let t = rebuild(self);
*self = Node {
..t
}
}
}
#[inline]
pub unsafe fn remove(&mut self, val: i64) {
if self.val() == val {
if self.cnt() > 0 {
(*self.0).cnt -= 1;
}
} else if self.val() > val {
if !self.left().0.is_null() {
self.left_mut().remove(val);
}
} else if !self.right().0.is_null() {
self.right_mut().remove(val);
}
self.update();
if is_need_rebuild(self) {
let t = rebuild(self);
*self = Node {
..t
}
}
}
}
const ALPHA: f64 = 0.78;
#[inline]
unsafe fn is_need_rebuild(node: &Node) -> bool {
node.cnt() > 0 && (node.size1() as f64 * ALPHA <= get_size1(node.left()).max(get_size1(node.right())) as f64 ||
node.size1() as f64 * ALPHA >= node.del_size() as f64)
}
static mut NODES: Vec<(i64, usize, usize, usize, usize)> = Vec::new();
#[inline]
unsafe fn get_mid(node: &mut Node) {
if !node.0.is_null() {
get_mid(node.left_mut());
if node.cnt() > 0 {
NODES.push((node.val(), node.cnt(), node.size1(), node.size2(), node.del_size()));
}
get_mid(node.right_mut());
node.clear();
}
}
#[inline]
unsafe fn build(l: usize, r: usize) -> Node {
if l == r {
return Node::none();
}
let mid = (l + r) >> 1;
let (val, cnt, size1, size2, del_size) = NODES[mid];
let mut root = Node::new(val);
(*root.0).cnt = cnt;
(*root.0).size1 = size1;
(*root.0).size2 = size2;
(*root.0).del_size = del_size;
(*root.0).left = build(l, mid);
(*root.0).right = build(mid + 1, r);
root.update();
root
}
#[inline]
unsafe fn rebuild(node: &mut Node) -> Node {
NODES.clear();
get_mid(node);
let l = 0_usize;
let r = NODES.len();
build(l, r)
}
struct ScapegoatTree {
root: Node,
}
fn upper(node: &Node, val: i64) -> usize {
if !node.0.is_null() {
let v = node.val();
let c = node.cnt();
let s = get_size2(node.left());
if v == val && c > 0 {
s + 1 + c
} else if v > val {
return upper(node.left(), val);
} else {
return upper(node.right(), val) + c + s;
}
} else {
1_usize
}
}
fn lower(node: &Node, val: i64) -> usize {
if !node.0.is_null() {
let v = node.val();
let c = node.cnt();
let s = get_size2(node.left());
if v == val && c > 0 {
s
} else if v < val {
return lower(node.right(), val) + c + s;
} else {
return lower(node.left(), val);
}
} else {
0_usize
}
}
fn at(node: &Node, k: usize) -> i64 {
if !node.0.is_null() {
let s = get_size2(node.left());
let c = node.cnt();
return if k <= s {
at(node.left(), k)
} else if k <= s + c {
node.val()
} else {
at(node.right(), k - s - c)
};
} else {
0
}
}
impl ScapegoatTree {
#[inline]
pub unsafe fn new() -> Self {
Self { root: Node::none() }
}
#[inline]
pub unsafe fn add(&mut self, val: i64) {
if self.root.0.is_null() {
self.root = Node::new(val);
} else {
self.root.add(val);
}
}
#[inline]
pub unsafe fn del(&mut self, val: i64) {
if !self.root.0.is_null() {
self.root.remove(val);
}
}
#[inline]
pub fn count(&self, val: i64) -> usize {
lower(&self.root, val)
}
#[inline]
pub fn query_kth(&self, val: i64) -> usize {
self.count(val) + 1
}
#[inline]
pub fn kth(&self, k: usize) -> i64 {
at(&self.root, k)
}
#[inline]
pub fn pre(&self, val: i64) -> i64 {
let t = lower(&self.root, val);
if t == 0 {
return -2147483647;
}
at(&self.root, t)
}
#[inline]
pub fn nxt(&self, val: i64) -> i64 {
let t = upper(&self.root, val);
if t == self.root.size2() + 1 {
return 2147483647;
}
at(&self.root, t)
}
}
struct SegNode(*mut Seg_Node);
struct Seg_Node {
l: usize,
r: usize,
mid: usize,
val: ScapegoatTree,
left: SegNode,
right: SegNode,
}
impl SegNode {
pub unsafe fn none() -> Self {
Self(std::ptr::null_mut())
}
pub unsafe fn new(l: usize, r: usize) -> Self {
let mut ans = Self::none();
ans.0 = Box::into_raw(Box::new(Seg_Node {
left: Self::none(),
right: Self::none(),
val: ScapegoatTree::new(),
l,
r,
mid: (l + r) >> 1,
}));
ans
}
#[inline]
fn left(&self) -> &SegNode {
unsafe { &(*self.0).left }
}
#[inline]
fn right(&self) -> &SegNode {
unsafe { &(*self.0).right }
}
#[inline]
fn left_mut(&mut self) -> &mut SegNode {
unsafe { &mut (*self.0).left }
}
#[inline]
fn right_mut(&mut self) -> &mut SegNode {
unsafe { &mut (*self.0).right }
}
#[inline]
fn clear(&mut self) {
let old = self.0;
self.0 = std::ptr::null_mut();
unsafe {
let _ = Box::from_raw(old);
}
}
#[inline]
fn l(&self) -> usize {
unsafe { (*self.0).l }
}
#[inline]
fn r(&self) -> usize {
unsafe { (*self.0).r }
}
#[inline]
fn mid(&self) -> usize {
unsafe { (*self.0).mid }
}
}
#[inline]
unsafe fn push_down(node: &mut SegNode) {
if node.left().0.is_null() {
(*node.0).left = SegNode::new(node.l(), node.mid());
}
if node.right().0.is_null() {
(*node.0).right = SegNode::new(node.mid() + 1, node.r());
}
}
struct SegTree {
root: SegNode,
old: Vec<i64>,
}
#[inline]
unsafe fn init(node: &mut SegNode, old: &Vec<i64>) {
let l = node.l();
let r = node.r();
for i in l..=r {
(*node.0).val.add(old[i]);
}
if l == r {
return;
}
push_down(node);
init(node.left_mut(), old);
init(node.right_mut(), old);
}
#[inline]
unsafe fn seg_query(l: usize, r: usize, node: &SegNode, val: i64) -> usize {
if !node.0.is_null() {
if l <= node.l() && node.r() <= r {
return (*node.0).val.count(val);
}
let mut ans = 0_usize;
if l <= node.mid() {
ans += seg_query(l, r, node.left(), val);
}
if r > node.mid() {
ans += seg_query(l, r, node.right(), val);
}
ans
} else {
0
}
}
#[inline]
unsafe fn seg_update(x: usize, old: i64, new_val: i64, node: &mut SegNode) {
let l = node.l();
let r = node.r();
let mid = node.mid();
(*node.0).val.del(old);
(*node.0).val.add(new_val);
if l == x && x == r {
return;
}
if x <= mid {
seg_update(x, old, new_val, node.left_mut());
} else {
seg_update(x, old, new_val, node.right_mut());
}
}
#[inline]
unsafe fn seg_pre(l: usize, r: usize, node: &SegNode, val: i64) -> i64 {
let ll = node.l();
let rr = node.r();
let mid = node.mid();
if l <= ll && rr <= r {
return (*node.0).val.pre(val);
}
let mut ans = -2147483647_i64;
if l <= mid {
ans = ans.max(seg_pre(l, r, node.left(), val));
}
if r > mid {
ans = ans.max(seg_pre(l, r, node.right(), val));
}
ans
}
#[inline]
unsafe fn seg_nxt(l: usize, r: usize, node: &SegNode, val: i64) -> i64 {
let ll = node.l();
let rr = node.r();
let mid = node.mid();
if l <= ll && rr <= r {
return (*node.0).val.nxt(val);
}
let mut ans = 2147483647_i64;
if l <= mid {
ans = ans.min(crate::seg_nxt(l, r, node.left(), val));
}
if r > mid {
ans = ans.min(crate::seg_nxt(l, r, node.right(), val));
}
ans
}
impl SegTree {
pub unsafe fn new(old: Vec<i64>) -> Self {
let n = old.len();
let mut root = SegNode::new(0, n - 1);
init(&mut root, &old);
Self { root, old }
}
#[inline]
pub unsafe fn query(&self, l: usize, r: usize, val: i64) -> usize {
seg_query(l, r, &self.root, val) + 1
}
#[inline]
pub unsafe fn update(&mut self, pos: usize, new_val: i64) {
let old = self.old[pos];
seg_update(pos, old, new_val, &mut self.root);
self.old[pos] = new_val;
}
#[inline]
pub unsafe fn kth(&self, l: usize, r: usize, k: usize) -> i64 {
let mut left = 0_i64;
let mut right = 1000000000000;
while left < right {
let mid = (left + right + 1) >> 1;
if self.query(l, r, mid) <= k {
left = mid;
} else {
right = mid - 1;
}
}
left
}
#[inline]
pub unsafe fn pre(&self, l: usize, r: usize, val: i64) -> i64 {
seg_pre(l, r, &self.root, val)
}
#[inline]
pub unsafe fn nxt(&self, l: usize, r: usize, val: i64) -> i64 {
seg_nxt(l, r, &self.root, val)
}
}
//----------------------------Test----------------------------
#[inline]
pub unsafe fn solve<R: BufRead, W: Write>(mut scanner: Scanner<R>, out: &mut W) {
//---------------------------------------------常用宏---------------------------------------------
#[allow(unused_macros)]
macro_rules! puts {($($format:tt)*) => (let _ = writeln!(out,$($format)*););}
#[allow(unused_macros)]
macro_rules! read_type_usize {() => {scanner.next::<usize>()};}
#[allow(unused_macros)]
macro_rules! read_type_i32 {() => {scanner.next::<i32>()};}
#[allow(unused_macros)]
macro_rules! read_type_i64 {() => {scanner.next::<i64>()};}
#[allow(unused_macros)]
macro_rules! read_type_i128 {() => {scanner.next::<i128>()};}
#[allow(unused_macros)]
macro_rules! read_type_isize {() => {scanner.next::<isize>()};}
#[allow(unused_macros)]
macro_rules! read_string_u8 {() => {scanner.next::<String>().into_bytes()};}
#[allow(unused_macros)]
macro_rules! read_usize {($n:expr) => {(0..$n).map(|_|scanner.next::<usize>()).collect::<Vec<usize>>()};}
#[allow(unused_macros)]
macro_rules! read_i32 {($n:expr) => {(0..$n).map(|_|scanner.next::<i32>()).collect::<Vec<i32>>()};}
#[allow(unused_macros)]
macro_rules! read_i64 {($n:expr) => {(0..$n).map(|_|scanner.next::<i64>()).collect::<Vec<i64>>()};}
#[allow(unused_macros)]
macro_rules! read_i128 {($n:expr) => {(0..$n).map(|_|scanner.next::<i128>()).collect::<Vec<i128>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_usize {($n:expr,$m:expr) => {(0..$n).map(|_|read_usize!($m)).collect::<Vec<Vec<usize>>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_i32 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i32!($m)).collect::<Vec<Vec<i32>>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_i64 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i64!($m)).collect::<Vec<Vec<i64>>>()};}
#[allow(unused_macros)]
macro_rules! count_bit {($n:expr) => {{let(mut ans,mut k)=(0_usize,$n);while k>0{ans+=1;k&=k-1;}ans}};}
#[allow(unused_macros)]
macro_rules! print_all {($A:expr) => {{for &v in &$A{let _ = write!(out, "{} ", v);}puts!();}};}
//-----------------------------------------------------------------------------------------------
let n = read_type_usize!();
let m = read_type_usize!();
let a = read_i64!(n);
let mut s = SegTree::new(a);
for _ in 0..m {
let t = read_type_usize!();
match t {
1 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.query(l,r,val));
}
2 => {
let (l, r, k) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_usize!());
puts!("{}",s.kth(l,r,k));
}
3 => {
let (pos, val) = (read_type_usize!() - 1, read_type_i64!());
s.update(pos, val);
}
4 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.pre(l,r,val));
}
5 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.nxt(l,r,val));
}
_ => {}
}
}
}
//-----------------------------main-------------------------------------
fn main() {
let (stdin, mut stdout) = in_out();
unsafe { solve(Scanner::new(stdin), &mut stdout); }
}
// --------------------------- tools -----------------------------------
mod raw {
use std::fs::File;
use std::io::{BufRead, BufReader, BufWriter, stdin, stdout, Write};
#[cfg(windows)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::windows::prelude::{AsRawHandle, FromRawHandle};
unsafe {
let stdin = File::from_raw_handle(stdin().as_raw_handle());
let stdout = File::from_raw_handle(stdout().as_raw_handle());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
#[cfg(unix)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::unix::prelude::{AsRawFd, FromRawFd};
unsafe {
let stdin = File::from_raw_fd(stdin().as_raw_fd());
let stdout = File::from_raw_fd(stdout().as_raw_fd());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
}
mod scanner {
use std::io::BufRead;
pub struct Scanner<R> {
reader: R,
buf_str: Vec<u8>,
buf_iter: std::str::SplitAsciiWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Self { reader, buf_str: Vec::new(), buf_iter: "".split_ascii_whitespace() }
}
pub fn next<T: std::str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buf_iter.next() {
return token.parse().ok().expect("Failed parse");
}
unsafe { self.buf_str.set_len(0); }
self.reader.read_until(b'\n', &mut self.buf_str).expect("Failed read");
self.buf_iter = unsafe {
let slice = std::str::from_utf8_unchecked(&self.buf_str);
std::mem::transmute(slice.split_ascii_whitespace())
}
}
}
}
}Rust与Splay树
多注意splay与rotate的细节
Rust
#![allow(unused_variables)]
#![warn(clippy::large_stack_arrays)]
#![warn(unused_macros)]
use crate::raw::in_out;
use crate::scanner::Scanner;
use std::io::{BufRead, Write};
use std::ops::{Add, AddAssign};
//----------------------------递归闭包---------------------------
// struct Func<'a, A, F>(&'a dyn Fn(Func<'a, A, F>, A) -> F);
//
// impl<'a, A, F> Clone for Func<'a, A, F> {
// fn clone(&self) -> Self {
// Self(self.0)
// }
// }
//
// impl<'a, A, F> Copy for Func<'a, A, F> {}
//
// impl<'a, A, F> Func<'a, A, F> {
// fn call(&self, f: Func<'a, A, F>, x: A) -> F {
// (self.0)(f, x)
// }
// }
//
// fn y<A, R>(g: impl Fn(&dyn Fn(A) -> R, A) -> R) -> impl Fn(A) -> R {
// move |x| (|f: Func<A, R>, x| f.call(f, x))(Func(&|f, x| g(&|x| f.call(f, x), x)), x)
// }
//Y组合子使用示例:(多参采用元组传参)
// let dfs = | f: & dyn Fn((usize, i32,bool)) -> bool, (i,sum,s): (usize,i32,bool) | -> bool{
// if i == n {
// return sum == 0 & & s;
// }
// return f((i + 1, sum + a[i], true)) | | f((i + 1, sum, s)) | |
// f((i + 1, sum - a[i], true));
// };
//----------------------------递归闭包---------------------------
//----------------------------常用函数----------------------------
#[allow(dead_code)]
#[inline]
fn prefix_array<T>(a: &Vec<T>, start: T) -> Vec<T> where T: Add<Output=T> + Copy + AddAssign {
(0..=a.len()).scan(start, |x, y| if y == 0 { Some(start) } else {
*x += a[y - 1];
Some(*x)
}).collect::<Vec<T>>()
}
#[allow(dead_code)]
#[inline]
fn suffix_array<T>(a: &Vec<T>, end: T) -> Vec<T> where T: Add<Output=T> + Copy + AddAssign {
let mut tmp = (0..=a.len()).rev().scan(end, |x, y| if y == a.len() { Some(end) } else {
*x += a[y];
Some(*x)
}).collect::<Vec<T>>();
tmp.reverse();
tmp
}
pub mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN { res.mt[i] = F.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62)).wrapping_add(i as u64); }
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 { self.gen() % n }
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 { f + self.next(t - f + 1) }
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() { RAND = Some(Random::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF) as u64)); }
RAND.as_mut().unwrap()
}
}
pub trait Shuffle { fn shuffle(&mut self); }
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}
//----------------------------常用函数----------------------------
//----------------------------Test----------------------------
#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
struct Node(*mut TreeNode);
#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
struct TreeNode {
fa: Node,
child: [Node; 2],
size: usize,
val: i64,
cnt: usize,
}
impl Node {
pub fn none() -> Self {
Self(std::ptr::null_mut())
}
pub fn new(val: i64, fa: Node) -> Self {
let mut ans = Self::none();
ans.0 = Box::into_raw(Box::new(TreeNode {
val,
fa,
child: [Self::none(), Self::none()],
cnt: 1,
size: 1,
}));
ans
}
#[inline]
pub fn clear(&mut self) {
let old = self.0;
self.0 = std::ptr::null_mut();
unsafe {
let _ = Box::from_raw(old);
}
}
#[inline]
pub fn fa(&self) -> &Node {
unsafe { &(*self.0).fa }
}
#[inline]
pub fn fa_mut(&mut self) -> &mut Node {
unsafe { &mut (*self.0).fa }
}
#[inline]
pub fn size(&self) -> usize {
unsafe { (*self.0).size }
}
#[inline]
pub fn cnt(&self) -> usize {
unsafe { (*self.0).cnt }
}
#[inline]
pub fn left(&self) -> &Node {
unsafe { &(*self.0).child[0] }
}
#[inline]
pub fn left_mut(&mut self) -> &Node {
unsafe { &mut (*self.0).child[0] }
}
#[inline]
pub fn right(&self) -> &Node {
unsafe { &(*self.0).child[1] }
}
#[inline]
pub fn right_mut(&mut self) -> &Node {
unsafe { &mut (*self.0).child[1] }
}
#[inline]
pub fn exist(&self) -> bool {
!self.0.is_null()
}
#[inline]
pub unsafe fn update(&mut self) {
(*self.0).size = self.cnt();
if self.left().exist() {
(*self.0).size += self.left().size();
}
if self.right().exist() {
(*self.0).size += self.right().size();
}
}
#[inline]
pub fn idx(&self) -> usize {
if self.fa().exist() && self.fa().right() == self {
return 1;
}
0
}
#[inline]
pub fn val(&self) -> i64 {
unsafe { (*self.0).val }
}
#[inline]
pub unsafe fn rotate(&mut self) {
let mut curr = *self;
let id = self.idx();
let mut fa = (*self.0).fa;
if fa.exist() {
let fa_id = fa.idx();
let faf = (*fa.0).fa;
if faf.exist() {
(*faf.0).child[fa_id] = curr;
}
*curr.fa_mut() = faf;
(*fa.0).child[id] = (*curr.0).child[id ^ 1];
if (*curr.0).child[id ^ 1].exist() {
*(*curr.0).child[id ^ 1].fa_mut() = fa;
}
(*curr.0).child[id ^ 1] = fa;
*fa.fa_mut() = curr;
fa.update();
curr.update();
*self = Node {
..curr
};
}
}
#[inline]
pub unsafe fn splay(&mut self) {
while self.fa().exist() {
if self.fa().fa().exist() {
if self.idx() == self.fa().idx() {
self.fa_mut().rotate();
} else {
self.rotate();
}
}
self.rotate();
}
}
#[inline]
pub unsafe fn query(&mut self, val: i64) -> usize {
let mut curr = *self;
let mut ans = 0;
loop {
let mut size = 0;
if curr.left().exist() {
size = curr.left().size();
}
if val < curr.val() {
if !curr.left().exist() {
curr.splay();
*self = Node {
..curr
};
return ans;
}
curr = *curr.left();
} else if val == curr.val() {
curr.splay();
*self = Node {
..curr
};
return ans + size;
} else {
ans += curr.cnt() + size;
if !curr.right().exist() {
curr.splay();
*self = Node {
..curr
};
return ans;
}
curr = *curr.right();
}
}
}
#[inline]
pub unsafe fn kth(&mut self, mut k: usize) -> i64 {
let mut curr = *self;
loop {
let mut size = 0;
if curr.left().exist() {
size = curr.left().size();
}
if k <= size {
curr = *curr.left();
} else if k <= size + curr.cnt() {
curr.splay();
*self = Node {
..curr
};
return curr.val();
} else {
k -= size + curr.cnt();
curr = *curr.right();
}
}
}
}
unsafe fn merge(mut x: Node, mut y: Node) -> Node {
if !x.exist() {
if y.exist() {
*y.fa_mut() = Node::none();
}
return y;
}
if !y.exist() {
*x.fa_mut() = Node::none();
return x;
}
*x.fa_mut() = Node::none();
*y.fa_mut() = Node::none();
y.kth(1);
(*y.0).child[0] = x;
(*x.0).fa = y;
y.update();
y
}
struct SplayTree {
root: Node,
}
impl SplayTree {
pub fn new() -> Self {
Self { root: Node::none() }
}
#[inline]
pub unsafe fn insert(&mut self, val: i64) {
if !self.root.exist() {
self.root = Node::new(val, Node::none());
return;
}
let mut curr = self.root;
loop {
if curr.val() == val {
(*curr.0).cnt += 1;
(*curr.0).size += 1;
curr.splay();
self.root = Node {
..curr
};
return;
} else {
let mut i = 0;
if curr.val() < val {
i = 1;
}
if !(*curr.0).child[i].exist() {
(*curr.0).child[i] = Node::new(val, curr);
curr.update();
curr = (*curr.0).child[i];
curr.splay();
self.root = Node {
..curr
};
return;
} else {
curr = (*curr.0).child[i];
}
}
}
}
#[inline]
pub unsafe fn remove(&mut self, val: i64) {
self.root.query(val);
if self.root.val() == val {
if self.root.cnt() > 1 {
(*self.root.0).cnt -= 1;
(*self.root.0).size -= 1;
} else {
self.root = merge(*self.root.left(), *self.root.right());
}
}
}
#[inline]
pub unsafe fn query(&mut self, val: i64) -> usize {
self.root.query(val) + 1
}
#[inline]
pub unsafe fn kth(&mut self, k: usize) -> i64 {
self.root.kth(k)
}
#[inline]
pub unsafe fn pre(&mut self, val: i64) -> i64 {
let mut curr = self.root;
let mut ans = Node::none();
while curr.exist() {
if curr.val() < val {
ans = curr;
curr = *curr.right();
} else {
curr = *curr.left();
}
}
if !ans.exist() {
return -2147483647;
}
ans.splay();
self.root = Node {
..ans
};
ans.val()
}
#[inline]
pub unsafe fn nxt(&mut self, val: i64) -> i64 {
let mut curr = self.root;
let mut ans = Node::none();
while curr.exist() {
if curr.val() > val {
ans = curr;
curr = *curr.left();
} else {
curr = *curr.right();
}
}
if !ans.exist() {
return 2147483647;
}
ans.splay();
self.root = Node {
..ans
};
ans.val()
}
}
struct SegNode(*mut Seg_Node);
struct Seg_Node {
l: usize,
r: usize,
mid: usize,
val: SplayTree,
left: SegNode,
right: SegNode,
}
impl SegNode {
pub unsafe fn none() -> Self {
Self(std::ptr::null_mut())
}
pub unsafe fn new(l: usize, r: usize) -> Self {
let mut ans = Self::none();
ans.0 = Box::into_raw(Box::new(Seg_Node {
left: Self::none(),
right: Self::none(),
val: SplayTree::new(),
l,
r,
mid: (l + r) >> 1,
}));
ans
}
#[inline]
fn left(&self) -> &SegNode {
unsafe { &(*self.0).left }
}
#[inline]
fn right(&self) -> &SegNode {
unsafe { &(*self.0).right }
}
#[inline]
fn left_mut(&mut self) -> &mut SegNode {
unsafe { &mut (*self.0).left }
}
#[inline]
fn right_mut(&mut self) -> &mut SegNode {
unsafe { &mut (*self.0).right }
}
#[inline]
fn clear(&mut self) {
let old = self.0;
self.0 = std::ptr::null_mut();
unsafe {
let _ = Box::from_raw(old);
}
}
#[inline]
fn l(&self) -> usize {
unsafe { (*self.0).l }
}
#[inline]
fn r(&self) -> usize {
unsafe { (*self.0).r }
}
#[inline]
fn mid(&self) -> usize {
unsafe { (*self.0).mid }
}
}
#[inline]
unsafe fn push_down(node: &mut SegNode) {
if node.left().0.is_null() {
(*node.0).left = SegNode::new(node.l(), node.mid());
}
if node.right().0.is_null() {
(*node.0).right = SegNode::new(node.mid() + 1, node.r());
}
}
struct SegTree {
root: SegNode,
old: Vec<i64>,
}
#[inline]
unsafe fn init(node: &mut SegNode, old: &Vec<i64>) {
let l = node.l();
let r = node.r();
for i in l..=r {
(*node.0).val.insert(old[i]);
}
if l == r {
return;
}
push_down(node);
init(node.left_mut(), old);
init(node.right_mut(), old);
}
#[inline]
unsafe fn seg_query(l: usize, r: usize, node: &SegNode, val: i64) -> usize {
if !node.0.is_null() {
if l <= node.l() && node.r() <= r {
return (*node.0).val.query(val) - 1;
}
let mut ans = 0_usize;
if l <= node.mid() {
ans += seg_query(l, r, node.left(), val);
}
if r > node.mid() {
ans += seg_query(l, r, node.right(), val);
}
ans
} else {
0
}
}
#[inline]
unsafe fn seg_update(x: usize, old: i64, new_val: i64, node: &mut SegNode) {
let l = node.l();
let r = node.r();
let mid = node.mid();
(*node.0).val.remove(old);
(*node.0).val.insert(new_val);
if l == x && x == r {
return;
}
if x <= mid {
seg_update(x, old, new_val, node.left_mut());
} else {
seg_update(x, old, new_val, node.right_mut());
}
}
#[inline]
unsafe fn seg_pre(l: usize, r: usize, node: &SegNode, val: i64) -> i64 {
let ll = node.l();
let rr = node.r();
let mid = node.mid();
if l <= ll && rr <= r {
return (*node.0).val.pre(val);
}
let mut ans = -2147483647_i64;
if l <= mid {
ans = ans.max(seg_pre(l, r, node.left(), val));
}
if r > mid {
ans = ans.max(seg_pre(l, r, node.right(), val));
}
ans
}
#[inline]
unsafe fn seg_nxt(l: usize, r: usize, node: &SegNode, val: i64) -> i64 {
let ll = node.l();
let rr = node.r();
let mid = node.mid();
if l <= ll && rr <= r {
return (*node.0).val.nxt(val);
}
let mut ans = 2147483647_i64;
if l <= mid {
ans = ans.min(crate::seg_nxt(l, r, node.left(), val));
}
if r > mid {
ans = ans.min(crate::seg_nxt(l, r, node.right(), val));
}
ans
}
impl SegTree {
pub unsafe fn new(old: Vec<i64>) -> Self {
let n = old.len();
let mut root = SegNode::new(0, n - 1);
init(&mut root, &old);
Self { root, old }
}
#[inline]
pub unsafe fn query(&self, l: usize, r: usize, val: i64) -> usize {
seg_query(l, r, &self.root, val) + 1
}
#[inline]
pub unsafe fn update(&mut self, pos: usize, new_val: i64) {
let old = self.old[pos];
seg_update(pos, old, new_val, &mut self.root);
self.old[pos] = new_val;
}
#[inline]
pub unsafe fn kth(&self, l: usize, r: usize, k: usize) -> i64 {
let mut left = 0_i64;
let mut right = 1000000000000;
while left < right {
let mid = (left + right + 1) >> 1;
if self.query(l, r, mid) <= k {
left = mid;
} else {
right = mid - 1;
}
}
left
}
#[inline]
pub unsafe fn pre(&self, l: usize, r: usize, val: i64) -> i64 {
seg_pre(l, r, &self.root, val)
}
#[inline]
pub unsafe fn nxt(&self, l: usize, r: usize, val: i64) -> i64 {
seg_nxt(l, r, &self.root, val)
}
}
//----------------------------Test----------------------------
#[inline]
pub unsafe fn solve<R: BufRead, W: Write>(mut scanner: Scanner<R>, out: &mut W) {
//---------------------------------------------常用宏---------------------------------------------
#[allow(unused_macros)]
macro_rules! puts {($($format:tt)*) => (let _ = writeln!(out,$($format)*););}
#[allow(unused_macros)]
macro_rules! read_type_usize {() => {scanner.next::<usize>()};}
#[allow(unused_macros)]
macro_rules! read_type_i32 {() => {scanner.next::<i32>()};}
#[allow(unused_macros)]
macro_rules! read_type_i64 {() => {scanner.next::<i64>()};}
#[allow(unused_macros)]
macro_rules! read_type_i128 {() => {scanner.next::<i128>()};}
#[allow(unused_macros)]
macro_rules! read_type_isize {() => {scanner.next::<isize>()};}
#[allow(unused_macros)]
macro_rules! read_string_u8 {() => {scanner.next::<String>().into_bytes()};}
#[allow(unused_macros)]
macro_rules! read_usize {($n:expr) => {(0..$n).map(|_|scanner.next::<usize>()).collect::<Vec<usize>>()};}
#[allow(unused_macros)]
macro_rules! read_i32 {($n:expr) => {(0..$n).map(|_|scanner.next::<i32>()).collect::<Vec<i32>>()};}
#[allow(unused_macros)]
macro_rules! read_i64 {($n:expr) => {(0..$n).map(|_|scanner.next::<i64>()).collect::<Vec<i64>>()};}
#[allow(unused_macros)]
macro_rules! read_i128 {($n:expr) => {(0..$n).map(|_|scanner.next::<i128>()).collect::<Vec<i128>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_usize {($n:expr,$m:expr) => {(0..$n).map(|_|read_usize!($m)).collect::<Vec<Vec<usize>>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_i32 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i32!($m)).collect::<Vec<Vec<i32>>>()};}
#[allow(unused_macros)]
macro_rules! read_tow_array_i64 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i64!($m)).collect::<Vec<Vec<i64>>>()};}
#[allow(unused_macros)]
macro_rules! count_bit {($n:expr) => {{let(mut ans,mut k)=(0_usize,$n);while k>0{ans+=1;k&=k-1;}ans}};}
#[allow(unused_macros)]
macro_rules! print_all {($A:expr) => {{for &v in &$A{let _ = write!(out, "{} ", v);}puts!();}};}
//-----------------------------------------------------------------------------------------------
let n = read_type_usize!();
let m = read_type_usize!();
let a = read_i64!(n);
let mut s = SegTree::new(a);
for _ in 0..m {
let t = read_type_usize!();
match t {
1 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.query(l,r,val));
}
2 => {
let (l, r, k) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_usize!());
puts!("{}",s.kth(l,r,k));
}
3 => {
let (pos, val) = (read_type_usize!() - 1, read_type_i64!());
s.update(pos, val);
}
4 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.pre(l,r,val));
}
5 => {
let (l, r, val) = (read_type_usize!() - 1, read_type_usize!() - 1, read_type_i64!());
puts!("{}",s.nxt(l,r,val));
}
_ => {}
}
}
}
//-----------------------------main-------------------------------------
fn main() {
let (stdin, mut stdout) = in_out();
unsafe { solve(Scanner::new(stdin), &mut stdout); }
}
// --------------------------- tools -----------------------------------
mod raw {
use std::fs::File;
use std::io::{BufRead, BufReader, BufWriter, stdin, stdout, Write};
#[cfg(windows)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::windows::prelude::{AsRawHandle, FromRawHandle};
unsafe {
let stdin = File::from_raw_handle(stdin().as_raw_handle());
let stdout = File::from_raw_handle(stdout().as_raw_handle());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
#[cfg(unix)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::unix::prelude::{AsRawFd, FromRawFd};
unsafe {
let stdin = File::from_raw_fd(stdin().as_raw_fd());
let stdout = File::from_raw_fd(stdout().as_raw_fd());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
}
mod scanner {
use std::io::BufRead;
pub struct Scanner<R> {
reader: R,
buf_str: Vec<u8>,
buf_iter: std::str::SplitAsciiWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Self { reader, buf_str: Vec::new(), buf_iter: "".split_ascii_whitespace() }
}
pub fn next<T: std::str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buf_iter.next() {
return token.parse().ok().expect("Failed parse");
}
unsafe { self.buf_str.set_len(0); }
self.reader.read_until(b'\n', &mut self.buf_str).expect("Failed read");
self.buf_iter = unsafe {
let slice = std::str::from_utf8_unchecked(&self.buf_str);
std::mem::transmute(slice.split_ascii_whitespace())
}
}
}
}
}总结
这些平衡树属于个人理解,如有不同写法,参照自己的.主要提供如果用面向对象书写.本文章仅供参考.
评论 (18)
