线段树属于二叉树, 其核心特征就是支持区间加法,这样就可以把任意待查询的区间$[L, R]$分解到线段树的节点上去,再把这些节点的信息合并起来从而得到区间$[L,R]$的信息. 下面证明在线段树上查询任意区间的复杂度是$O(\log{N})$的,$N$是区间总长度. 由于访问一个节点(即获得一个节点内与待查询区间$[L, R]$相关的信息)是$O(1)$的,只要证明查询一个区间要访问的节点数是$O(\log{N})$的. 如果某个节点完全包含在$[L,R]$内,则不会再向下查询,我们称这样的节点

发现每次区间加只能加1,最多全局加\(n\)次,这样的话,最后的答案是调和级数为\(nlogn\),我们每当答案加1的时候就单点加,最多加\(nlogn\)次,复杂度可以得当保证. 然后问题就是怎么判断答案是否该加1.我们可以用线段树设初值为给出的排列,把区间加改成区间减,维护最小值.当最小值为0是遍历左右子树,找到该加1的节点,一共会找\(nlongn\)次复杂度也可以得到保证. #include<iostream> #include<cstring> #include<c

题意 题目链接 Sol 这题关键是注意到题目中的\(b\)是个排列 那么最终的答案最多是\(nlogn\)(调和级数) 设\(d_i\)表示\(i\)号节点还需要加\(d_i\)次才能产生\(1\)的贡献 用线段树维护每个节点里\(d_i\)的最小值,每次当\(d_i - 1= 0\)的时候往下递归即可 时间复杂度:\(O(nlog^2 n)\) 多组数据记得清空lazy标记啊qwq.... #include<bits/stdc++.h> using namespace std; const

题面传送门 神仙题. 乍一看和经典题 花神游历各国有一点像,只不过多了一个区间加操作.不过多了这个区间加操作就无法再像花神游历各国那样暴力开根直到最小值为 \(1\) 为止的做法了,稍微感性理解一下即可明白,比方说你对一个已经全变为 \(1\) 的长度为 \(10^5\) 区间再加上 \(10^5\),那还需要 \(10^5\times\log 10^5\) 次区间修改操作才能变回原样,这样一来复杂度必然爆炸. 注意到我们对一个区间进行全局加,是不影响它的极差的,因此我们考虑用极差的角度思考这个

题解 传送门 题解 然而要我来说我感觉只是个爆搜啊-- //minamoto #include<bits/stdc++.h> #define R register #define ll long long #define ls (p<<1) #define rs (p<<1|1) #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;-

