蓝桥杯重要考点—树状数组

树状数组经典操作

1、修改某一段区间的值   add

2、求某一段区间的前缀和  sum

int lowbit(int x){
    return x & -x;
}

int add(int x, int c){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x){
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}

例题:

第一题:楼兰图腾

在完成了分配任务之后,西部314 来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(V),一个部落崇拜铁锹(),他们分别用 V 和  的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了 n 个点,经测量发现这 n 个点的水平位置和竖直位置是两两不同的。

西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关,因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn),其中 y1∼yn 是 1 到 n 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n且 yi>yj,yj<yk,则称这三个点构成 V 图腾;

如果三个点 (i,yi),(j,yj),(k,yk)满足 1≤i<j<k≤n 且 yi<yj,yj>yk,则称这三个点构成  图腾;

西部 314 想知道,这 n个点中两个部落图腾的数目。

因此,你需要编写一个程序来求出 V 的个数和  的个数。

输入格式

第一行一个数 n。

第二行是 n 个数,分别代表 y1,y2,…,yn

输出格式

两个数,中间用空格隔开,依次为 V 的个数和  的个数。

数据范围

对于所有数据,n≤200000,且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。

输入样例:

5
1 5 3 2 4

输出样例:

3 4

分析样例,我们就知道是找当前点 前面比他大的 乘以 后面也比他大的 ,两个数量相乘即是V个数

同理倒的也是如此

那我们从前面求一遍,再从后面求一遍即可

怎么与树状数组相关呢,每次加进去 add(y, 1), 因为是全排列,加进去的就是当前的位置和个数

要求的就是前面位置 或者后面位置 的数量,这就是sum了

求前面比他大的,不就是求 sum(n) - sum(y) ,也就是  y  + 1 ——n的个数

再初始化树状数组为0,反过来加一遍,就相当于反过来求

#include<iostream>
#include<cstring>
using namespace std;

const int N = 200010;
typedef long long LL;
int n;
int great[N], lower[N], tr[N], a[N];

int lowbit(int x){
    return x & -x;
}

int add(int x, int c){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x){
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++){
        int y = a[i];
        great[i] = sum(n) - sum(y);   //正着求 y + 1 到 n
        lower[i] = sum(y - 1);        //      1 到 y - 1
        add(y, 1);
    }
    
    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for(int i = n; i ; i --) {
        int y = a[i];
        res1 += great[i] * (LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)sum(y - 1);
        add(y, 1);
    }
    
    printf("%lld %lld", res1, res2);
    return 0;
}

第二题:一个简单的整数问题

给定长度为 N 的数列 A然后输入 M 行操作指令。

第一类指令形如 C l r d,表示把数列中第 l∼r个数都加 d。

第二类指令形如 Q x,表示询问数列中第 x 个数的值。

对于每个询问,输出一个整数表示答案。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数 A[i]。

接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。

输出格式

对于每个询问,输出一个整数表示答案。

每个答案占一行。

数据范围

1≤N,M≤105
|d|≤10000
|A[i]|≤109

输入样例:

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例:

4
1
2
5

这道题就很经典了

如果你用差分去求的话,每次修改完之后重新就要求前缀和,为O(n)级别肯定超时

但是使用树状数组维护前缀和,只需要O(logn)

要加以进去的就是差分数组,add(i, a[i] - a[i- 1])

树状数组维护的是前缀和,求某一个数,就是sum(x)

#include<iostream>
using namespace std;

const int N = 100010;
typedef long long LL;
int n, m;
int a[N], tr[N];

int lowbit(int x){
    return x & -x;
}

void add(int x, int c){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        add(i, a[i] - a[i - 1]);
    }
    
    while(m--){
        string op;
        int l, r, d;
        cin>>op;
        scanf("%d", &l);
        if(op == "C") {
            scanf("%d%d", &r, &d);
            add(l, d), add(r + 1,  -d);
        }
        else{
            printf("%d\n", sum(l));
        }
    }
    
    return 0;
}

第三题:一个简单的整数问题2

还需思考,待更..

第四题:谜一样的牛

有 n头奶牛,已知它们的身高为 1∼n且各不相同,但不知道每头奶牛的具体身高。

现在这 n 头奶牛站成一列,已知第 i 头牛前面有 Ai 头牛比它低,求每头奶牛的身高。

输入格式

第 1 行:输入整数 n。

第 2..n 行:每行输入一个整数 Ai,第 i 行表示第 i 头牛前面有 Ai 头牛比它低。
(注意:因为第 1 头牛前面没有牛,所以并没有将它列出)

输出格式

输出包含 n 行,每行输出一个整数表示牛的身高。

