首页 > 其他分享 >【模板】 Splay

【模板】 Splay

时间:2023-05-06 17:35:35浏览次数:33  
标签:ch cur int tot Splay fa root 模板

splay

#include <bits/stdc++.h>

using namespace std;

const int N = 5e6 + 10;

int val[N], cnt[N], fa[N], ch[N][2], siz[N];
int tot, root;

void maintain(int x) {
	siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}

bool get(int x) {
	return x == ch[fa[x]][1];
}

void clear(int x) {
	ch[x][0] = ch[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;
}

void rotate(int x) {
	int y = fa[x], z = fa[y], chk = get(x);
	ch[y][chk] = ch[x][chk ^ 1];
	if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
	ch[x][chk ^ 1] = y;
	fa[y] = x;
	fa[x] = z;
	if (z) ch[z][y == ch[z][1]] = x;
	maintain(y);
	maintain(x);
}

void splay(int x) {
	for (int f = fa[x]; f = fa[x], f; rotate(x)) {
		if (fa[f]) rotate(get(x) == get(f) ? f : x);
	}
	root = x;
}

void insert(int k) {
	if (!root) {
		val[++tot] = k;
		cnt[tot]++;
		root = tot;
		maintain(root);
		return;
	}
	int cur = root, f = 0;
	while (true) {
		if (val[cur] == k) {
			cnt[cur]++;
			maintain(cur);
			maintain(f);
			splay(cur);
			break;
		}
		f = cur;
		cur = ch[cur][val[cur] < k];
		if (!cur) {
			val[++tot] = k;
			cnt[tot]++;
			fa[tot] = f;
			ch[f][val[f] < k] = tot;
			maintain(tot);
			maintain(f);
			splay(tot);
			break; 
		}
	}
}

int rk(int k) {
	int res = 0, cur = root;
	// ※※※ 
	while (cur) {
		if (val[cur] > k) {
			cur = ch[cur][0];
		}
		else {
			res += siz[ch[cur][0]];
			if (val[cur] == k) {
				splay(cur);
				return res + 1;
			}
			res += cnt[cur];
			cur = ch[cur][1];
		}
	}
	// ※※※
	return res + 1;
}

int kth(int k) {
	int cur = root;
	if (!cur) return 0;
	while (true) {
		if (ch[cur][0] && siz[ch[cur][0]] >= k) {
			cur = ch[cur][0];
		}
		else {
			k -= cnt[cur] + siz[ch[cur][0]];
			if (k <= 0) {
				splay(cur);
				return val[cur];
			}
			cur = ch[cur][1];
		}
	}
}

//insert x first, x is root now, just go find it and delete x at last
int pre() { int cur = ch[root][0]; if (!cur) return 0; while (ch[cur][1]) cur
= ch[cur][1]; splay(cur); return cur; }

int suf() {
	int cur = ch[root][1];
	if (!cur) return 0;
	while (ch[cur][0]) cur = ch[cur][0];
	splay(cur);
	return cur;
}

void del(int k) {
	rk(k);		//find the pos of k and splay it to the root
	if (cnt[root] > 1) {
		cnt[root]--;
		maintain(root);
		return;
	}
	if (!ch[root][0] && !ch[root][1]) {
		clear(root);
		root = 0;
		return;
	}
	if (!ch[root][0]) {
		int cur = root;
		root = ch[root][1];
		fa[root] = 0;
		clear(cur);
		return;
	}
	if (!ch[root][1]) {
		int cur = root;
		root = ch[root][0];
		fa[root] = 0;
		clear(cur);
		return;
	}
	int cur = root, x = pre();
	fa[ch[cur][1]] = x;
	ch[x][1] = ch[cur][1];
	clear(cur);
	maintain(root);
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		int x;
		scanf("%d", &x);
		insert(x);
	}
	int last = 0, res = 0;
	while (m--) {
		int op, x;
		scanf("%d %d", &op, &x);
		x ^= last;
		if (op == 1) insert(x);
		if (op == 2) del(x);
		if (op == 3) last = rk(x), res ^= last;
		if (op == 4) last = kth(x), res ^= last;
		if (op == 5) {
			insert(x);
			last = val[pre()];
			res ^= last;
			del(x);
		}
		if (op == 6) {
			insert(x);
			last = val[suf()];
			res ^= last;
			del(x);
		}
	}
	printf("%d\n", res);
	/*
	int n;
	cin >> n;
	//Node *root = nullptr;
	while (n--) {
		int op, x;
		cin >> op >> x;
		if (op == 1) insert(x);
		if (op == 2) del(x);
		if (op == 3) cout << rk(x) << endl;
		if (op == 4) cout << kth(x) << endl;
		if (op == 5) {
			insert(x);
			cout << val[pre()] << endl;
			del(x);
		}
		if (op == 6) {
			insert(x);
			cout << val[suf()] << endl;
			del(x);
		}
	}
	*/
	return 0;
}

