首页 > 其他分享 >最大异或和 可持久化数据结构入门

最大异或和 可持久化数据结构入门

时间:2024-01-19 16:02:15浏览次数:33  
标签:xor 入门 lastest trie int 异或 read 数据结构

最大异或和

题目描述

给定一个非负整数序列 \(\{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\) 最大,输出最大值。

输入格式

第一行包含两个整数 \(N, M\),含义如问题描述所示。
第二行包含 \(N\) 个非负整数,表示初始的序列 \(A\)。
接下来 \(M\) 行,每行描述一个操作,格式如题面所述。

输出格式

假设询问操作有 \(T\) 个,则输出应该有 \(T\) 行,每行一个整数表示询问的答案。

样例 #1

样例输入 #1

5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4
Q 5 7 0 
Q 3 6 6

样例输出 #1

4
5
6

提示

  • 对于所有测试点,\(1\le N,M \le 3\times 10 ^ 5\),\(0\leq a_i\leq 10 ^ 7\)。

原题链接

trie树我现在感觉最大的作用就是异或和这种东西了

这题有几个值得注意的地方
1.连续的异或和,可以用类似前缀异或和的东西来转化为单点的查询。
这个和树状数组很像
2.“历史版本”的作用。
这个其实就是可持久化的作用,主要是分析什么样子的问题可以被转化为可持久化维护。
这个是要一直总结的,之后还有各种可持久化的数据结构。

异或有一个abb=a的性质,挺重要的。这题就要用上。

我们设\(s[i]\)表示序列\(a\)的前\(i\)个数\(xor\)起来得到的结果。
\(s[0]=0\),则查询的东西\(a[p]\ xor\ a[p+1]\ xor...\ xor\ a[n]\ xor\ x=s[p-1]\ xor\ s[n]\ xor\ x\)
所有我们只需要维护\(s[]\)即可
对于添加操作,数组\(s\)很容易维护。
则对于询问,问题变为,已知\(val=s[N]\ xor\ x\),求一个数字\(p\in [l-1,r-1]\)使得\(s[p]\ xor\ s[n]\ xor\ x\)最大

额,插一句理解。
可持久化01trie树的特点是能够把历史状态们放在一起比较,所以把要比较的东西放在一起才是要做的。
我们把这个题目转化后,其实要比较的东西就是很好的了。只是两个数字xor的大小。
这个可是01trie树的专场啊。

假如是没有限制的,那就是每次在查询的时候,往最后面添加一个\(s[n]\ xor\ x\),然后再这个trie树上找最大。
如果有\(p\leq r-1\)的限制,那么就是在r-1版本的trie树上查找就好了,就是可持久化。
如果有\(l-1\leq p\)的限制,那就添加一个节点信息\(end[x]\)信息,表示这个是第几个二进制数字的结尾。如果不是结尾让它\(end=-1\)
然后再用一个\(lastest\)表示这个子树里面最大的\(end\)值,然后从\(root[r-1]\)节点出发寻找的时候,仅考虑\(lastest\geq l-1\)的点即可

为什么只有这一维能用这个办法统计呢?
或者说,为什么\(p\leq r-1\)需要用可持久化?
哦哦,就像你不能用线段树来统计区间内有几个数字\(=0\)一样,你要怎么来用两个数字来表示这个区间里面有没有数字再这个区间呢
(要是能的话,你用这个办法写二位偏序也太爽了吧)

嘶,我第二天又想了想,到底是不是因为这个所以才要用可持久化的啊。哦哦,我又蠢了,我之前想的是对的。

我趣,那可持久化数据结构不久这个作用了?
在时间复杂度不变和空间复杂度略微增加的情况下,维护历史版本。
但是只支持单点修改,区间修改不太行。
而历史版本的作用其实是一个偏序,这样再带上一个节点信息可以做到维护区间的一些信息。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
	char c=getchar();int a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
const int N=600010;
int trie[N*24][2],lastest[N*24];
int s[N],root[N],n,m,tot;
void insert(int i,int k,int p,int q)//第几次修改,当前在这个数字的第几位,现在在上一颗树的哪个节点,在这棵树的哪个节点 
{
	if(k<0)
	{
		lastest[q]=i;
		return;
	}
	int c=s[i]>>k&1;
	if(p)trie[q][c^1]=trie[p][c^1];//把和这个路径没有关系的节点复制过去 
	trie[q][c]=++tot;
	insert(i,k-1,trie[p][c],trie[q][c]);
	lastest[q]=max(lastest[trie[q][0]],lastest[trie[q][1]]);
}
int ask(int now,int val,int k,int limit)//查询 
{
	if(k<0)return s[lastest[now]]^val;
	int c=val>>k&1;
	if(lastest[trie[now][c^1]]>=limit)
		return ask(trie[now][c^1],val,k-1,limit);
	else
		return ask(trie[now][c],val,k-1,limit);
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read();
	lastest[0]=-1;
	root[0]=++tot;
	insert(0,23,0,root[0]);
	for(int i=1;i<=n;i++)
	{
		int x=read();
		s[i]=s[i-1]^x;
		root[i]=++tot;
		insert(i,23,root[i-1],root[i]);
	}
	for(int i=1;i<=m;i++)
	{
		char c;
		cin>>c;
		if(c=='A')
		{
			int x=read();
			root[++n]=++tot;
			s[n]=s[n-1]^x;
			insert(n,23,root[n-1],root[n]);
		}
		else
		{
			int l=read(),r=read(),x=read();
			cout<<ask(root[r-1],x^s[n],23,l-1)<<endl;
		}
	}
	return 0;
}

标签:xor,入门,lastest,trie,int,异或,read,数据结构
From: https://www.cnblogs.com/HLZZPawa/p/17974845

相关文章

  • 数据结构——线段树 入门以后 学习笔记
    数据结构——线段树入门以后学习笔记入门笔记有时间写。才发现我不会线段树。/ll可以看出来我很喜欢class/cf有的代码需要前置:usingll=longlong;constexprllmod=998244353;constexprintroot=1;P3372线段树1classseg_t{private:structemm{......
  • 若依框架入门一源码分析一登录验证码
    若依框架入门一源码分析一关于登录页面的验证码问题前端页面的验证码开关设置的是true,但是打开画面验证码没有被显示,原因是后端代码判断了redis中是否有值,有则覆盖前端<el-form-itemprop="code"v-if="captchaEnabled"><el-inputv-model="loginForm......
  • PostgreSQL从入门到精通教程 - 第42讲:pg_rman部署与使用
       PostgreSQL从小白到专家,是从入门逐渐能力提升的一个系列教程,内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容,希望对热爱PG、学习PG的同学们有帮助,欢迎持续关注CUUGPG技术大讲堂。 第42讲:pg_rman部署与使用 PostgreSQL第42讲:1月20日......
  • 二叉树 - 二叉树入门题
    二叉树入门题1.判断两颗树是否相同classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){//如何判断两颗树是否相同?根相同+左右子树相同//如何判断根相同?结构+值相同if(p==null&&q!=null||p!=null&&......
  • 这才是你应该了解的Redis数据结构!
    深入了解Redis数据结构Redis,作为一种高性能的内存数据库,支持多种数据结构,从简单的字符串到复杂的哈希表。在这篇博文中,我们将深入探讨Redis的一些主要数据结构,并通过详细的例子展示它们的使用。1.字符串(String)1.1存储和获取Redis中的字符串是二进制安全的,可以存储任何数......
  • Python编程语法零基础入门
    0.开始前了解#号是一行注释"""6个"是多行注释"""#--coding:UTF-8print(u"你好!")#中文加上u转为unicode显示,不然会显示乱码1.基础语法和概念#(1)基本数据结构(整型、浮点型、字符串、布尔型)#格式:name=value没有分号、编译器自动匹配类型int_num=10float_num=......
  • kafka入门(八):副本
    副本kafka副本之间是一主多从的关系。其中leader副本负责处理读写请求,follower副本只负责与leader副本的消息同步。副本处于不同的broker中,当leader副本出现故障时,从follower副本中重新选举新的leader副本对外提供服务。kafka通过多副本机制实现了故障的自动转......
  • 普普通通入门js案例(原生)
    数组中数据的遍历 vararr=[34,3,4,3]; for(i=0;i<arr.length;i++){ console.log(arr[i]); }求数组中的最大值 vararr=[34,3,4,3]; max=arr[0]; for(i=1;i<arr.length;i++){ if(max<arr[i]){ max=arr[i]; } }求数组中的平......
  • mysql8.0索引数据结构
    1、为什么使用索引假如给数据使用二叉树这样的数据结构进行存储,如下图所示2、索引及其优缺点2.1、索引概述2.2、优点(1)类似大学图书馆建书目索引,提高数据检索的效率,降低数据库的IO成本,这也是创建索引最主要的原因。(2)通过创建唯一索引,可以保证数据库表中每一行数据的唯一性......
  • day 02java入门之Hello.java
    java命令行执行(注意代码编写用GBK,命令行窗口用GBK进行解析)注意public类名要和文件名一致,一个.java文件中最多只有一个public类java注意事项一个.java文件中若含有多个类时,编译完成后会生成相应个数的.class文件......