第 i 行输出第 i 头牛的身高。

数据范围

1≤n≤105

输入样例:

5
1
2
1
0

输出样例:

2
4
5
3
1

每一只牛发现前面比他低的牛,模拟样例得到

从最后开始模拟,第ai头牛,找当前数组第ai + 1小的数 就是当前牛的身高

涉及两个操作

1、找到了,删除某头牛

2、找到该位置,第 ai + 1比他小的数

第一个在树状数组里面很好解决

第二个把树状数组初始化为1,表示该位置可以使用,sum(k) == ai + 1表示当前位置身高为k(身高为1-n),怎么找这个k,使用二分,满足二段性的

#include<iostream>
using namespace std;

const int N = 100010;
typedef long long LL;
int h[N], tr[N], ans[N];
int n;

int lowbit(int x){
    return x & -x;
}

void add(int x, int c){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x){
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d", &n);
    
    for(int i = 2; i <= n; i ++) scanf("%d", &h[i]);
    
    for(int i = 1; i <= n; i ++) tr[i] = lowbit(i);
    
    for(int i = n; i; i--){
        int k = h[i] + 1;
        int l = 1, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = r;
        add(r, -1);
    }
    
    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

全网最详细的UI自动化测试元素定位方法总结

目录 前言 元素定位概述 常用的元素定位器 元素定位方法 元素定位技巧 总结 前言 UI自动化测试是软件测试中的一个重要环节&#xff0c;它可以通过模拟用户的实际操作&#xff0c;自动化执行UI界面上的测试用例&#xff0c;以提高测试效率和准确性。元素定位是UI自动化测…

卡尔曼滤波浅析

文章目录前言任务状态预测外部影响因素外部不确定性状态更新利用测量进一步修正状态合并两个高斯分布公式汇总图形化解释总结&#xff08;readme&#xff09;references前言 Kalman Filter算法&#xff0c;是一种递推预测滤波算法&#xff0c;算法中涉及到滤波&#xff0c;也涉…

数据更新 | CnOpenData法拍房数据

法拍房数据 一、数据简介 法拍房&#xff0c;即“法院拍卖房产”&#xff0c;是被法院强制执行拍卖的房屋 。当债务人&#xff08;业主&#xff09;无力履行借款合约或无法清偿债务时&#xff0c;而被债权人经司法程序向法院申请强制执行&#xff0c;将债务人名下房屋拍卖&…

sql注入靶场练习

文章目录Less-1Less-2Less-3Less-4Less-5Less-6Less-7Less-8Less-9Less-10Less-11Less-12Less-13Less-14Less-15Less-16Less-17less-18Less-19Less-20Less-1 union没有被过滤&#xff0c;先试出来长度。 ?id1orderby3%23 ?id1orderby4%23到4时&#xff0c;发现 然后再试出来…

JVM与Java体系

JVM体系跟着尚硅谷的康师傅学习 JVM内存与垃圾回收概述 除了大部分的Java开发 人员&#xff0c;除了会在项目中使用到与Java平台相关的框架&#xff0c;与API&#xff0c;对于Java的虚拟机了解甚少。但是也需要我们知道如何处理OOM&#xff0c;SOF异常&#xff0c;除了…

Java实现一个简单的东南西北中的面板

目录 一、前言 二、代码部分 1.代码 三、程序运行结果&#xff08;面板弹出&#xff09; 四、涉及到的知识点代码 一、前言 1.本代码是我在上学时写的&#xff0c;有一些地方没能完美实现&#xff0c;请包涵也请多赐教&#xff01; 2.本弹窗界面可以根据简单的要求进行…

字节跳动CVPR 2023论文精选来啦(内含一批图像生成新研究)

计算机视觉领域三大顶会之一的 CVPR 今年已经开奖啦。 今年的 CVPR 将于六月在加拿大温哥华举办&#xff0c;和往年一样&#xff0c;字节跳动技术团队的同学们收获了不少中选论文&#xff0c;覆盖文本生成图像、语义分割、目标检测、自监督学习等多个领域&#xff0c;其中不少…

Linux 中yum获取的的详细步骤

**1.yum的作用 可以帮我们管理RPM包 可以帮我们安装软件&#xff0c; 如果软件有其他依赖&#xff0c;会帮我们安装依赖后在安装软件 类似于Maven 2.yum命令 search 查询命令或者软件 info 查看包的信息 list / list jdk 查询安装的rpm包&#xff0c;或者只查询某一周 3.更换yu…

【Paper】2016_基于LQR的多智能体系统协同最优控制_姚蒙

姚蒙. 基于LQR的多智能体系统协同最优控制[D].华南理工大学,2016. 文章目录第四章 线性离散时间多智能体系统协同最优控制4.1 引言4.2 离散时间多智能体系统一致最优控制4.3 离散时间领导者-跟随者系统跟踪最优控制4.4 数值仿真Ref第四章 线性离散时间多智能体系统协同最优控制…

HttpRunner3.x(7) hook函数

目录 调用 hook 函数 测试用例层面&#xff08;testcase&#xff09;-3.1.11不支持 测试步骤层面&#xff08;teststep&#xff09; 编写hook函数 请求request预处理 返回 response 处理 HttpRunner 从 1.4.5 版本开始实现了全新的 hook 机制&#xff0c;可以在请求前和请…

JavaSE——方法的使用

目录 一、方法的概念及使用 1、什么是方法(method) 2、方法定义 3、方法调用的执行过程 4、实参和形参的关系 二、方法重载 1、为什么需要方法重载 2、方法重载概念 3、方法签名 三、递归 1、递归的概念 2、递归执行过程分析 3、递归练习 一、方法的概念及使用 1、…

Java 你还在用lsit.contain做去重? 你是故意的还是不小心的?

前言 最近又是一轮代码review , 发现了一些实现去重的代码&#xff0c;在使用 lsit.contain ...... 如&#xff1a; 我沉思&#xff0c;是不是其实很多初学者也存在这种去重使用问题&#xff1f; 所以我选择把这个事情整出来&#xff0c;分享一下。 正文 首先是造出一个 List&l…

Linux基础教程

Linux 目标 ​ Linux概述【了解】 ​ Linux网络连接三种模式【了解】 Linux目录结构【掌握】 Linux常用命令【掌握】 Linux操作目录的命令【掌握】 Linux操作文件的命令【掌握】 Linux的Vi编辑器【会用】 Linux打包与解压命令【掌握】 一、Linux概述 1、Linux的概述…

动力节点王鹤SpringBoot3学习笔记——第五章 说说Web服务

目录 第五章 说说Web服务 5.1 高效构建Web应用 5.1.1 html页面视图 5.1.2 JSON视图 5.1.3 给项目加favicon 5.2 Spring MVC 5.2.1 控制器Controller 5.2.1.1 匹配请求路径到控制器方法 5.2.1.2 RequestMapping 5.2.1.3 控制器方法参数类型与可用返回值类型 5…

HashMap底层数据结构

TreeMap TreeMap的底层是红黑树&#xff0c;是自平衡的二叉查找树。 在查找元素时会从左子树或右子树查找&#xff0c;和元素一个一个进行比较&#xff0c;对于大数量的查找的场景TreeMap不适合&#xff08;HashMap解决了这个问题&#xff09;。 TreeMap的好处&#xff0c;是…

隐私计算 FATE - 多分类神经网络算法测试

一、说明 本文分享基于 Fate 使用 横向联邦 神经网络算法 对 多分类 的数据进行 模型训练&#xff0c;并使用该模型对数据进行 多分类预测。 二分类算法&#xff1a;是指待预测的 label 标签的取值只有两种&#xff1b;直白来讲就是每个实例的可能类别只有两种 (0 或者 1)&…

两个数组的交集(力扣刷题)

给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetcode.cn/problems/intersection-of-two-arrays 说…

人大女王金融硕士——站在一个更高的起点,拓宽自己的眼界

俗话说&#xff1a;“视野所及&#xff0c;心之所止”。做任何事情&#xff0c;最重要的是眼光。眼界不一样&#xff0c;就会有不一样的人生。站得更高才能看得更远&#xff0c;看得更远才能收获更多。人民大学与加拿大女王大学金融硕士项目为我们提供在职读研平台&#xff0c;…

Python机器学习:最大熵模型

信息论里&#xff0c;熵是可以度量随机变量的不确定性的&#xff0c;已经证明的&#xff1a;当随机变量呈均匀分布的时候&#xff0c;熵值最大&#xff0c;一个有序的系统有着较小的熵值&#xff0c;无序系统的熵值则较大。 机器学习里面&#xff0c;最大熵原理假设&#xff1…

【HAL库】HAL库STM32cubemx快速使用

文章目录整体框图一、基础工程1 新建工程2 配置RCC3 配置SYS4 工程设置5 生成代码6 keil设置下载&复位二、必备外设1 目录规范2 LED2 RTC3 USART4 KEY三、其他外设1 OLED&#xff08;模拟IIC、模拟SPI&#xff09;2 BH1750光强检测3 MQ2烟雾检测3 MQ4甲醛检测4 DHT11温湿度…
最新文章