首页 > 其他分享 >可持久化trie

可持久化trie

时间:2024-02-23 22:23:42浏览次数:31  
标签:持久 trie 异或 权值 oplus 节点

可持久化trie

考虑像主席树建树,然后可以处理trie的进阶问题

最大异或和

题目描述

给定一个非负整数序列 \(\{a\}\),初始长度为 \(N\)。

有 \(M\) 个操作,有以下两种操作类型:

  1. A x:添加操作,表示在序列末尾添加一个数 \(x\),序列的长度 \(N\) 加 \(1\)。
  2. Q l r x:询问操作,你需要找到一个位置 \(p\),满足 \(l \le p \le r\),使得:\(a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x\) 最大,输出最大值。

solution

可持久化trie上维护前缀xor,然后就考虑在\(l-1\sim r-1\)的s找到xor\(s_n\oplus x\)的最大异或,然后可持久化trie上维护的r-1版本可以处理1~r-1,但是trie好像不支持可减性,然后就是每个节点记录以当前节点为根的子树中,最后的版本是lst,然后就是子树中lst<l-1就不考虑,否则就正常做

[TJOI2018] 异或

题目描述

现在有一颗以 \(1\) 为根节点的由 \(n\) 个节点组成的树,节点从 \(1\) 至 \(n\) 编号。树上每个节点上都有一个权值 \(v_i\)。现在有 \(q\) 次操作,操作如下:

  • \(1~x~z\):查询节点 \(x\) 的子树中的节点权值与 \(z\) 异或结果的最大值。
  • \(2~x~y~z\):查询节点 \(x\) 到节点 \(y\) 的简单路径上的节点的权值与 \(z\) 异或结果最大值。

solution

首先只有询问,考虑直接分开处理

对于询问1,一个子树内的dfn序连续,就是把树的dfn序搞出来就是上面那题

对于询问2,就考虑分成两条链,然后考虑按照树的父子关系建可持久化trie,也是类似

[THUSC2015] 异或运算

题目描述

给定长度为 \(n\) 的数列 \(X={x_1,x_2,...,x_n}\) 和长度为 \(m\) 的数列 \(Y={y_1,y_2,...,y_m}\),令矩阵 \(A\) 中第 \(i\) 行第 \(j\) 列的值 \(A_{i,j}=x_i\ \operatorname{xor}\ y_j\),每次询问给定矩形区域 \(i∈[u,d],j∈[l,r]\),找出第 \(k\) 大的 \(A_{i,j}\)。(\(n\le1000,m\le300000,p\le500\))

solution

根据数据范围不难猜到需要\(O(pn\log w)\)的复杂度

所以考虑对于一个数x,和一个数列Y如何算第k大,先将数列建成trie,维护左右儿子各有多少数,然后像权值线段树一样处理第k大。若有多个x则每次处理多个(有点像树状数组套线段树)。考虑如何拓展Y

很容易想到把Y持久化,然后考虑左右儿子各有多少数,满足可减性,即可直接处理(并且上面的题也可以使用)

标签:持久,trie,异或,权值,oplus,节点
From: https://www.cnblogs.com/zhy114514/p/18028186

相关文章

  • 在k8S中,一个Pod如何实现数据持久化?数据共享?跨节点Pod如何实现数据共享?
    在Kubernetes(k8S)中,同一个Pod内实现数据持久化和数据共享的方式主要通过使用Volume(卷)来完成。Volume是Kubernetes提供的一种抽象,它代表了宿主机上的一个目录或存储设备,可以被Pod中的一个或多个容器挂载并访问。1.数据持久化:EmptyDir:在Pod创建时自动创建一个空......
  • Object方法 — Object.entries()
    Object方法—Object.entries()Object.entries()方法是JavaScript中的一个静态方法,用于返回一个给定对象自身可枚举属性的键值对数组。该方法接受一个对象作为参数,并将该对象的可枚举属性转换为一个二维数组,其中每个子数组包含两个元素:属性的键和属性的值。返回的数组中的......
  • Rust 编译报 spurious network error (1 tries remaining): [7] Couldn't connect to
    现象:当执行 cargobuild时报类似错误:warning:spuriousnetworkerror(3triesremaining):[7]Couldn'tconnecttoserver(Failedtoconnectto127.0.0.1port8899after2040ms:Couldn'tconnecttoserver);class=Net(12)warning:spuriousnetworkerror......
  • 在k8S中,K8S持久化可以对接哪些储存,为什么要选择它?
    在Kubernetes(k8s)中,持久化存储可以对接多种类型的存储系统,以满足不同场景下的需求。Kubernetes的设计使得它可以与各种云服务提供商的存储解决方案、本地存储系统以及第三方开源或商业存储产品进行集成。以下是一些常见的存储类型:云服务提供商的块存储/卷:AWSEBS(Elastic......
  • DBeaver Public Key Retrieval is not allowed
    最近由于navicat到期了,没续了。打算用用dbeaver。dbeaver是免费和开源(GPL)为开发人员和数据库管理员通用数据库工具。家用完全足够了。但是在配置数据库连接的时候遇到错误:DBeaver连接MySQL提示“PublicKeyRetrievalisnotallowed”。PublicKeyRetrievalisnotallowed......
  • nvm list available 命令执行异常 Could not retrieve https://npm.taobao.org/mirror
    异常:无法连接镜像地址 解决方法在nvm的安装位置找到文件settings.txt,修改镜像地址修改前 修改后保存再次运行命令 ......
  • VOYAGE: 在文档数据库中持久化对象
    VOYAGE:在文档数据库中持久化对象Voyage是由EstebanLorenzano开发的一个小型持久化框架,它是对象和持久化机制之间的一个中间层,通是NoSQL数据库。这本小册子最初是由EstebanLorenzano撰写的一些博客文章,JohanFabry和StéphaneDucasse对这些文章进行了广泛的修改,包括SabineMa......
  • 在涉及恶意软件的任何调查中,寻找持久性点(也称为“自动启动扩展点”或ASEP)是一项经常出
    AutostartcategoriesWhenyoulaunchAutorunsforthefirsttime,allautostartentriesonthesystemaredisplayedinonelonglistontheEverythingtab.As Figure4-8 shows,thedisplayincludesupto19othertabsthatbreakdownthecompletelistint......
  • 01trie
    01trie定义01-trie是字符集为0,1的trie,可以维护异或极值,维护异或和实现主体仍然是trie,维持\(t\)数组记录儿子不变。需要因为异或的性质,所以只需要维护加入0/1边的奇偶性即可,所以添加\(w\)数组记录父节点到该节点的边数。此外因为要统计异或和,所以要在树上统计,用\(xorv......
  • POJ--3764 The xor-longest Path(Trie)
    记录13:562024-2-10找到俩个点,获得最大的边权异或值。利用异或的性质,一个值被异或俩次相当于没有异或即axorbxorb=a所以先从顶点出发,获得每个点路径上的异或值,然后对这俩个值进行异或就获得了他们之间路径的异或值。获取从顶点到每个点路径上的异或值后,可以利用trie来......