线段树

HDU1754,I Hate It（线段树）

本题涉及线段树的区间查询最大值与单点更新，属于一道模板题。代码如下： #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn2e55; struct Node {int l,r;int m…

5-14 数据结构啊poi C.交错和

http://acm.hust.edu.cn/vjudge/contest/view.action?cid78124#problem/C //想看题目的willinglive 我们可以用线段树维护s1,s2,ts1,ts2分别表示奇数位的和，偶数位的和，ANS[l,r]，ANS[l1,r]，然后合并的时候看下前面部分的长度直…

POJ3468,A Simple Problem with Integers（线段树-区间查询-区间更新）

线段树的裸题。给定N个数，有两种操作，一种使[a,b]区间内所有数加上c，另一种询问[a,b]区间内所有数的和。代码如下： #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> usin…

【NOI2017模拟6.26】A

Description 给出一棵树，求树上所有满足路径中任意两个不同点a,b,gcd(a,b)≠a的无序路径 n<1e5 Solution 先讲讲我在考场上想的辣鸡做法暴力部分枚举倍数来判断能做到n^2 log n 由于某些奥妙重重的原因这个做法能跑过3*1e4 一条链的话可以预处理出每个点…

使用线段树解决数组任意区间元素修改问题

使用线段树解决数组任意区间元素修改问题作者：Grey 原文地址： 博客园：使用线段树解决数组任意区间元素修改问题 CSDN：使用线段树解决数组任意区间元素修改问题要解决的问题数组任意区间内的元素修改，增加&…

bzoj 3747: [POI2015]Kinoman

Description 共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<l<r<n)，并观看第l,l1,…,r天内所有的电影。如果…

bzoj 2482: [Spoj1557] Can you answer these queries II

Description 给定n个元素的序列。给出m个询问：求l[i]~r[i]的最大子段和（可选空子段）。这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。比如：1，2，3，2&#xff0c…

5-14 数据结构啊poi W.区间对

http://acm.hust.edu.cn/vjudge/contest/view.action?cid78124#problem/W //想看题目的willinglive 首先想到O(n^2)的做法，枚举区间[l,r]，我们考虑加入r1的时候有多少段。如果[l,r]有k段，那么r1的位置前后如果均存在，则[l,r1]k-1…

SDUT 2880 第五届山东省ACM省赛 Devour Magic （线段树+区间处理） 57行代码搞定~

传送门：SDUT 2880题目大意： 数轴上有从 1~n 的 n ( 1< n < 1e5)个点，每个点每单位时间会增加 1 单位法力，给出某个人按时间顺序的 m 次操作，每次操作都会在时间 t 时把区间 [ l , r ] 内的法力都收走&#xff0c…

UESTC - 1597 线段树区间乘法加法取模

题意： 给一个数组， 有三个操作 1. 区间乘法 2. 区间加法 3. 询问区间的和并取模。思路：两个数组作为懒惰标记。分别是对加法和乘法的对子树传递的保存。每次乘法时， 都要把sum数组也乘起来，在向下传递时就可以先乘…

bzoj 3165: [Heoi2013]Segment

Description 要求在平面直角坐标系下维护两个操作： 1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 2.给定一个数k,询问与直线 x k相交的线段中，交点最靠上的线段的编号。 Input 第一行一个整数n，表示共n 个操作。接下来…

[BZOJ2138]stone

Description 给定长度为n的序列A，ai表示位置i有多少个石子。有m次操作，第i次操作从区间[li,ri]中选择ki个石子丢弃，如果不足ki个则全部丢弃保证区间互不相交最大化丢弃石子的字典序 n,m<40000 Solution 考虑如果我们已经知道了每次要…

Educational Codeforces Round 112 (Rated for Div. 2) E. Boring Segments 线段树+尺取

题目链接题目大意给你一个1-m的区间 n个线段这个线段 l,r,w 代表从l到r 权值为w 问你如何选择线段可以让线段覆盖这个区间并且选择的线段的权值最大和最小的差最小即最大权值和最小权值最接近题目思路由于是要找到线段权值差最小有单调性很轻易考虑到将所给的…

2021ICPC网络赛Ⅱ（第二场）L Euler Function 线段树+欧拉函数定理

题目链接题目大意两种操作 0 l r w, for each index i∈[l,r], change xi to xiw.1 l r, calculate and print mod 998244353.其中\varphi (x_{i}) 就是区间内欧拉函数的和题目思路要做这个题首先要知道以下两个定理我们先预处理出来一百以内的欧拉函数以及一百…

【动态规划】【线段树】P8051 [ZYOI Round1] Bird/鸟

分析先不考虑瞬移功能，设fif_ifi表示i位置上的最多的飞行次数，那么我们可以线通过单调栈预处理出来每个位置 i ，左侧和右侧第一个比它高的位置，分别记为lp[i]和rp[i]，那么转移方程为fimax{fj1∣lp[i]≤j≤rp[i]}f_…

[ARC 063 F]Snuke's Coloring 2

Description 给出一个wxh的网格图，和n个点，求一个周长最大的矩形，满足这个矩形内部没有点。注意矩形边界上不算在内部。 n<2*1e5 Solution 首先让我们来想一个分治做法。分治了一条中线，我们想要求出跨过中线的答案。那…

