首页 > 其他分享 >Splay 伸展树扩展应用

Splay 伸展树扩展应用

时间:2023-12-07 21:14:02浏览次数:27  
标签:val int 扩展 tr son Splay fa size 伸展

Update

2023.5.27 好吧,lxl好像已经发明过这种数据结构了(悲)。

前言

谈谈扩展Splay。(下文用KzSplay代替)

前置知识:

1.Splay,以及文艺平衡树。

2.线段树。

问题引入

请你设计一种数据结构,支持 在线 处理以下操作:

给定一个长度为 \(n\) 的序列 \(a\) 。

1.支持序列的区间翻转。

2.支持任意区间的交换。

(如 "aabbc" 交换 "aa" 与 "c" 变为 "cbbaa")

3.支持区间的求和。

4.支持区间整体加减。

约束条件:

\(1 \leq n \leq 10^5,1 \leq a_i \leq 10^9\)

分析

首先,看到操作1就可以知道,这种数据结构一定要跟平衡树的左右子树旋转有关。

再看操作2,实际上可以发现这个操作可以分解成四次操作1:

操作3和操作4模仿线段树懒标记下传,在Splay旋转前先下传并摆脱懒标记,具体见代码。

Code

#include <bits/stdc++.h>
using namespace std;
int n, Q, opts, l, r, l1, r1, l2, r2, dt, Kth_Res;
const int SIZE_OF_N = 1e5 + 5;
const int SIZE_OF_KzSPLAY = 1e5 + 5;
int root, tot, a[SIZE_OF_N];
struct KzSplay {
	int size, fa, val;
	int id, son[2], lazy, tag;
	KzSplay (){
		size = fa = val = 0;
		id = son[0] = son[1] = lazy = 0;
	}
}tr[SIZE_OF_KzSPLAY];
void make0 (){
	tr[0].fa = tr[0].id = tr[0].lazy = tr[0].size = tr[0].son[0] = tr[0].son[1] = tr[0].tag = tr[0].val = 0;
}
void push_down (int x){ // Before doing 'push_down', the point must be already solved.
	make0 ();
	if (x == 0)
		return ;
	if (tr[x].lazy == 1){
		tr[tr[x].son[0]].lazy ^= 1;
		tr[tr[x].son[1]].lazy ^= 1;
		swap (tr[x].son[0], tr[x].son[1]);
		tr[x].lazy = 0;
	}
	if (tr[x].tag != 0){
		tr[tr[x].son[0]].tag += tr[x].tag;
		tr[tr[x].son[1]].tag += tr[x].tag;
		a[tr[tr[x].son[0]].id] += tr[x].tag;
		a[tr[tr[x].son[1]].id] += tr[x].tag;
		tr[tr[x].son[0]].val += tr[x].tag * tr[tr[x].son[0]].size;
		tr[tr[x].son[1]].val += tr[x].tag * tr[tr[x].son[1]].size;
		tr[x].tag = 0;
	}
}
void maintain (int x){
	make0 ();
	push_down (x);
	push_down (tr[x].son[0]);
	push_down (tr[x].son[1]);
    make0 ();
	tr[x].size = tr[tr[x].son[0]].size + tr[tr[x].son[1]].size + 1;
    tr[x].val = tr[tr[x].son[0]].val + tr[tr[x].son[1]].val + a[tr[x].id];
}
int get (int x){
	return (int) x != tr[tr[x].fa].son[0];
}
void zag (int x){
	make0 ();
	int y = tr[x].fa, z = tr[y].fa, u = tr[x].son[0];
	int xval = tr[x].val, xsize = tr[x].size;
	int yval = tr[y].val, ysize = tr[y].size;
	int uval = tr[u].val, usize = tr[u].size;
	tr[x].size = ysize;
	tr[x].val = yval;
	tr[y].size += - xsize + usize;
	tr[y].val += - xval + uval;
	tr[y].son[1] = tr[x].son[0];
	if (tr[y].son[1])
		tr[tr[y].son[1]].fa = y;
	tr[x].son[0] = y;
	tr[y].fa = x;
	tr[x].fa = z;
	if (z)
		tr[z].son[y != tr[z].son[0]] = x;
	maintain (y);
	maintain (x);
}
void zig (int x){
	make0 ();
	int y = tr[x].fa, z = tr[y].fa, u = tr[x].son[1];
	int xval = tr[x].val, xsize = tr[x].size;
	int yval = tr[y].val, ysize = tr[y].size;
	int uval = tr[u].val, usize = tr[u].size;
	tr[x].size = ysize;
	tr[x].val = yval;
	tr[y].size += - xsize + usize;
	tr[y].val += - xval + uval;
	tr[y].son[0] = tr[x].son[1];
	if (tr[y].son[0])
		tr[tr[y].son[0]].fa = y;
	tr[x].son[1] = y;
	tr[y].fa = x;
	tr[x].fa = z;
	if (z)
		tr[z].son[y != tr[z].son[0]] = x;
	maintain (y);
	maintain (x);
}
void rotate (int x){
	int z = tr[x].fa;
	push_down (z);
	push_down (tr[z].son[0]);
	push_down (tr[z].son[1]);
	push_down (tr[tr[z].son[0]].son[0]);
	push_down (tr[tr[z].son[0]].son[1]);
	push_down (tr[tr[z].son[1]].son[0]);
	push_down (tr[tr[z].son[1]].son[1]);
	if (get (x) == 0)
		zig (x);
	else
		zag (x);
}
void splay (int x){
	for (int f = tr[x].fa;f = tr[x].fa, f;rotate (x)){
        push_down (f);
        push_down (x);
		if (tr[f].fa)
			rotate (get (x) == get (f) ? f : x);
    }
	root = x;
}
void splay_ (int x){
	for (;tr[x].fa && tr[x].fa != root;rotate (x)){
        push_down (tr[x].fa);
        push_down (x);
	}
}
int Kth (int k){
	Kth_Res = 0;
	int cur = root;
	while (true){
		push_down (cur);
		if (tr[cur].son[0] && k <= tr[tr[cur].son[0]].size)
			cur = tr[cur].son[0];
		else {
			k -= tr[tr[cur].son[0]].size + 1;
			Kth_Res += tr[tr[cur].son[0]].val + a[tr[cur].id];
			if (k <= 0){
				return cur;
			}
			cur = tr[cur].son[1];
		}
	}
}
void Swap (int l, int r){
    if (r <= l)
        return ;
	splay (Kth (l));
	splay_ (Kth (r + 2));
	tr[tr[tr[root].son[1]].son[0]].lazy ^= 1;
}
void Update (int l, int r, int x){
	splay (Kth (l));
	splay_ (Kth (r + 2));
	int u = tr[tr[root].son[1]].son[0];
	tr[u].tag += x;
	tr[u].val += tr[u].size * x;
	a[tr[u].id] += x;
}
void Build (int l, int r, int father, int t){
	if (l > r)
		return ;
	int mid = l + r >> 1, p;
	++ tot;
	p = tot;
	tr[tot].id = mid;
	tr[tot].val = a[mid];
	if (father)
		tr[tot].fa = father;
	else
		root = tot;
	tr[tot].size = 1;
	tr[father].son[t] = tot;
	if (l == r)
		return ;
	Build (l, mid - 1, p, 0);
	Build (mid + 1, r, p, 1);
	maintain (p);
}
int main (){
	freopen ("example.in", "r", stdin);
	freopen ("example.out", "w", stdout);
	scanf ("%d%d", &n, &Q);
	for (int i = 1;i <= n;++ i)
		scanf ("%d", &a[i]);
	Build (0, n + 1, 0, 0);
	while (Q --){
		scanf ("%d", &opts);
		// 1 : Let [l, r] be upside-down.
		if (opts == 1){
			scanf ("%d%d", &l, &r);
			Swap (l, r);
		}
		// 2 : Swap [l1, r1] and [l2, r2].  ## Tips : (r1 - l1) and (r2 - l2) may not equal to each other.
		if (opts == 2){
			scanf ("%d%d%d%d", &l1, &r1, &l2, &r2);
			int d1 = r1 - l1, d2 = r2 - l2;
			Swap (l1, r2);
			Swap (l1, l1 + d2);
			Swap (l1 + d2 + 1, r2 - d1 - 1);
			Swap (r2 - d1, r2);
		}
		// 3 : Ask the sum of the number of [l, r].
		if (opts == 3){
			scanf ("%d%d", &l, &r);
			Kth (l);
			int el = Kth_Res;
			Kth (r + 1);
			int er = Kth_Res;
			printf ("%d\n", er - el);
		}
		// 4 : Add the same number dt to [l, r].
		if (opts == 4){
			scanf ("%d%d%d", &l, &r, &dt);
			Update (l, r, dt);
		}
	}
	return 0;
}

