acwing算法提高之数据结构--可持久化数据结构

目录

  • 1 介绍
  • 2 训练

1 介绍

本专题用来记录可持久化数据结构相关的题目。

本专题主要讲如下两类数据结构的可持久化:

  1. trie的可持久化
  2. 线段树的可持久化,即主席树

可持久化的前提:本身的拓扑的结构不变

解决什么类型的问题:可以保存下来数据结构的所有历史版本。
核心思想:只记录每一个版本与前一个版本不同的结点。

2 训练

题目1:256最大异或和

C++代码如下,

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 600010, M = N * 25;int n, m;
int s[N];
int tr[M][2], max_id[M];
int root[N], idx;void insert(int i, int k, int p, int q) {if (k < 0) {max_id[q] = i;return;}int v = s[i] >> k & 1;if (p) tr[q][v^1] = tr[p][v^1];tr[q][v] = ++idx;insert(i, k-1, tr[p][v], tr[q][v]);max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}int query(int root, int C, int L) {int p = root;for (int i = 23; i >= 0; --i) {int v = C >> i & 1;if (max_id[tr[p][v^1]] >= L) p = tr[p][v^1];else p = tr[p][v];}return C ^ s[max_id[p]];
}int main() {scanf("%d%d", &n, &m);max_id[0] = -1;root[0] = ++idx;insert(0, 23, 0, root[0]);for (int i = 1; i <= n; ++i) {int x;scanf("%d", &x);s[i] = s[i-1] ^ x;root[i] = ++idx;insert(i, 23, root[i-1], root[i]);}char op[2];int l, r, x;while (m--) {scanf("%s", op);if (*op == 'A') {scanf("%d", &x);n++;s[n] = s[n-1] ^ x;root[n] = ++idx;insert(n, 23, root[n-1], root[n]);} else {scanf("%d%d%d", &l, &r, &x);printf("%d\n", query(root[r-1], s[n]^x, l-1));}}return 0;
}

题目2:255第K小数

C++代码如下,

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 100010, M = 10010;int n, m;
int a[N];
vector<int> nums;struct Node {int l, r;int cnt;
}tr[N * 4 + N * 17];int root[N], idx;int find(int x) {return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}int build(int l, int r) {int p = ++idx;if (l == r) return p;int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);return p;
}int insert(int p, int l, int r, int x) {int q = ++idx;tr[q] = tr[p];if (l == r) {tr[q].cnt++;return q;}int mid = l + r >> 1;if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);else tr[q].r = insert(tr[p].r, mid + 1, r, x);tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;return q;
}int query(int q, int p, int l, int r, int k) {if (l == r) return r;int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;int mid = l + r >> 1;if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);nums.push_back(a[i]);}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());root[0] = build(0, nums.size() - 1);for (int i = 1; i <= n; ++i) {root[i] = insert(root[i-1], 0, nums.size() - 1, find(a[i]));}while (m--) {int l, r, k;scanf("%d%d%d", &l, &r, &k);printf("%d\n", nums[query(root[r], root[l-1], 0, nums.size() - 1, k)]);}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2998780.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【笔试训练】day14

1.乒乓球框 思路&#xff1a; 无思路 代码&#xff1a; #include <iostream> using namespace std;int main() {string a;string b;int mp[26]{0};cin>>a>>b;for(int i0;i<b.size();i){int ub[i]-A;mp[u];}for(int i0;i<a.size();i){int ua[i]-A;mp…

【TDengine】mac m1解决no taos in java.library.path

前言 使用macos搭建springbootmybatisplus&#xff0c;通过mqtt将数据更新到tdenigne 3.2.3&#xff0c;数据源使用远程服务器的tdengine。 问题 启动时报错&#xff1a; Caused by: java.lang.UnsatisfiedLinkError: no taos in java.library.path 以下是官方文档 打开本…

opencv_23_高斯模糊