HDU1698，Just a Hook（线段树）

这道题考察的是线段树的区间更新和区间查询。关于线段树的区间更新操作，可参考博客： https://www.cnblogs.com/TenosDoIt/p/3453089.html#f PS：线段树的区间更新必须借助延迟标记（本人用lazy表示），否则时间…

杭电2019多校第六场 HDU-6638 Snowy Smile （线段树+最大子矩阵和）

链接：http://acm.hdu.edu.cn/showproblem.php?pid6638 题意：T组样例。n个二维平面上的点，每个点有一个权值，问最大子矩阵和。思路： 题解：首先将纵坐标离散化到 O(n) 的范围内，方便后续的处…

线段最大重合区域问题

线段最大重合区域问题作者：Grey 原文地址： 博客园：线段最大重合区域问题 CSDN：线段最大重合区域问题题目描述牛客-线段重合-连接点算重合区域主要思路暴力解法第一步，首先得到所有线段开始位置的最小值…

bzoj 4034: [HAOI2015]T2

Description 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 &#x…

2023牛客暑期多校训练营8-C Clamped Sequence II

2023牛客暑期多校训练营8-C Clamped Sequence II https://ac.nowcoder.com/acm/contest/57362/C 文章目录 2023牛客暑期多校训练营8-C Clamped Sequence II题意解题思路代码题意解题思路先考虑不加紧密度的情况，要支持单点修改，整体查询&#xff0…

GDKOI2016 Day 1 T1 魔卡少女

T1 魔卡少女给出N个数，M个操作。操作有修改和询问两种，每次修改将一个数改成另一个数，每次询问一个区间的所有连续子区间的异或和。线段树，对于二进制的每一位开一颗线段树。对于每一个区间，维护其从左开始但不到右结…

算法竞赛进阶指南 (线段树+懒标记) 一个简单的整数问题2

题面题解对于有区间修改和区间查询的，我们第一个想到的就是用线段树懒标记去做区间修改时，当修改区间完全包含树区间时，在这个树区间打一个标记（表示给以当前节点为根的子树中的每一个节点加上add,不包含根节点）&am…

2020 CCPC秦皇岛 D - Exam Results Gym - 102769E 线段树+离散化

链接https://codeforces.com/gym/102769/standings 题目大意有n个学生每个学生有两个成绩你可以选择一个为这个学生的最终成绩设这n个学生的最终成绩中最大的为MAX 问你如何选择让数量最多的学生最终成绩不低于MAX的百分之P 题目思路每个学生的两个成绩 ai 和 bi a…

【NOIP2015模拟11.2晚】我的天

Description 有n个人排成一列。给出m次操作，每次操作让区间l~r的人互相认识。求每次操作后新增了多少对认识的人。 n,m<300000 Solution 很显然，每个人认识的人都是一个区间内的。为了避免算重复，我们可以只计算他左边和他认识的人。设…

【NOIP2015模拟11.2】有趣的有趣的家庭菜园

Description 给出一个序列，每个位置有高度h，费用c和权值b。你现在可以移除一些位置，代价为移除位置的费用和。然后，你可以的到所有满足以下条件的位置的权值的收益。 1:所有没有被移除的j,且j Solution 很明显，最后…

5-14 数据结构啊poi E.splay上的游戏

http://acm.hust.edu.cn/vjudge/contest/view.action?cid78124#problem/E //想看题目的willinglive 我们发现无论如何操作。树的中序遍历不变于是我们维护中序遍历，每次左旋或者右旋只改变两个点的状态然后记录下他的子树是哪段，用线段树维护区间乘积…

HDU 5875 Function【线段树】

这个题类似南京网络赛的题目题目大意是给你一个区间[l,r] 让你求 a[l] %a[l1]%a[l2]%….%a[r]的值我们发现只有取模一个小的数的时候结果才会变化，所以我们只要求 [l1,r] 区间内第一个比当前树小的即可用一个线段树来维护区间最小值，然后优先向左边…

Codeforces Round #373 (Div. 1) C.Sasha and Array

题目大意：给你一个长度为n的数列an，有两种操作 1、将L到R的ai加上X 2、询问L到R之间，f(aL)f(aL1)……f(aR)的和考虑维护fib数列的转移区间加，就相当于区间乘上一个矩阵那么我们直接维护矩阵的合并和懒标记下推就可以了乘的矩阵…