标签:val,int,扩展,tr,son,Splay,fa,size,伸展
From: https://www.cnblogs.com/imcaigou/p/17883950.html

相关文章

  • Java扩展赋值运算符,字符串连接符
    1.扩展赋值运算符  2.字符串连接符   ......
  • Splay/LCT 学习笔记
    唔,其实我不会Splay,但是我会LCT。众所周知,会LCT和会Splay是两回事,因为LCT只需要旋至根即可。到现在还是不会,但是先把LCT的Splay写一下吧。自己复习用的。先给代码。LCTcodeintisroot(intx){returnch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}intidt(intx){retur......
  • jupyter notebook代码补全扩展安装遇到 Jupyter command `jupyter-contrib` not found
    Jupytercommandjupyter-contribnotfound.解决方案——新的安装方式。方法1:pip方式1.先使用以下命令,卸载旧版本的jupyter_contrib_nbextensions和upyter_nbextensions_configurator:分别用cmd命令,卸载之前的安装pipuninstalljupyter_contrib_nbextensionspipuninsta......
  • 从字符串中分离文件路径,文件名及文件扩展名
    从字符串中分离文件路径,文件名及文件扩展名如一个文件:D:\文档\C#BASE\StringBuilder.md要分离出文件路径:D:\文档\C#BASE\文件名:StringBuilder文件扩展名:md这是我们要拿到“\”和“.”这两个字符最后出现的索引stringpath="D:\文档\C#BASE\StringBuilder.md";inti=path.la......
  • 扩展欧几里得算法
    扩展欧几里得算法裴蜀定理(Bézout'slemma)定义设\(a,b\)是不全为零的整数,对任意整数\(x,y\),满足\(\gcd(a,b)\midax+by\),且存在整数\(x,y\),使得\(ax+by=\gcd(a,b)\).证明对于第一点由于\(\gcd(a,b)\mida,\gcd(a,b)\midb\)所以\(\gcd(a,b)\midax,\gcd(a,b)\mid......
  • 【组成原理-指令】扩展操作码的树形解法
    仿照哈夫曼树(或前缀编码,Prefix-free)的解法,目前先不解释具体怎么画了,直接放例题,大家自己慢慢品味吧。【例1】某指令系统指令长16位,操作码字段为4位,地址码字段为4位,采用扩展操作码技术,形成三地址指令15条、二地址指令15条、一地址指令15条、零地址指令16条。【解......
  • 2023ICCV_FSI Frequency and Spatial Interactive Learning for Image Restoration in
     三.Network 1.  2.FLB:没看懂是怎么分离的水平和竖直方向 3.SLB:每一层保留一半的通道特征用于细化,其余的在特征重构后输出(没看懂)。Multi-distillationNetwork 超分辨网络的Multi-distillationNetwork(2019ACMMM_LightweightImageSuper-ResolutionwithIn......
  • 发现一个很好用的excel的php扩展
    废话不多,直接给文档地址:xlswrite导出时不容易超出内存,号称最大使用内存为最后一行数据大小。导出速度也很6.  插入内容:使用 Spreadsheet时,可以切换使用存储方式,默认是内存,如果切换了其他的比如文件,可以减少内存压力。Settings::setCache需要传入实现接口CacheInte......
  • php8自定义扩展
    1:进入php源码目录下的ext.如/usr/local/php-8/ext2.生成自定义扩展的名字phpext_skel.php--extpython3.撰写函数原型,编辑python.stub.php3.1默认是test1,test2<?php/**@generate-function-entries*/functionall(array$arr):bool{}function......
  • kore可扩展安全的Web 应用程序框架
    kore是基于c开发的web框架,可以让我们使用c以及python开发webapi,主要的特点是安全以及可扩展主要特性SNI支持http1.1支持websocket支持默认TLS支持可选后台任务内置参数校验基于acme的自动https权限分离设计可选异步pg访问模块热加载worker进程沙箱支持(基于pledge以及s......