标签:ch,cur,int,tot,Splay,fa,root,模板
From: https://www.cnblogs.com/lr599909928/p/17378077.html

相关文章

  • django模板层
    目录一、模板层1.模板语法传值2.模板语法传值特性3.模板语法之过滤器(内置函数)lengthsliceaddfilesizeformatdatetruncatecharstruncatewordssafe二、模板层之标签分支结构iffor循环with(定义变量名)三、自定义过滤器、标签及inclusion_tag(了解)四、母版(模板)的继承与导入(重要)......
  • OrchardCore 中的 插件开发/ Shape / DisplayDriver / 视图扩展 / Razor代码注入
    请注意该文章仅限于OrchardCore项目中的DisplayDriver扩展机制,ASP.NETCOREMVC自身并没有对应功能,如果需要可以将相关的OrchardCore模块添加到项目中也可以实现响应功能背景最近一个功能需求,需要使用其它用户模拟身份,所以计划在用户列表页面扩展按钮组功能那么开始看代......
  • 使用nacos配置,启动服务时一直报 Error starting ApplicationContext. To display the
    报错日志如下:ErrorstartingApplicationContext.Todisplaytheconditionsreportre-runyourapplicationwith'debug'enabled.-2023-05-0509:46:02.328[TID:N/A]ERROR8236---[main]o.s.b.d.LoggingFailureAnalysisReporter:***********......
  • Python多线程爬虫简单模板
    多线程爬虫的流程可以大致分为:(1)获取种子URL:从初始URL中抓取起始页面,解析其中的URL,并将这些URL添加到未访问的URL队列中;(2)解析下载的网页:从URL队列中取出一个URL,下载其内容,解析其中的链接,并把新的链接放入未访问的URL队列中;(3)存储爬取的数据:从URL队列中取出未访问的URL,把其中的内......
  • DX12 实现 模板——物体轮廓
    前言本篇将展示如何运用深度模板缓冲区来实现游戏中的物体轮廓效果源代码model_outline基础知识模板测试过程//compare_func:定义的比较函数。对两个参数进行比较//StencilRef:模板参考值//StencilReadMask:位于D3D12_DEPTH_STENCIL_DESC//Value:正在接受模板测试的值if......
  • C++类模板(模板类)
    参考资料:C++类模板(模板类)详解(biancheng.net) 人们需要编写多个形式和功能都相似的函数,因此有了函数模板来减少重复劳动;人们也需要编写多个形式和功能都相似的类,于是 C++ 引人了类模板的概念,编译器从类模板可以自动生成多个类,避免了程序员的重复劳动。例如,在《C++运算符重......
  • 【模板】堆 题解
    题目传送门一道小根堆模板题。在做这道题之前,我们先介绍一下小根堆是什么。我们定义小根堆是一种对于任何一个父结点的权值总是小于或等于子节点权值的完全二叉树。因此,不难看出,一个小根堆的堆顶(这棵树的根节点)应该是这个堆(树)中权值最小的结点。简单介绍完了小根堆,我们再介绍......
  • 求最大值(函数模板)
    一、问题描述:两个类如下设计:类Time有三个数据成员,hh,mm,ss,分别代表时,分和秒,并有若干构造函数和一个重载-(减号)的成员函数。类Date有三个数据成员,year,month,day分别代表年月日,并有若干构造函数和一个重载>(<)(大于号或者小于号)的成员函数。要求设计一个函数模板template<classT>Tma......
  • eclipse注释模板及格式化模板导入方法
    格式化模板导入步骤  1.点击Window->Preference->Java->CodeStyle->Formatter2.点击右侧Import选择*.xml模板文件导入即可3.如果需要对模板进行修改,可点击Edit编辑即可4.模板示例:1.<?xmlversion="1.0"encoding="UTF-8"standalone="no"?>2.<profilesvers......
  • 洛谷 P3369 【模板】普通平衡树
    有旋Treap模板#include<bits/stdc++.h>usingnamespacestd;structNode{ Node*ch[2]; intval,rank; intrep_cnt; intsiz; Node(intval):val(val),rep_cnt(1),siz(1){ ch[0]=ch[1]=nullptr; rank=rand(); } voidupd_siz(){ siz=......