蓝桥小课堂-平方和模拟 1 2 2 2 3 2 ⋯ n 2 n ⋅ ( n 1 ) ⋅ ( 2 n 1 ) 6 1^22^23^2\cdotsn^2\dfrac{n\;\cdot\;(n 1)\;\cdot\;(2n1)}{6} 122232⋯n26n⋅(n1)⋅(2n1)。 write(n * (n 1) * (n * 2 1) / 6);房顶漏水啦 m a x ( 最大的行 − 最小的行 , 最大的列 −…

【挖坑】【GSS系列】GSS3:带单点修改的区间最大子段和

Can you answer these queries? GSS系列是spoj出品的一套数据结构好毒瘤题，主要以线段树、平衡树和树链剖分为背景，进行了一些操作的魔改，使得难度远超模板题，但对于思维有极大的提升。所以我会选择一些在我能力范围内的…

AHOI2009 维护序列（线段树+懒标记）

原题链接思路题意让维护区间，涉及操作有区间修改和区间查询，很明显的线段树懒标记再看需要维护的信息，就是线段树的节点，首先肯定有左右两个端点 l , r ，然后就是区间和 sum ,再有就是懒标记区间加add，区…

【每日一题】区域和检索 - 数组可修改

文章目录 Tag题目来源解题思路方法一：分块方法二：线段树方法三：树状数组写在最后 Tag 【树状数组】【线段树】【分块】【前缀和】【设计类】【2023-11-13】题目来源 307. 区域和检索 - 数组可修改解题思路使用前缀和解决不行吗&#x…

F - Pre-order and In-order（Atcoder 255）

题目： 题目链接： F - Pre-order and In-order (atcoder.jp) 题解：Editorial - Aising Programming Contest 2022（AtCoder Beginner Contest 255） 思路: 因为官方题解已经说的很清楚了我这里就简要补充一些 1.首先…

【挖坑】【GSS系列】GSS5：限制端点范围的区间最大子段和

Can you answer these queries? GSS系列是spoj出品的一套数据结构好毒瘤题，主要以线段树、平衡树和树链剖分为背景，进行了一些操作的魔改，使得难度远超模板题，但对于思维有极大的提升。所以我会选择一些在我能力范围内的…

刷题记录:牛客NC20279[SCOI2010]序列操作

传送门:牛客题目描述: lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全…

POJ 2528 Mayor’s posters （线段树+离散化处理）彻底搞懂延迟标记

传送门：POJ 2528题目大意： 有 n 张海报，高度一样，现在告诉你每一张张贴的宽度区间为 [ l , r ] （1<l<r<1e7），问全部张贴完毕后，可以看到几张海报。注意，只要能看…

Mayor's posters OpenJ_Bailian -POJ - 2528 （离散化算法）

Mayor’s posters OpenJ_Bailian - 2528 题目我就不写出来拉 ，简单依据这道题来简单的说一下离散化算法。离散化算法是一种将许多很大的空间根据这些空间的相对关系 ，进行离散化 ，将这些大空间转变为与之一一对应的小…

2023河南萌新联赛第（六）场：河南理工大学-L 阴晴不定的大橘学长

2023河南萌新联赛第（六）场：河南理工大学-L 阴晴不定的大橘学长 https://ac.nowcoder.com/acm/contest/63602/L?&headNavacm 文章目录 2023河南萌新联赛第（六）场：河南理工大学-L 阴晴不定的大橘学长题…

codeforces 877E. Danil and a Part-time Job (DFS序列+线段树)

传送门：codeforces 877E 题目大意： 有一颗树，树的每个节点有一盏灯，状态为亮或灭。现在可以进行以下两种操作： 1.pow x，将以 x 为根节点的子树（包括根节点）的所有节点的灯的状态都…

HDU 174 I hate it

Description 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问…

poj 3468 线段树求区间和模板

limit 5000MS 时间 2719MS 求区间和模板两个操作 ： 1. 求区间和 2.区间加法 #include <cstdio> #include <cstring> #include <iostream> #define mem(a) memset(a, 0, sizeof(a)) using namespace std; const int inf 0x3f3f3f3f; const …

线段树（求矩形周长）

# define N 5005 int e; struct node1 {int x,y1,y2;int f; } line[2*N]; struct node2 {int l,r;int lf,rf;/*左右区间所对应的y值*/int cnt;/*节点上线段的测度*/int count;/*节点被线段完全覆盖的次数*/int lines;/*节点上所包含的线段的段数*/int lb,rb;/*节点的左右端点是…

POJ 3468 线段树成段更新区间求和 + 延迟标记详解 A Simple Problem with Integers

接触线段树有很长时间了，感觉最近才慢慢的弄懂线段树的思想，它的精华所在。所以想跟刚开始学习线段树的朋友分享一下，希望对你们有所帮助。下面我来基于 POJ 3468 题来讲解一下线段树成段更新区间求和问题的解法。POJ 3468 的题目大意是给出 …

洛谷P3373 [ 模板] 线段树（乘法和加法）

andy的小伙伴acer（WA_哈_哈）已经写好【模板】线段树1啦，但是仅仅支持区间加法和查询，这对于oier们当然是远远不够的，所以本蒟蒻在此奉上线段树的区间加法，乘法的实现，以及对乘法标记的下放&…

【数据结构】树状数组C++详解

文章目录引入树状数组定义什么是单点修改和区间查询工作原理区间查询代码实现单点修改实现代码242. 一个简单的整数问题AC代码如下：练习：AC代码如下：引入 242. 一个简单的整数问题给定长度为 N的数列 A A A<

酒店

题目描述 A城市有个超级大酒店，住房部只有一层，只向南，但房间有N个（编号1, 2 .. N）。刚开始所有房间都是空的，但酒店肯定会有人来住宿，有些房间就要被入住。但客人经常会问一个问题&#xff0c…

【挖坑】【GSS】GSS7：树链剖分中的最大子段和

Can you answer these queries? GSS系列是spoj出品的一套数据结构好毒瘤题，主要以线段树、平衡树和树链剖分为背景，进行了一些操作的魔改，使得难度远超模板题，但对于思维有极大的提升。所以我会选择一些在我能力范围内的题挖坑…

HDU-1698 Just a Hook(线段树区间更新)

文章目录题目描述输入格式输出格式样例输入样例输出提交链接提示解析参考代码题目描述在 DotA 的游戏中，Pudge 的肉钩实际上是大多数英雄最可怕的东西。挂钩由几个长度相同的连续金属棒组成。现在 Pudge 想在钩子上做一些操作。让我们将钩子的连续金属棒从 1…

第 116 场 LeetCode 双周赛题解

A 子数组不同元素数目的平方和 I 枚举：枚举子数组，用集合记录当前子数组中不同元素的个数 class Solution { public:using ll long long;int sumCounts(vector<int> &nums) {ll mod 1e9 7;int n nums.size();unordered_set<int> s;l…

Codeforces Educational Codeforces Round 56 (Rated for Div. 2) 1093G. Multidimensional Queries

有一kkk维点序列。求[l,r][l,r][l,r]之间Manhattan\text{Manhattan}Manhattan距离最大的点。要求点修改区间查询。解:每维的坐标分解如下： ∣aj−bj∣aj−bjorbj−aj,j1,2,...,k|a_{j}-b_j|a_{j}-b_{j}\ or\ b_{j}-a_{j},j1,2,...,k∣aj−bj∣aj−bj or b…

算法竞赛进阶指南---（线段树+懒标记）旅馆

题面题解我们可以将其看作是一个01串，初始全部为0 。操作1 ：找到最靠左的长度为len的全部为0的串，输出左端点，并将这个区间全部变成1，如果不存在就输出0 ； 操作2，把左端点为l，长度…

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）（A,B,C,D,E,F,G）

看不懂的英文，题意很难理解，这场还是有点难度的。 C需要处理，D是不太明显的dijikstra，E是线段树优化dp，F是个不好想的线段树，主席树应该也能做。 A Yay! 题意： 长度大于等于3的字符串里只有两…

[LOJ6507]「雅礼集训 2018 Day7」A

Description 给出一个长度为n的序列a，要求资瓷区间或，区间与和求区间最小值 n<5e5,ai<2^31 Solution 让我们先来考虑一个暴力： 如果一次操作对某个区间的影响是一样的（即最小值还是那个数），那么我…

赛后题解:Codeforces Round #852 (Div. 2)1793C Dora and Search

传送门:CF 题目描述: 题目较长,此处省略输入: 4 3 1 2 3 4 2 1 4 3 7 1 3 2 4 6 5 7 6 2 3 6 5 4 1 输出: -1 1 4 2 6 -1一道有关区间最大值/最小值的问题本题需要求出一个区间,满足区间的两个端点都不是区间最值比赛时我是这么想的.当你的区间最值在区间两端点时显然是…

牛客练习赛53 老瞎眼 pk 小鲜肉[思维+离线+线段树]

题目大意给定一个序列，q个查询查询（l,r）内异或值0 的最小区间题目分析考虑对序列求一个前缀异或和那么每个点找到与自己相同的最近的点的位置，就是每个点作为右端点 0 的最小区间。所有的查询区间按照右端点排序然后…

codeforces 1023 D Array Restoration （树状数组）

题面题意有一个长度为n的序列，你可以进行 q 次修改，第i次修改将区间 [l,r] 的数修改成 i ，涉及的 q次修改必须要覆盖区间中的每个数，q 次修改之后，将这个序列中的某些数变为0，得到一个新的序列&#xff0…

acwing 1275 最大数

题面题解因为题中最多m次操作，所以最多有m个节点，那么我们就可以提前建立一颗M*4节点的线段树，那么对于A操作，就变成了在某一个位置修改数，那么Q操作就变成了查询区间的最大值，其他就是线段树模板了代码…

2019南昌网络赛 I. Max answer（单调栈+线段树）

链接：https://nanti.jisuanke.com/t/38228 题意和思路都和https://blog.csdn.net/birdmanqin/article/details/97553976差不多。 #include <bits/stdc.h> #define ll long long using namespace std; const int N 5e510; const ll inf 1e18; struct node …

【线段树】【树链剖分】P5354 [Ynoi2017] 由乃的

题意简化版的上树带修 n,m≤1e5val<264n,m \le 1e5 \ val < 2^{64}n,m≤1e5 val<264 分析我们可以用线段维护树上一段操作，由0/1进去后出来的结果，维护一下正反两个方向，结合树剖和简化版的贪心方式就可以得到O(nklog2n)O(nklo…

注意分类讨论完整性：CF1371F

https://www.luogu.com.cn/problem/CF1371F 此题要分类讨论完全容易漏掉 >>>>><<<<< 在左右或中间的情况多对拍 #include<bits/stdc.h> using namespace std; //#define int long long inline int read(){int x0,f1;char chgetchar(…

2019牛客暑期多校训练营（第四场）C sequence（单调栈+线段树）

链接：https://ac.nowcoder.com/acm/contest/884/C 题意：注意是多组输入。。。。第一行给出n，接下来给出数组a的n个元素和数组b的n个元素。在所有连续区间中，假设为[l,r]，求数组a在该区间的最小值*数组b在该区间的和的…

【WinterCamp 2013】阿凡达

Description 维护一个序列，资瓷 1：将A[l]~A[r]中的每一个A[x]变为(x-l1)*a mod b 2：询问A[l]~A[r]的和 n<1e9,m<5*1e4 Solution 考虑将一次赋值看做一个颜色段，然后同一个颜色段里面的和我们可以用类欧来计算。用线…

杭电2019多校第二场 HDU-6601 Keen On Everything But Triangle（线段树+三角形与斐波那契数列或主席树（模板））

链接：http://acm.hdu.edu.cn/showproblem.php?pid6601、题意：多组样例。给你一个n和q，接下来一行n个数，加下来q行，每行给出l、r，求区间[l,r]中的数，能组成三角形周长的最大值。不能组成则输出…

2016多校训练Contest4: 1007 Treasure hdu5770

Problem Description?? has got a treasure map,the treasure map consists of N nodes,there are N-1 bidirectional roads, Each of them connects a pair of nodes,the N nodes are all connected by the N-1 bidirectional roads.?? can travel through the roads.Ther…

约瑟夫问题解析附C/C++代码——使用线段树解决

目录一、何为约瑟夫问题二、朴素法2.1 朴素法-C语言2.2 朴素法-C三、线段树法3.1 何为线段树3.2 约瑟夫问题的线段树构建3.3 线段树的查询和修改3.3.1 删除结点（修改count）3.3.2 查询结点数（计算1~i的活人数）3.3.3 完整代码四、参…

Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma 线段树

题目链接题目大意给你一个1-n的区间你要完成以下两种操作 1 将某个数改为某个数 2 判断l到r范围内有多少个连续的不下降区间如 345这个区间里有6个区间 （单个数字也算） 题目思路两个区间合并后的答案数量变化可以很轻易地想到只与两个区间相…

[Daimayuan] 奶牛集会（C++，线段树）

题目描述约翰的 n n n 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第 i i i 头奶牛的坐标为 x i x_i xi，…

上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果

https://www.luogu.com.cn/problem/P8518 没有要求在线，显然离线（。维护时间戳，上线段树。好了，我们现在知道一个人的曲线变化了。怎么做呢？ 前面所有碰上下界的都是没用的！我们只需要找最后一段的时间…

【挖坑】【GSS系列】GSS4:区间开平方

Can you answer these queries? GSS系列是spoj出品的一套数据结构好毒瘤题，主要以线段树、平衡树和树链剖分为背景，进行了一些操作的魔改，使得难度远超模板题，但对于思维有极大的提升。所以我会选择一些在我能力范围内的题挖坑…

1129 - 喵哈哈村的战斗魔法师丶坏坏い月线段树

题意：n个数，有q次询问，每次询问有两个操作 1.在区间【l, r】找到比v大的第一个数的下标 2.把【l,r】的数全部加上v。思路： 裸线段树的题写法1：线段树 #include <cstdio> #include <cstring> #include…

POJ2892，Tunnel Warfare（线段树维护连续区间）

正在入门线段树，做了几道题，都是比较侧重去考虑父节点与其子节点之间的关系，而本题不但要考虑父节点与子节点的关系，还要考虑相同父节点的子节点之间的关系。本文是参考下面博客写的： https://blog.csdn.net/libin568…

5-14 数据结构啊poi B.mex

http://acm.hust.edu.cn/vjudge/contest/view.action?cid78124#problem/B //想看题目的willinglive 因为mex有单调性，所以我们用线段树来维护以每个点为右端点的mex的和。然后枚举左端点。修改左端点的时候只需要修改当前到下一次该点的值出现的位置-1就可以了 #…

hdu 1556 color the ball 线段树区间更新加lazy标记

题意：给你一排气球让你涂色， 有n个操作，表示将[l，r]区间的球涂色，问最后1~n的气球被涂色的次数。 #include<iostream> #include<cstdio> #include<cstring> const int MAXN 100005; using namespa…

ACM-ICPC 2018 徐州赛区网络预赛 Trace【线段树】

题目大意，这个题就是给你若干个点，这些点与坐标轴围成一个矩形，然后后面的矩形可以覆盖前面的矩形，问最后还留在平面中的线段的长度是多少分析：离散化以后倒过来扫点，比如说求x，就用线段树维护…

【LeetCode:715. Range 模块 | 线段树】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…

线段树的模板【区间更新，区间查询】

线段树的模板线段树讲解 #include <bits/stdc.h> #define fill(arr,val) memset(arr,var,sizeof(arr) using namespace std; const int maxn1e550; const int mod1e97; typedef long long ll; struct node {int l,r;ll sum,lazy;void update(ll x){sum(r-l1)*x;lazyx;…

数据结构——线段树的基础知识

1.线段树的定义： 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(ab)/2]&#xf…

线段树模板合集--单点替换，区间替换，区间增加3种情况

1.单点覆盖，区间查询 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; #define lson l , m , rt << 1 #define rson m 1 , r , rt << 1 | 1 const int maxn 100007; const int INF0x7fffffff; i…

Light oj 1138 - Trailing Zeroes (III)

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! 1*2*…*N. For example, 5! 120, 120 contains one zero on the trail. Input Input starts with an integer T (≤ 10000), deno…

codeforces 1252K Addition Robot【线段树+矩阵乘法】

题目大意给你一个串包含AB两种元素，进行以下两种操作 1、给定一个区间[l,r][l,r][l,r] 将 A 变成 B，B 变成 A 2、给定一个查询区间 [l,r][l,r][l,r] 以及两个数 x,y 在区间 [l,r][l,r][l,r]中如果 s[i]As[i] As[i]A 那么 x xy 否则 yxy 查询这个…

算法竞赛进阶指南---0x43（线段树）interval GCD

题面题解两个操作，给一段区间加上一个数，查询区间的最大公约数，我们知道，对于不加懒标记的线段树只能做到单点修改和区间查询，要想区间查询就要加上懒标记，但是我们再仔细思考，题中只有一个区…

bzoj 2957: 楼房重建

Description 小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。　　为了简化问题，我们考虑这些事件发生在一个二维平面上。小…

备战蓝桥杯---线段树基础2

今天我们把线段树的另一个模板看一下： 在这里，我们注意到乘的操作，因此我们用两个懒标记来分别表示加和乘，这时我们面临了一个问题，就是当我们把标记往下传时，它的儿子怎么知道是先乘还是先加？ …

HDU - 1166 敌兵布阵

敌兵布阵题目链接 C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营…

bzoj 4127: Abs

Description 给定一棵树,设计数据结构支持以下操作1 u v　d　表示将路径 (u,v) 加d2　u　v 表示询问路径 (u,v) 上点权绝对值的和Input 第一行两个整数n和m，表示结点个数和操作数接下来一行n个整数a_i,表示点i的权值接下来n-1行,每行两个整数u,v表示存在一条(u,v)…

线段树维护矩阵：0920T4

正解为文艺平衡树维护矩阵，但我打不动，所以打了部分分首先可以写成dp形式然后又可以写成矩阵形式然后矩阵显然支持结合律所以可以拿线段树维护 #include<bits/stdc.h> using namespace std; #define int long long inline int read(){int…

线段树（求矩形并，交，并减交的面积）

# define N 100100 int e; //记录横坐标个数,注意主函数里不要有同名变量 struct node1 {double x,y1,y2;int f; } line[N*2]; struct node2 {double rf,lf,cnt,incnt; //求矩形交可以没有cnt，求矩形并可以没有incntint l,r,c; } tree[N*5]; double y[N*2]; int c…

【ZJOI2008】树的统计

Description 给出一棵n个节点的树，和m个操作。每个点有点权，操作有单点修改，树上路径和和树上路径最大主三种。n<30000,m<200000,-30000<权值<30000。 Solution 裸的树链剖分。不多解释。不会的请点击树链剖分学习小记 Cod…

数据结构：线段树（SegNode）

作用对于区间的修改和查询的时间复杂度都是log级别的，比如计算一个区间的和线段树的定义它其实就是一颗二叉树， 但它有一个范围left,right左子树的范围是 left - center，右子树的范围是 center - right而当前count lChild.count rCh…

28.线段树与树状数组基础

一、线段树 1.区间问题线段树是一种在算法竞赛中常用来维护区间的数据结构。它思想非常简单，就是借助二叉树的结构进行分治，但它的功能却非常强大，因此在很多类型的题目中都有它的变种，很多题目都需要以线段树为基础进行发展。…

leetcode 2213 — 由单个字符重复的最长子字符串

leetcode 2213 — 由单个字符重复的最长子字符串一、题目描述二、题目分析三、算法1、初版实现2、线段树（1）结构（2）实现（3）测试代码（4）区间更新与懒惰标记（5）…

bzoj 2733: [HNOI2012]永无乡（线段树合并）

Description 永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出…

第七周周赛——字典树 + 线段树 + 树状数组等等（去师大比赛前的最后一场）

题目分别出自： poj1195，codeforces 482B，codeforces 591A，poj 2503，poj2442，codeforces 445B A题： A题题目链接题目描述： Mobile phones TimeLimit:5000MS MemoryLimit:65536…

5-14 数据结构啊poi A.暑假作业

http://acm.hust.edu.cn/vjudge/contest/view.action?cid78124#problem/A //想看题目的willinglive 用线段树维护这种东西还是第一次写。。我们先考虑合并操作。维护F0开始乘的区间和和F1开始乘的区间和。只需要把右边那段乘上一个矩阵再加上左边那段就可以了单点修改直接做…

HDU1166,敌兵布阵（线段树单点更新，区间求和）

刚开始学习线段树，这道题是道不错的模板题。关于线段树可参考： https://blog.csdn.net/x314542916/article/details/7837276 https://blog.csdn.net/WhereIsHeroFrom/article/details/78969718 #include<cstdio> #include<iostream> #incl…

线段树

线段树为什么需要线段树呢？线段树能做什么呢？ 首先介绍一下线段树的原理线段树就是将 [ 1 , n ] 分解成若干特定的子区间（ 数量不超过 4*n ），然后将每个区间 [ L , R ] 都再次分解为少量特定的子区间，通…

【YBT2023寒假Day12 B】仰望星空（DP）（线段树）（笛卡尔树）

仰望星空题目链接：YBT2023寒假Day12 B 题目大意有一个 n*n 的网格，第 i 列下面的 ai 个点都是障碍。然后又一些不是障碍的地方有特殊点，删掉它有费用。要你用最小费用使得不存在两个特殊点在一个矩阵中且矩阵中没有障碍。思路注意…

刷题记录:牛客NC14522珂朵莉的数列

传送门:牛客题目描述: 珂朵莉给了你一个序列，有n*(n1)/2 个子区间，求出她们各自的逆序对个数，然后加起来输出输入: 10 1 10 8 5 6 2 3 9 4 7 输出: 270对于这道题,我们发现和逆序对有关,但是我们肯定不能直接求出每一个区间的逆序对数然后…

【模板】线段树 2

题目描述如题，已知一个数列，你需要进行下面三种操作： 将某区间每一个数乘上 xxx 将某区间每一个数加上 xxx 求出某区间每一个数的和输入格式第一行包含三个整数 n,m,pn,m,pn,m,p，分别表示该数列数字的个数、操作的总个数…

HDU- 1166 敌兵布阵 - 线段树

Lily特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花…

AtCoder Beginner Contest 343（A,B,C,D,E,F）

比赛链接 CE是暴力，D是数据结构题，F是线段树。这场的E比较有意思，其他的感觉有点水。 A - Wrong Answer 题意： 给你两个数 A , B A,B A,B ( 0 ≤ A , B ≤ 9 ) (0\le A,B\le 9) (0≤A,B≤9)，返回一个个位数&#…

刷题记录:牛客NC23054华华开始学信息学线段树+分块

传送门:牛客题目描述: 题目latex公式较多,此处省略输入: 10 6 1 1 1 2 4 6 1 3 2 2 5 7 1 6 10 2 1 10 输出: 3 5 26这道题让我体验到的线段树相对于树状数组的常数巨大我们倘若直接用单点修改的话，如果D过小比如1那么我们足足要加n次，时间复杂度爆…

【2-SAT】【树链剖分】【线段树】【前缀和优化建图】CF1007D Ants

题意给定一棵树，开始每条边都没有颜色有m次操作，每次给定两个点对(a,b)(a,b)(a,b)(c,d)(c,d)(c,d)，选择一个给两者的路径上的边染色问是否存在一种选择方式，使得不存在被重复染色的边分析考虑这种二选一的需要2-SAT解决 …

式子表达ds类——多用位置/值域表示未知数+区间覆盖转区间加：CF407E

https://www.luogu.com.cn/problem/CF407E 多用位置/值域表示未知数推出的式子中 n n n 表示长度，应该直接换成 r − l 1 r-l1 r−l1 区间覆盖转区间加推出的式子有 m x , m n mx,mn mx,mn，朴素思路是用单调队列区间覆盖维护那样就不能很方便…

[ZJOI2016]线段树

Description 给出一个长度为n的序列，对这个序列进行m次操作，每次操作随机一个区间[l,r]，把这个区间里面的数全部变成这些数的最大值。求最后每个位置的数的期望，答案乘上(n(n1)/2)^m后对1e97取模 n,m<400，a[i]&…

【树链剖分】【线段树】树的核心

题意给定一棵带点权的树，初始点权均为0。有两种操作：1.给u子树内所有点权值1 2.给路径u到v之间的点权值1 每次修改后输出带权重心靠近1优先 n,q≤105n,q\le10^5n,q≤105 分析可以把点权aia_iai的点，拆成aia_iai个点，那么…

POJ3264，Balanced Lineup（线段树区间查询最值）

这道题也是线段树的裸题，但其实也没有必要用线段树来做，可以用RMQ等其它区间查询最值的方式，用线段树反而会更慢，不过作为线段树的入门题，拿来练练手也是挺不错的。线段树AC代码如下： #include<cstdio…

树状数组，线段树，容斥，P3801 红色的幻想乡

P3801 红色的幻想乡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目背景蕾米莉亚的红雾异变失败后，很不甘心。题目描述经过上次失败后，蕾米莉亚决定再次发动红雾异变，但为了防止被灵梦退治，她决定将红雾以奇怪的阵势释…

LeetCode_线段树_中等_307.区域和检索 - 数组可修改

目录 1.题目2.思路3.代码实现（Java） 1.题目给你一个数组 nums ，请你完成两类查询。其中一类查询要求更新数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的…

bzoj3638【GDOI2016模拟3.20】diyiti

Description 给出一个长度为n的序列，a1~an，和m次操作，每次操作分为 0 x val，将ax变成val 1 l r k，询问在区间l~r中，最多k个不重合区间的最大和是多少。 n,m<10^5，|ai|<500&#xff0c…

[洛谷 OJ]P1047 校门外的树

题目链接： https://www.luogu.org/problem/P1047 import java.util.Scanner;public class Main {public static void main(String[] args) {// TODO Auto-generated method stubScanner scnew Scanner(System.in);int lsc.nextInt();int msc.nextInt();boolean[] …

Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines

题目大意： 给你n个点，分别位于pi。每个点有个爆炸范围ri和代价ci，花费ci可以引爆某个点，并且pi-ri到piri范围内的点都会被引爆。q个询问，每次修改一个点的ci，每次输出引爆所有店的最小代价。题解&#xf…

hdu 5875 Function 2016ACM/ICPC大连赛区网络赛1008

Problem DescriptionThe shorter, the simpler. With this problem, you should be convinced of this truth.You are given an array Aof Npostive integers, and Mqueries in the form (l,r). A function F(l,r) (1≤l≤r≤N)is defined as:F(l,r){AlF(l,r−1) modArlr;l<…

第 372 场 LeetCode 周赛题解

A 使三个字符串相等求三个串的最长公共前缀 class Solution { public:int findMinimumOperations(string s1, string s2, string s3) {int n1 s1.size(), n2 s2.size(), n3 s3.size();int i 0;for (; i < min({n1, n2, n3}); i)if (!(s1[i] s2[i] && s2[i] s…

[bzoj1588][HNOI2002]营业额统计

Description 给出n个数，求每个数和它前面每个数的差值绝对值的最小值之和。 n<32767 Solution 很显然求前驱后驱。可以离散化后用权值线段树二分找。也可以直接用splay找。或者还可以离线排完序用双向链表找。你喜欢就好喽。。。 Orz bzoj上rank1 0…

ABC245E Wrapping Chocolate [线段树二分]

也许更好的阅读体验 D e s c r i p t i o n \mathcal{Description} Description n n n个物品有长和宽， m m m个盒子也有长和宽，一个盒子最多可以装一个物品，问 n n n个物品能否都放进盒子，物品和盒子不能旋转 S o l u t i o n \…

线段树【java实现】

一、解决问题区间最值和区间求和问题力扣相关题目： 303. 区域和检索 - 数组不可变 729. 我的日程安排表 I 二、线段树定义平衡二叉树，数组中的元素都存储在叶子结点中，如图是一个求区间最大值的线段树。已知数组arr[11…

结队编程 - 华为OD统一考试

OD统一考试题解： Java / Python / C 题目描述某部门计划通过结队编程来进行项目开发，已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程，结队分组规则如下： 从部门中…

【数据结构】线段树算法总结（区间修改）

知识概览线段树一般有5个操作： pushup：用子节点更新当前节点信息pushdown：把懒标记往下传build：初始化一棵树modify：修改一个区间query：查询一个区间不带懒标记（支持单点修改）的线…

约瑟夫问题Josephus problem

约瑟夫问题：经典算法已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列&#xff…

石油大 Contest1777 - 2019年第二阶段我要变强个人训练赛第九场 C 给你一个666（线段树或RMQ）

时间限制: 1 Sec 内存限制: 256 MB 提交: 346 解决: 62 [提交] [状态] [命题人:admin] 题目描述 Tongtong非常喜欢用“say 666”的方式来打招呼，因此热爱数学的他找到了一个说666的新方式。Tongtong构造了一个数学上很6的运算。定义一个6位二进制数上的运算 : …

贪心找性质+dp表示+矩阵表示+线段树维护：CF573D

比较套路的题目首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况然后直接上dp，由 i − 1 , i − 2 , i − 3 i…

【WC2016模拟】最假女选手

Description 维护一个序列，资瓷： 1：区间加 2：区间取max 3：区间取min 4：区间求和 5：区间求max 6：区间求min n<5*1e5 Solution 最近正在搞数据结构专题，于是找…

2017 ICPC西安 H Arrangement for Contests

题面题解线段树板子吧，维护一个区间最小值，懒标记更新即可代码 #include<bits/stdc.h>using namespace std; typedef long long ll; const int N 1e5 10;int T, n, k; ll a[N];struct Node {ll l, r;ll minn;// 最小值ll lazy; //向下更新…

LeetCode 第390场周赛个人题解

目录 100245. 每个字符最多出现两次的最长子字符串原题链接思路分析 AC代码 100228. 执行操作使数据元素之和大于等于 K 原题链接思路分析 AC代码 100258. 最高频率的 ID 原题链接思路分析 AC代码 100268. 最长公共后缀查询原题链接思路分析 AC代码 10024…

线段树 hdoj 1166 敌兵布阵

单点更新，区间求和敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 113122 Accepted Submission(s): 47399Problem DescriptionC国的死对头A国这段时间正在进行军事演习，所以C国…

[模板]单点修改，区间查询——java

package 模板;import java.util.Arrays; import java.util.Scanner;public class 线段树 {//单点修改，区间查询static int sum[]new int[40],a[]new int[40];//区间查询public static int que(int L,int R,int l,int r,int k) {if(L<l&&R>r) {return …