void ColorInvert::gaussian_blur(Mat& image) { Mat dst; GaussianBlur(image, dst, Size(0, 0), 15); // Size(2, 2), imshow("图像模糊2", dst); }

Docker-compose的介绍与用法

Docker-compose Docker Compose 是一个开源的容器编排工具&#xff0c;由 Docker 官方开发。它允许开发者定义一个或多个 Docker 容器作为单个服务&#xff0c;并将这些服务组合成一个项目。这些定义被保存在一个 YAML 文件中&#xff0c;称为 docker-compose.yml。 使用 Dock…

什么是DDoS攻击?怎么防御DDoS攻击?

在网络安全领域&#xff0c;DDoS攻击一直是热门话题&#xff0c;随着网络技术的不断发展和网络环境的复杂化演变&#xff0c;DDoS攻击变得愈加频繁、更具破坏性。根据2023年网络安全态势研判分析年度综合报告&#xff0c;全年全网网络层的DDoS攻击次数达2.51亿次&#xff01;本…

【开发工具】pythontutor——在线内存可视化工具

笔者在学习RISC-V时&#xff0c;希望找到一款可视化的内存工具&#xff0c;遗憾目前还未找到。发现了pythontutor这个网站&#xff0c;可以对C、python等多种语言进行内存可视化。结果似乎是x86架构的&#xff0c;符合小端存储。 贴一下网址&#xff0c;原准备依据开源版本进行…

Rethinking Reconstruction Autoencoder-Based Out-of-Distribution Detection

Rethinking Reconstruction Autoencoder-Based Out-of-Distribution Detection 摘要1引言2相关工作3前提4方法摘要 在某些场景中,分类器需要检测远离其训练数据的分布外样本。具有理想的特性,基于重构自动编码器的方法通过使用输入重构误差作为新颖性与正常性的度量来解决这…

用什么模型算法可以预测足球胜平负

预测足球胜平负的模型算法有很多种&#xff0c;每种算法都有其特点和适用场景。以下是一些常见的模型算法&#xff1a; Elo预测法&#xff1a; 这是一种通过研究主客场球队在比赛前的积分情况来预测胜负的方法。Elo预测法通过计算两队之间的积分差&#xff0c;根据特定的公式&…

React配置@别名路径配置

1. 背景知识 路径解析配置&#xff08;webpack&#xff09;&#xff0c;把 / 解析为 src/路径联想配置&#xff08;VsCode&#xff09;&#xff0c;VsCode 在输入 / 时&#xff0c;自动联想出来对应的 src/下的子级目录 2. 路径解析配置 配置步骤&#xff1a; 安装craco npm …

搭建MongoDB副本集

文章目录 一、什么是MongoDB的副本集二、副本集的架构三、副本集的成员四、部署副本集1、节点划分2、安装MongoDB2.1、下载解压安装包 3、创建主节点3.1、创建存储数据和日志的目录3.2、新建配置文件3.3、启动节点服务 4、创建副本节点4.1、创建存储数据和日志的目录4.2、新建配…

MVC架构简述

MVC简介 MVC 是一种非常常见且常用的分层架构&#xff0c;主要包括&#xff1b;M - mode 对象层&#xff0c;封装到 domain 里。V - view 展示层&#xff0c;但因为目前都是前后端分离的项目&#xff0c;几乎不会在后端项目里写 JSP 文件了。C - Controller 控制层&#xff0c…

​基于Python的在线自主评测系统(django)​

基于Python的在线自主评测系统(django) 开发语言:Python 数据库&#xff1a;MySQL所用到的知识&#xff1a;Django框架工具&#xff1a;pycharm、Navicat、Maven 学生功能模块的实现 学生注册的实现 学生登录界面首页 在线考试界面 考试成绩查看界面 教师功能模块的实现 新建…

学生管理系统[Python语言]

各位大佬好 &#xff0c;这里是阿川的博客 &#xff0c; 祝您变得更强 个人主页&#xff1a;在线OJ的阿川 大佬的支持和鼓励&#xff0c;将是我成长路上最大的动力 阿川水平有限&#xff0c;如有错误&#xff0c;欢迎大佬指正 学生管理系统是计算机专业最基础的一个作业&#…

基于ESP32—CAM物联网WIFI小车

一.功能概述 摄像头的画面可以实时的传输到&#xff0c;点灯科技APP的手机端&#xff0c;这样可以实时查看周围环境的状况&#xff0c;灯光不足&#xff0c;画面不清晰时可以打开灯光照明。手机端有左转、右转、前进、后退、停止的按钮。可以根据自己需要&#xff0c;来控制小车…

南京航空航天大学用契约锁让校园业务盖章“腾出手”、办事更便捷

南京航空航天大学&#xff08;以下简称“南航”&#xff09;创建于1952年&#xff0c;是国家“双一流”建设高校&#xff0c;国家“211工程”、“985工程优势学科创新平台”重点建设高校之一&#xff0c;同时也是新中国自己创办的第一批航空高等院校之一。 创新高校网上签字盖…

Vitis HLS 学习笔记--Schedule Viewer 调度查看器

目录 1. 简介 2. Schedule Viewer详解 2.1 视图说明 2.1.1 Operation\Control Step 2.1.2 周期关系图 2.1.3 Schedule Viewer 菜单栏 2.1.4 属性视图 2.2 内容说明 2.2.1 实参&#xff08;b&#xff09;解释 2.2.2 实参&#xff08;a&#xff09;解释 2.2.3 变量&am…

一、初识Django

简介 Django 是一个用于构建 Web 应用程序的高级 Python Web 框架。 版本对应 不同版本的django框架是基于特定的不同的python版本开发的&#xff0c;所以不同版本的django框架要正常执行功能只能安装特定的python版本 Django安装 安装 Django # 全局安装 pip install dj…

第一个Cython程序-helloworld

Cython是Python的一个模块&#xff0c;可以将python语言“翻译”成C语言。 如何安装&#xff1f; python -m pip install Cython -i https://pypi.tuna.tsinghua.edu.cn/simple/ 新建两个文件helloworld.pyx和setup.py。 helloworld.pyx print("hello world")setu…

MySQL中SELECT语句的执行过程

2.1.1. 一条SELECT语句的执行过程 MySQL 的架构共分为两层&#xff1a;Server 层和存储引擎层 Server层负责建立连接、分析和执行SQL存储引擎层负责数据的存储和提取&#xff0c;支持 InnoDB、MyISAM、Memory 等多个存储引擎&#xff0c;MySQL5.5以后默认使用InnoDB&#xff0…

一个单例模式中使用std::unique_ptr引起的莫名其妙的COFF损坏的问题(未解决)

使用static std::unique_ptr和static std::shared_ptr都不行struct IElementAgendaEvents {//! Called to allow listeners to modify the agenda by adding/removing entries before applying tool operation. Return true if entries added or invalidated.virtual bool …