首页 > 其他分享 >Treap 模板代码

Treap 模板代码

时间:2023-06-09 17:46:57浏览次数:41  
标签:ch return fa int root 代码 Treap data 模板

struct Node {
	int pri, data, num, sz, ch[2], fa;
}t[maxn];

int pos;

struct Treap {
	int root;
	int newNode(int x) {
		t[++ pos] = (Node){rand(), x, 1, 1, 0, 0, 0};
		return pos;
	}
	void update(int x) {
		t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + t[x].num;
	}
	int locate(int x) {
		return x == t[t[x].fa].ch[1];
	}
	void rotate(int x){
		int y = t[x].fa, z = t[y].fa, p = locate(x);
		t[y].ch[p] = t[x].ch[p ^ 1], t[x].ch[p ^ 1] = y, t[t[y].ch[p]].fa = y;
		t[x].fa = t[y].fa, t[y].fa = x;
		update(y), update(x);
		if (z) {
			t[z].ch[t[z].ch[1] == y] = x;
			update(z);
		}
	}
	void maintain(int x) {
		while (x) {
			update(x);
			x = t[x].fa;
		}
	}
	void insert(int data) {
		if (root == 0) {
			root = newNode(data);
			return ;
		}
		int x = root;
		while (true) {
			if (t[x].data == data){
				t[x].num ++;
				break;
			}
			int p = data > t[x].data;
			if (!t[x].ch[p]) {
				t[x].ch[p] = newNode(data);
				t[t[x].ch[p]].fa = x;
				x = t[x].ch[p];
				break;
			}
			x = t[x].ch[p];
		}
		maintain(x);
		while (t[x].fa && t[t[x].fa].pri < t[x].pri)
			rotate(x);
		if (t[x].fa == 0)
			root = x;
	}
	int get_pos(int data) {
		int x = root;
		while (true) {
			if (t[x].data == data)
				return x;
			int p = data > t[x].data;
			x = t[x].ch[p];
		}
		return x;
	}
	void del(int data) {
		int x = get_pos(data);
		if (t[x].num > 1){
			t[x].num --;
			maintain(x);
			return ;
		}
		while (t[x].ch[0] + t[x].ch[1]) {
			int p = t[t[x].ch[1]].pri > t[t[x].ch[0]].pri;
			rotate(t[x].ch[p]);
			if (t[t[x].fa].fa == 0)
				root = t[x].fa;
		}
		t[x].num = 0;
		maintain(x);
		t[t[x].fa].ch[locate(x)] = 0;
		t[x].fa = 0;
		if (root == x)
			root = 0;
	}
	int rks(int data) {
		int x = root;
		int res = 0;
		while (true) {
			if (t[x].data == data)
				return res + t[t[x].ch[0]].sz + 1;
			if (t[x].data < data)
				res += t[x].num + t[t[x].ch[0]].sz;
			x = t[x].ch[(data > t[x].data)];
		}
	}
	int kth(int k) {
		int x = root;
		while (x) {
			if (t[t[x].ch[0]].sz >= k)
				x = t[x].ch[0];
			else if (t[x].num + t[t[x].ch[0]].sz >= k)
				return t[x].data;
			else k -= t[x].num + t[t[x].ch[0]].sz, x = t[x].ch[1];
		}
	}
	int pre(int data) {
		int x = root, ans;
		while (x) {
			if (t[x].data < data)
				ans = t[x].data, x = t[x].ch[1];
			else x = t[x].ch[0];
		}
		return ans;
	}
	int suf(int data) {
		int x = root, ans;
		while (x) {
			if (t[x].data > data)
				ans = t[x].data, x = t[x].ch[0];
			else x = t[x].ch[1];
		}
		return ans;
	}
}treap;

标签:ch,return,fa,int,root,代码,Treap,data,模板
From: https://www.cnblogs.com/yh2021shx/p/17469855.html