题目链接 问题在于操作二.操作二可以拆分成:区间加\(C\).区间(对\(0\))取\(\max\). 注意到操作一的\(C\)都是非负数,即数列中不会出现负数,所以我们直接维护最小值和最小值出现的次数即可得到操作三的答案. 操作一的赋值和操作二的加都是模板.但是取\(\max\)会影响最小值的个数(某些\(>mn\)的值可能一起变成最小值). 参照吉司机线段树,我们还需要维护严格次小值\(se\). 进行\(\max(v)\)操作时,若\(mn[rt]\geq v\),则直接返回:若\(se[

题目链接 可持久化线段树模板题. 这里总结一下可持久化线段树. 可持久化数据结构就是能恢复历史状态的数据结构,比如可持久化\(Trie\),并查集,平衡树. 可持久化数组是最基础的,这里通过可持久化线段树来实现. 可持久化线段树 ·复杂度:时间\(O(n\log n)\),空间\(O(m\log n)\). ·实现: 这里只针对单点修改的可持久化,区间修改是很复杂的. 可以发现,线段树的每次单点修改只会改变树上的\(\log n\)个节点,于是我们对这\(\log n\)个节点创建副本,如图(自

发现和SDOI2017树点涂色差不多 但是当时这道题模拟赛的时候不会写 赛后也没及时订正 所以这场模拟赛的这道题虽然秒想到了LCT和线段树但是最终还是只是打了暴力. 痛定思痛 还是要把这道题给补了. 但是对于这道题来说 暴力还是有价值的. 考虑20分 每次暴力dfs. 考虑对于树是随机生成的 那么期望高度为logn 我们发现每次修改只用修改到1 也就是说每次暴力修改颜色的话只需要logn的时间复杂度. 考虑如何动态维护子树内的值 考虑修改一个点的颜色 子树内之前和它颜色一样的点 显然子树内部整体

title : 可持久化线段树 date : 2021-8-18 tags : 数据结构,ACM 可持久化线段树 可以用来解决线段树存储历史状态的问题. 我们在进行单点修改后,线段树只有logn个(一条链)的节点被修改,我们可以让修改后的树与修改前的树共享节点,节省时间和空间. 在学习之前,我们先引入三个前置知识:离散化.动态开点,权值线段树. 离散化 对于较大的数据范围,只要将关键点记录下来,记录下rank,就能把数据缩小到可以接受的范围,以便建立线段树或其他数据结构来解决问题. 具体步骤 (

题目的意思是求重合层数最多的段(把点也看成段). 给的数据范围为N<1e5; ai<1e9; 有于N只有1e5;那么离散化一下可以将ai的范围映射到1e5,而不改变原端点的相对大小. 接下来用线段树来做就行了,要用lazy操作,到最后再把所有的值放下,然后比较每个点的大小,最大的就为重合最多的. 线段树复杂度为N*log(N); 1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4

题意 题目链接 单点修改,区间mod,区间和 Sol 如果x > mod ,那么 x % mod < x / 2 证明: 即得易见平凡, 仿照上例显然, 留作习题答案略, 读者自证不难. 反之亦然同理, 推论自然成立, 略去过程Q.E.D., 由上可知证毕. 然后维护个最大值就做完了.. 复杂度不知道是一个log还是两个log,大概是两个吧(线段树一个+最多改log次.) #include<bits/stdc++.h> #define Pair pair<int, int&g

地址:http://uoj.ac/contest/45 第一题是鸽子固定器. 只会10分.按 s 从小到大排序,然后 dp[ i ][ j ][ k ] 表示前 i 个元素.已经选了 j 个.最小值所在位置是 k 的最大代价. #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; int rdn() { ;;char ch=getc

时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:5791 解决:2649 题目描述: 有一个长度为整数L(1<=L<=10000)的马路,可以想象成数轴上长度为L的一个线段,起点是坐标原点,在每个整数坐标点有一棵树,即在0,1,2,...,L共L+1个位置上有L+1棵树.     现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树.     可能有M(1<=M<=100)个区间,区间之间可能有重叠.现在要求移

转载自:http://blog.csdn.net/shiqi_614/article/details/8228102 之前做了些线段树相关的题目,开学一段时间后,想着把它整理下,完成了大牛NotOnlySuccess的博文“完全版线段树”里的大部分题目,其博文地址Here,然后也加入了自己做过的一些题目.整理时,更新了之前的代码风格,不过旧的代码仍然保留着. 同样分成四类,不好归到前四类的都分到了其他.树状数组能做,线段树都能做(如果是内存限制例外),所以也有些树状数组的题目,会标示出来,并且放

转载LINK:LAZY_TAG 先看一个具体问题吧 PKU 3468 http://poj.org/problem?id=3468 题意很清楚 1 ≤ N,Q ≤ 100000. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000."Q a b" means querying the sum of Aa, Aa+1, ... , Ab. 用朴素的做法是O(NQ)的 明显

[题目描述 Description] 给一个 1 到 N 的排列{Ai},询问是否存在 1<=p1<p2<p3<p4<p5<…<pLen<=N(Len>=3),使得 Ap1,Ap2,Ap3,…ApLen 是一个等差序列. [输入描述 Input Description] 输入的第一行包含一个整数 T,表示组数. 下接 T 组数据,每组第一行一个整数 N,每组第二行为一个 1 到 N 的排列, 数字两两之间用空格隔开. [输出描述 Output Desc

题意: 给定一个n*n的矩阵,一个格子上可以放一个车.其中有q个子矩阵,且q个子矩阵互不相交或者是重叠(但边界可以衔接).这q个子矩阵所覆盖的地方都是不能够放车的.车可以越过子矩阵覆盖的地方进行攻击(车可以横着或者是竖着直走,就像象棋中的那样).现在问的是一共最多能够放多少个不能够互相攻击的车. 数据范围 1<=n<=10000,0<=q<=10000 输入格式 首先输入两个数字n,q,分别表示矩阵的大小和子矩阵的个数. 接下来有q行,每行四个正整数x1,y1,x2,y2,分别表示

线段树之——区间修改区间查询 1.概述 线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段(即“子数组”),因而常用于解决数列维护问题,基本能保证每个操作的复杂度为O(lgN). 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点. 对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b].因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长

Gold is everywhen! - somebody 启发式合并 将小的集合一个个插入到大的集合. 每次新集合大小至少比小集合大一倍,因此每个元素最多合并\(\log n\)次,总复杂度为\(n\log n\) × 插入复杂度. splay合并 将小的splay按中序遍历一个个插入到大的splay. 可证明复杂度为\(O(n\log n)\). 没什么特殊的应用. 线段树合并 int merge(int x, int y, int l, int r) { if(!~x) return y;

题面 给定一棵 \(n\) 个点的树,点带点权. 有 \(m\) 次操作,每次操作给定 \(x,y\) ,表示修改点 \(x\) 的权值为 \(y\) . 你需要在每次操作之后求出这棵树的最大权独立集的权值大小. 题解 如题所示 , 是个模板题 ... 首先考虑静态 \(dp\) , 令 \(dp_{u,0/1}\) 为 \(u\) 不存在 / 存在 于最大权独立集的权值大小 . 然后转移很显然 , 一个点存在于独立集中时 , 儿子全都不能选 . 不存在时 , 儿子可选可不选 . 令 \(v\)