区间专题
hdu 1754 I Hate It（线段树，单点更新，区间最值）
题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
hdu4267区间统计
题意：给一些数，有两种操作，一种是在[a,b] 区间内，对（i - a）% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import
hdu4417区间统计
给你一个数列{An}，然后有m次查询，每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead
hdu3333区间统计
题目大意：求一个区间内不重复数字的和，例如1 1 1 3，区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
【uva】11536-Smallest Sub-Array（区间移动问题）
一个区间移动的问题，1A了，感觉没什么好说的。。 13975926 11536 Smallest Sub-Array Accepted C++ 0.809 2014-08-01 11:00:20 #include<cstdio>#include<cstring>#include<iostream>using namespace std;#define INF 1 << 30
【hdu】Just a Hook（线段树区间修改）
线段树模板题，练的是懒惰标记。 懒惰标记，就是更新一段区间的时候，如果小区间被包含在了所需要更新的区间里面，那么直接对代表这个区间的数组元素赋值，之后做一个标记（表示这个区间的子区间都需要更新）但是不继续递归（这样可以节省很多的时候）。 116571152014-09-15 14:17:26Accepted1698796MS2380K1750 BG++KinderRiven #
【hdu】I Hate It（线段树，结点修改求区间最大值）
线段树的模板题，还是二分递归。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>#incl
【hdu】敌兵布阵（线段树，更加结点，区间求和）
最近开始刷线段树，主要围绕notonlysuccess的线段树总结刷。 结点修改还是比较简单的，不需要什么懒惰标记，直接二分递归就可以了。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vecto
ZOJ 3324 Machine(线段树区间合并）
这道题网上很多代码是错误的，由于后台数据水，他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度（就是最接近初始位置的高度），和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数，min_v 记录该区间最小高度 cover
【Leetcode56】合并区间（数组 | 排序）
文章目录 一、题目二、思路三、代码 一、题目 二、思路 先将所有子列表按照start_pos进行排序，有利于保持顺序性，每次处理新子列表时，只用和结果列表ans_lst的最后一个子列表对比，如果有重合则合并，然后将合并的新子列表插入结果列表排序可以使用lambda函数，intervals.sort(key=lambda x: x[0])因为使用了sort，所以时间复杂度O(
力扣 | 递归 | 区间上的动态规划 | 486. 预测赢家
文章目录 一、递归二、区间动态规划 LeetCode：486. 预测赢家 一、递归 注意到本题数据范围为 1 < = n < = 20 1<=n<=20 1<=n<=20，因此可以使用递归枚举选择方式，时间复杂度为 2 20 = 1024 ∗ 1024 = 1048576 = 1.05 × 1 0 6 2^{20} = 1024*1024=1048576=1.05 × 10^
滑动窗口——632. 最小区间
最近在抽时间写LC上的一个专栏——2024春招冲刺百题计划。挑着做，做了几道和滑动窗口相关的题目，632. 最小区间，LC上标记为困难，第一次写完全没有思考，参考了别人写的答案茅塞顿开，特此记录以鞭策自己学习。最近实习结束回到学校后，一边搞科研，自己本来想一天写一篇博客，以此鞭策自己学习，但自己研究方向和后端丝毫不沾边，自己最近又没有学习新的知识用以记录博客，也甚是悔已。人生如是，
HDU 1556 Color the ball (树状数组-- 区间更新，单点求值)
OJ题目 ：点这里~~ 与 单点更新，区间求值 稍有不同，需要理解注意。 AC_CODE int n;int num[100002];int lowbit(int x){return x&(-x);}int sum(int x){int ret = 0;while(x > 0){ret += num[x];x -= lowbit(x);}return ret;}void ad
HDU 1166 敌兵布阵 （树状数组--单点更新，区间求值）
OJ题目 ： click here ~~~ 中文的，大概题意就不说了。树状数组的水题。 忘记清空数组，导致WA，真可恨啊~~~~~~~ AC_CODE int n;int num[50002];int lowbit(int x){return x&(-x);}int sum(int x){int ret = 0;while(x > 0){ret += num[x];x -= l
【代码随想录|贪心part04以后——重叠区间】
代代码随想录|贪心part04以后——重叠区间 一、part041、452.用最少数量的箭引爆气球2、435. 无重叠区间2、763.划分字母区间3、56. 合并区间4、738.单调递增的数字 总结 python 一、part04 1、452.用最少数量的箭引爆气球 452. 用最少数量的箭引爆气球 class Solution:def findMinArrowShot
AcWing907. 区间覆盖
参考的视频讲解：↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【贪心算法08-区间问题03-区间覆盖】 每次贪心就是选择左端点里面＜起始端点里面右边界最大的，这样就是保证了最少区间个数! 然后每次迭代都会更新一次起始端点st，反复运用本算法。 一定要仔细看视频讲解！！！ #include<iostream>#include<algorithm>#define N 100010#define INF 2
SQL进阶技巧：每年在校人数统计 | 区间重叠问题
目录 0 问题分析 1 数据准备 2 问题分析 3 小结 区间重叠问题 0 问题分析 有一个录取学生人数表 in_school_stu，记录的是每年录取学生的人数及录取学生的学制，计算每年在校学生人数。 1 数据准备 create table in_school_stu as(select stack(5,1,2001,2,1200,2,2000,5,1300,
Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers
对应POJ 题目：点击打开链接 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 72765 Accepted: 22465Case Time Limit: 2000MS Description You have N integers, A1
Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain
对应HDU题目：点击打开链接 Play with Chain Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4571 Accepted Submission(s): 1859 Problem Descript
【线段树】-POJ-3468-区间增减区间求和
依然是模板，原版来自hh大神 题目链接：http://poj.org/problem?id=3468 lazy的思想还是蛮有用的吧。。不只是线段树 #include <cstdio>#include <algorithm>#include <cstring>#include <iostream>typedef long long ll;using namespace std;#
[a, b]区间内找到一些数满足可以被一个整数c整除
/***************************************************************** 问题描述： 牛牛想在[a, b]区间内找到一些数满足可以被一个整数c整除,现在你需要帮助牛牛统计区间内一共有多少个这样的数满足条件？ 输入描述: 首先输入两个整数a,b,（-5*10^8 ≤ a ≤ b ≤ 5*10^8)接着是一个正整数c（1 <=
5.在一维坐标轴上有n个区间段，求重合区间最长的两个区间段。
这种题目见过一些类似的题目。这里整理一下思路。 一位很牛逼的网友写的，点击打开链接。用的是分治法，类似于归并排序。 还有一种动态规划的方法，点击打开链接，思路如下： 假设S[n]表示n条线段中最长重叠距离，最长重叠距离只与两条线段有关，那么考虑两种情况： 1. 最长重叠距离与第n条线段无关，则最长重叠距离存在于前n-1条线段中，即S[n]=S[n-1]； 2. 最长重叠距离与第n条线段有
合并区间【leetcode】
题目 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例 1： 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间
代码随想录算法训练营Day02 | 209.长度最小的子数组、59.螺旋矩阵II、区间和、开发商购买土地
文章目录 209.长度最小的子数组思路与重点相关题目（TODO） 59.螺旋矩阵II思路与重点 区间和思路与重点 开发商购买土地思路与重点 209.长度最小的子数组 题目链接：209. 长度最小的子数组 - 力扣（LeetCode）讲解链接：代码随想录 (programmercarl.com)状态：回忆不起来，直接看题解了。 思路与重点 最直观的方法还是我们的暴力
数据结构-非线性结构-树形结构：有序树 -＞ 二叉树 -＞ 平衡二叉树 -＞ 线段树 (Segment Tree) / 区间树【不是完全二叉树；用于处理区间类数据】【基于静态数组/链表】【竞赛】
平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树； 线段树的代码实现 SegmentTree.java /*** 线段树** @author whx* @version 2018/8/25*/public class SegmentTree<E> {/**普通数据*/private E[] data;/**树结构数据*/private E[] tr
【3.8】贪心算法-解无重叠区间
一、题目 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。 示例 1: 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。 示例 2: 输入: intervals