相关文章

  • Sgt 模板代码
    structSgt{ intlazyTag; intval;}t[maxn];voidpushUp(intx,intl,intr){ t[x].val=t[x].lazyTag*(r-l+1)+t[x*2].val+t[x*2+1].val;}voidpushDown(intx,intl,intr){ intmid=l+r>>1; t[x*2].lazyTag+=t[x].lazyTa......
  • mysql 8.0.26 my.cnf 配置文件模板
    ##############[mysqld]basedir=/home/work/mysql_3306datadir=/home/work/mysql_3306/datatmpdir=/home/work/mysql_3306/tmppid_file=/home/work/mysql_3306/tmp/mysqld.pidsocket=/home/work/mysql_3306/tmp/mysql.sockmysqlx_socket=/home/work/mysql......
  • 21份软件测试全流程文档模板(标准版)
    1、需求说明书2、功能测试计划3、功能测试用例4、业务流程测试用例5、系统安装配置说明书6、阶段功能测试报告7、性能测试计划8、性能测试用例9、性能测试报告10、系统功能测试报告11、需求变更说明书12、用户建议说明书13、验收测试报告14、产品发布说明书15、系统......
  • 模板模式:具体的步骤延迟到子类中实现
    模板模式是一种行为设计模式,它允许将算法的结构与实现分开,从而使得实现可以在不改变算法结构的情况下被重用。模板模式的核心思想是定义一个抽象基类,其中包含了算法的骨架,但是具体的步骤延迟到子类中去实现。这样一来,同一套算法的不同实现可以共享同一个基类代码,从而避免了代码的......
  • 卷积神经网络-全面图解-带你了解前向后向传播的所有细节(文末代码)
    卷积神经网络-全面图解-带你了解前向后向传播的所有细节综述本文将会从基础的前馈神经网络入手,通过bp神经网络,引出卷积神经网络,并把专门的重点放在如何理解和实现卷积神经网络的卷积层、下采样层、全连接层、以及最终的softmax的反向传播的理解。最后实现基于python的车标识别6分类......
  • java代码输出控制台输出菱形
    privatestaticvoidrhombFuncation(){introw=3;for(inti=1;i<=row;i++){for(introw1=row;row1>i;row1--){System.out.print("-");}for(intj=0;j<i;j++){Syste......
  • Quartz + SpringBoot 实现定时任务(多任务,多执行时间)代码模板(直接CV即可)
    一,什么是Quartzquartz是一款开源且丰富特性的Java任务调度库,用于实现任务调度和定时任务。它支持各种任务类型和灵活的配置选项,具备作业持久化、集群和分布式调度、错误处理和重试机制等功能。Quartz被广泛应用于各种应用程序中,提供可靠和灵活的任务调度解决方案。二,核心概念......
  • c++ 模板详解
    模板就是将类型进行参数化函数模板//函数模板的定义格式template<class形参名,class形参名...>返回值类型函数名(参数列表){函数体;}模板形参不能为空,并且函数模板中每一个类型参数在函数参数表中至少使用一次,只有这样才能推断出具体的类型template<classT>......
  • 代理IP出现错误代码429如何解决
    代理IP出现错误代码429主要是因为请求过多,即客户端向服务端发送请求过于频繁,超出服务器设置的请求限制,导致连接失败。这种问题通常出现在需要频繁获取数据或者进行大量操作时。那么,如何解决代理IP出现错误代码429呢?以下是一些可能的解决方法:1.增加请求间隔时间:可以尝试......
  • 代理IP出现错误代码504如何解决
    代理IP出现错误代码504是一种常见的网络错误,意思是网关超时,即在客户端向服务端发送请求后,代理服务器过了一段时间都没有响应,导致连接失败。这个问题通常会出现在需要从服务器获取大量数据或者处理复杂请求时。那么,如何解决代理IP出现错误代码504呢?以下是一些可能的解决方法......