2 月 7 日算法练习- 数据结构-树状数组上二分

问题引入

给出三种操作,
0在容器中插入一个数。
1在容器中删除一个数。
2求出容器中大于a的第k大元素。

树状数组的特点就是对点更新,成段求和,而且常数非常小。原始的树状数组只有两种操作,在某点插入一个数和求1到i的所有数的和。

这道题目一共有三种操作,但是实质上其实只有两种:插入和询问。插入操作和删除操作可以视为一种,只不过一个是将标记+1,另一个是-1,而插入的数对应于树状数组的下标,这样就可以在log(n)的时间内完成插入和删除。
求大于a的k大元素,可以通过二分枚举答案来完成,枚举的是当前答案在树状数组中的位置,设为m,然后对v[a+1]- v[m]求和就是小
于等于m的数的个数,这一步可以用树状数组的求和操作来完成,然后根据和k的比较来调整m的位置。询问的复杂度也是log(n)的。

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110000;
int tree[maxn];
int q;int lowbit(int x){return x&-x;
}void add(int pos,int x){while(pos<maxn){tree[pos] += x;pos += lowbit(pos);}return;
}
int query(int pos){int res = 0;while(pos){res+=tree[pos];pos -= lowbit(pos);}return res;
}int find(int a,int k){int l = a+1,r = maxn-1;int ans = -1;while(l<=r){int mid = (l+r)>>1;if(query(mid)-query(a)==k)ans = mid;if(query(mid)-query(a)>=k)r = mid-1;else l = mid +1;}return ans;
}int main( ){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>q;while(q--){int x,y,z;cin>>x;if(x==0){cin>>y;add(y,1);}else if(x==1){cin>>y;if((query(y)-query(y-1))==0)continue;add(y,-1);}else{cin>>y>>z;cout<<find(y,z)<<'\n';}}return 0;
}

算法分析

树状数组+二分复杂度可以比较直接的得到为 nlog2n

修改数组

在这里插入图片描述
思路:利用树状数组+二分。利用树状数组来快速求得区间和从而利用二分来找到第一个大于 i 的数的位置。

#include<iostream>
using namespace std;
const int maxn = 1e5+9;
int a[maxn],vis[maxn],tree[maxn];
int n;int lowbit(int x){return x&-x;
}void add(int k,int x){while(k<maxn){tree[k]+=x;k += lowbit(k);}
}int query(int k){int ans = 0;while(k){ans+=tree[k];k-=lowbit(k);}return ans;
}int main( ){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(!vis[a[i]])vis[a[i]]=1,add(a[i],1);else{int l=a[i],r =maxn,ans = -1;while(l<=r){int mid = (l+r)>>1;if(query(mid)-query(a[i]-1)<mid-a[i]+1)r = mid-1,ans = mid;else l = mid+1;}a[i] = ans;vis[ans]=1;add(ans,1);}}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];return 1;
}

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

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

相关文章

Sublime Text 3配置 Node.js 开发环境

《开发工具系列》 Sublime Text 3配置 Node.js 开发环境 一、引言二、主要内容2.1 初识 Sublime Text 32.2 初识 Node.js2.3 接入 Node.js2.3.1 下载并安装 Node.js2.3.2 环境变量配置 2.4 配置 Node.js 开发环境2.5 编写 Node.js 代码2.6 运行 Node.js 代码 三、总结 一、引言…

Spring Boot3整合Redis

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《spring boot实战》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途。 目录 前置条件 1.导依赖 2.配置连接信息以及连接池参数 3.配置序列化方式 4.编写测试 前置条件 已经初始化好一个spr…

C++,stl,deque容器详解

目录 1.deque容器的构造函数 代码示例&#xff1a; 2.deque的赋值操作 3.deque的大小操作 4.deque的插入和删除 5.deque的数据存取 6.deque的排序操作 1.deque容器的构造函数 代码示例&#xff1a; #include<bits/stdc.h> using namespace std;void print(deque…

Spring Cloud使用ZooKeeper作为注册中心的示例

简单的Spring Cloud应用程序使用ZooKeeper作为注册中心的示例&#xff1a; 1.新建模块&#xff1a; 2.勾选依赖&#xff1a; 3.在pom.xml文件中做出部分修改及添加Spring Cloud Zookeeper 依赖版本&#xff1a; 完整pom文件 <?xml version"1.0" encoding&q…

单片机学习笔记---LED点阵屏的工作原理

目录 LED点阵屏分类 LED点阵屏显示原理 74HC595的介绍 一片74HC595的工作原理 多片级联工作原理 总结 LED点阵屏由若干个独立的LED组成&#xff0c;LED以矩阵的形式排列&#xff0c;以灯珠亮灭来显示文字、图片、视频等。LED点阵屏广泛应用于各种公共场合&#xff0c;如汽…

微信小程序(三十八)滚动容器

注释很详细&#xff0c;直接上代码 上一篇 新增内容&#xff1a; 1.滚动触底事件 2.下拉刷新事件 源码&#xff1a; index.wxml <view class"Area"> <!-- scroll-y 垂直滚动refresher-enabled 允许刷新bindrefresherrefresh 绑定刷新作用函数bindscrollto…

Netty中使用编解码器框架

目录 什么是编解码器&#xff1f; 解码器 将字节解码为消息 将一种消息类型解码为另一种 TooLongFrameException 编码器 将消息编码为字节 将消息编码为消息 编解码器类 通过http协议实现SSL/TLS和Web服务 什么是编解码器&#xff1f; 每个网络应用程序都必须定义如何…

imgaug数据增强神器:增强器一览

官网&#xff1a;imgaug — imgaug 0.4.0 documentationhttps://imgaug.readthedocs.io/en/latest/ github:GitHub - aleju/imgaug: Image augmentation for machine learning experiments. imgaug数据增强神器&#xff1a;增强器一览_iaa 图像增强改变颜色-CSDN博客文章浏览阅…

C++新版本特性

目录: 前言 C11的常用新特性 auto类型推导&#xff1a; auto的限制&#xff1a; auto的应用&#xff1a; decltype类型推导&#xff1a; decltype的实际应用&#xff1a; 使用using 定义别名&#xff1a; 支持函数模板的默认模板参数 : tuple元组&#xff1a; 列表初…

泛型相关内容

1. 什么是泛型 泛型就是定义一种模板&#xff0c;既实现了编写一次&#xff0c;万能匹配&#xff0c;又通过编译器保证了类型安全。 2. 使用泛型 1&#xff09;使用泛型时&#xff0c;把泛型参数<T>替换为需要的class类型&#xff0c;不指定时默认为Obje…

uniapp中配置开发环境和生产环境

uniapp在开发的时候&#xff0c;可以配置多种环境&#xff0c;用于自动切换IP地址&#xff0c;用HBuilder X直接运行的就是开发环境&#xff0c;用HBuilder X发布出来的&#xff0c;就是生产环境。 1.使用HBuilder X创建原生的uniapp程序 选择vue3 2.什么都不改&#xff0c;就…

可达鸭二月月赛——入门赛第四场(周三)题解

可达鸭二月月赛——入门赛第四场&#xff08;周三&#xff09;题解 博文作者&#xff1a;王胤皓 题目&#xff08;可达鸭学员应该能打开&#xff0c;打不开的题解里有题目简述&#xff09;题解(点击即可跳转&#xff0c;里面有我的名字)T1 小可喝水linkT2 \texttt{ }\texttt{ …

06-OpenFeign-使用HtppClient连接池

默认下OpenFeign使用URLConnection 请求连接&#xff0c;每次都需要创建、销毁连接 1、添加ApacheHttpClient依赖 <!-- 使用Apache HttpClient替换Feign原生httpclient--><dependency><groupId>org.apache.httpcomponents</groupId><artifact…

音视频色彩:RGB/YUV

目录 1.RGB 1.1介绍 1.2分类 1.2.1RGB16 1)RGB565 2)RGB555 1.2.2RGB24 1.2.3RGB222 2.YUV 2.1介绍 2.2分类 2.2.1 YUV444 2.2.2 YUV 422 2.2.3 YUV 420 2.3存储格式 2.3.1 YUYV 2.3.2 UYVY 2.3.3 YUV 422P 2.3.4 YUV420P/YUV420SP 2.3.5 YU12 和…

百卓Smart管理平台 uploadfile.php 文件上传漏洞【CVE-2024-0939】

百卓Smart管理平台 uploadfile.php 文件上传漏洞【CVE-2024-0939】 一、 产品简介二、 漏洞概述三、 影响范围四、 复现环境五、 漏洞复现手动复现小龙验证Goby验证 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工…

【Linux】vim的基本操作与配置(上)

Hello everybody!今天我们要进入vim的讲解了。学会了vim,咱们就可以在Linux系统上做一些简单的编程啦&#xff01; 那么废话不多说&#xff0c;咱们直接进入正题&#xff01; 1.初识vim vim是一款多模式的文本编辑器&#xff0c;可以对一个文件进行编辑操作。 它一共有三个模…

Visual Studio 2022中创建的C++项目无法使用万能头<bits/stdc++.h>解决方案

目录 发现问题 解决办法 第一步 第二步 第三步 第四步 最后一步 问题解决 发现问题 如果大家也遇到下面这种问题&#xff0c;可能是没有include文件夹中没有bits/stdc.h 解决办法 第一步 打开一个C项目&#xff0c;鼠标移动至头文件上右击&#xff0c;选择转到文档或…

Docker Compose 构建 LNMP 环境:一站式 PHP 网站部署指南

Docker Compose 构建 LNMP 环境&#xff1a;一站式 PHP 网站部署指南 简介环境准备和安装安装 Docker安装 Docker Compose准备项目目录结构 编写 Docker Compose 文件基础结构配置 Nginx 服务配置 PHP 服务配置 MySQL 服务完整的 docker-compose.yml 示例 Nginx 容器配置创建 N…

微信自动预约小程序开发指南:从小白到专家

随着互联网的发展&#xff0c;小程序已经成为了一个备受欢迎的在线预约平台。本文将详细介绍如何使用第三方制作平台&#xff0c;如乔拓云网&#xff0c;来搭建一个从入门到精通的预约小程序。 首先&#xff0c;我们需要登录乔拓云网&#xff0c;并选择一个适合自己的小程序模板…

PdfFactory Pro软件下载以及序列号注册码生成器

PdfFactory Pro注册机是一款针对同名虚拟打印机软件所推出的用户名和序列号生成器。PdfFactory Pro是一款非常专业的PDF虚拟打印软件&#xff0c;通过使用这款注册机&#xff0c;就能帮助用户免费获取注册码&#xff0c;一键激活&#xff0c;永久免费使用。 pdffactory7注册码如…