ACM 粗心永远AC不了系列——HDU 1754 I Hate It|线段树区间求最值

2024-03-30 04:48

本文主要是介绍ACM 粗心永远AC不了系列——HDU 1754 I Hate It|线段树区间求最值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

线段树应用水题之一

一:线段树基本概念

1:概述

线段树,类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(lgN)!

性质:父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b],线段树需要的空间为数组大小的四倍

2:基本操作(demo用的是查询区间最小值)

线段树的主要操作有:

(1):线段树的构造 void build(int node, int begin, int end);

(2):区间查询int query(int node, int begin, int end, int left, int right);

(3):区间或节点的更新 及 线段树的动态维护update (这是线段树核心价值所在,节点中的标记域可以解决N多种问题)

动态维护需要用到标记域,延迟标记等。

3:主要应用

(1):区间最值查询问题 (见模板1)

(2):连续区间修改或者单节点更新的动态查询问题 (见模板2)

(3):多维空间的动态查询 (见模板3)

具体线段树ACM情况可以参看转载博客:数据结构专题——线段树

题目来源:I Hate It

ac代码:

#pragma warning(disable:4996)  
#include <stdio.h>  
#include <algorithm>
using namespace std;
#define MAXN 200000 + 10
int a[MAXN];
struct Node
{int l = 0, r = 0, v = 0;
}tree[800010];//注意数组一定要开大,之前开了400010,结果愣是超时,改了20+次才发现数组开的不够大,粗心
void build(int i, int l, int r) {tree[i].l = l;tree[i].r = r;if (l == r){tree[i].v = a[l];return;// 叶子节点退出}int mid = (r + l) >> 1;build(i << 1, l, mid);// 建立左子树 数组完全二叉树 i*2==i<<1build(i << 1 | 1, mid + 1, r);// 建立右子树 数组完全二叉树 i*2+1==i<<1|1tree[i].v = max(tree[i << 1].v, tree[i << 1 | 1].v);
}
void update(int num, int x, int v) {if (tree[num].l == x && tree[num].r == x) {tree[num].v = v;return;}int mid = (tree[num].l + tree[num].r) >> 1;if (x > mid)update(num << 1 | 1, x, v);elseupdate(num << 1, x, v);tree[num].v = max(tree[num << 1].v, tree[num << 1 | 1].v);
}
int query(int i, int left, int right) {if (tree[i].l == left && tree[i].r == right) {return tree[i].v;}int mid = (tree[i].l + tree[i].r) >> 1;if (right <= mid)return query(i << 1, left, right);else if (left >= mid + 1)return query(i << 1 | 1, left, right);else {int le = query(i << 1, left, mid);int ri = query(i << 1 | 1, mid + 1, right);return max(le, ri);}
}
int main()
{int n, m;char s[5];while (~scanf("%d%d", &n, &m)){for (int i = 1; i <= n; ++i){scanf("%d", a + i);}build(1, 1, n);for (int i = 0; i < m; ++i){scanf("%s", s);int a, b;scanf("%d%d", &a, &b);if (s[0] == 'Q')printf("%d\n", query(1, a, b));else if (s[0] == 'U')update(1, a, b);}}return 0;
}





这篇关于ACM 粗心永远AC不了系列——HDU 1754 I Hate It|线段树区间求最值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/860508

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl