线段

原理： 1) 求出向量ao在ab上的投影距离 2) a沿着ab方向移动投影距离就是垂足点的位置 // 获得原点到直线ab的垂点 public static Vector2 GetPerpendicularToOrigin(Vector2 a, Vector2 b) { var ab = b - a; ......

P6242 【模板】线段树 3 支持区间加，区间取 \(\min\)，区间求和，区间 \(\max\)，区间历史 \(\max\)。 先提一嘴吉司机。 就是对线段树的每个节点记录最大值，严格次大值和最大值个数，只在 \(se<v<mx\) 的区间操作，否则向下递归。如果没有区间加，复杂度势能分析是 ......

Exhausted? 题解 前言： 看本篇题解，您如果想要掌握所有知识点的话，请您先去了解下什么是霍尔定理，当然如果可以的话，可以去看看我的这个博客。 涉及的算法和思想知识点： 线段树、扫描线。 霍尔定理。 较少的容斥原理。 正文： 理论分析： 从简单入手：我们想想，要是值域再小一点的话，我们可以怎 ......

空间复杂度，一般是根据操作次数来计算的，或者按照题目的空间，算出最大开多少数组。 根据感性理解，线段树的深度是\(\lceil log_2n\rceil\)的，反正\(d = \lfloor log_2n\rfloor+1\)肯定够。 那\(m\)次操作，注意这个操作不一定是原题中的询问，而是你对于 ......

ap1×ab与ap2×ab的结果异号，则表示两点在线段两侧；同号则表示在线段同侧 有一个点在线段上或两个点都在线段上，当做在线段同侧处理 //两点是否在线段同侧 public static bool IsTwoPointSameSideOfSegment(Vector2 a, Vector2 b, ......

大致解决的问题就是区间查询以及单点的修改 #include<bits/stdc++.h> #define int long long using namespace std; const int N=5e5+10; int a[N],tag[N<<2]; struct{ struct{ int l, ......

几种要考虑的情况 1) 点p和线段断点a, b重叠，pa•ab=pa.x*pa.y+ab.x*ab.y=0 2) pa, pb共线，则pa×pb=0 2-1) p在线段ab上，此时pa, pb的夹角为180度，cos(180)=-1，pa•ab=-|pa|*|ab| 2-2) p在线段ab外，此时p ......

几种要考虑的情况 1) 点p和线段断点a, b重叠 2) pa, pb共线, p在线段ab上 3) pa, pb共线, p在线段ab外 4) pa, pb不共线 //点是否在线段上 public static bool IsPointOnSegment(Vector2 p, Vector2 a, V ......

几种要考虑的情况 1) 点和线段两端重叠的情况 2) 点在线段两侧的情况 p在另一侧的情况以此类推 3) 点在线段中间的情况 //点到线段的距离 public static float PointToSegmentDistance2(Vector2 p, Vector2 a, Vector2 b) ......

#include<bits/stdc++.h>#define int long longusing namespace std;const int N=5e5+10;int a[N],tag[N<<2];struct{ struct{ int l,r,sum; }tr[N<<2]; void pus ......

无区间最值操作 这里讲两种简易方法： 1.矩阵 考虑线段树的 \(tag\) 必须要有结合律，几个值互相更新，考虑矩阵乘法去实现这个操作。 例题 支持区间加，查询区间和，区间历史版本和。 考虑记一个点的状态为： \[\begin{bmatrix} his\\ sum\\ len \end{bmatr ......

矩阵乘法与线段树标记 让我们回归本质，将一切线性操作归为矩阵。 目录矩阵乘法与线段树标记线段树区间加线段树历史版本和线段树历史版本最大/最小值线段树区间取 \(\min\) 与历史版本最大NOIP2022 比赛优化标记常数关于向量构造的一些小技巧作者有话说 线段树的懒标记是非常普遍且巧妙的，但是对于 ......

P2251 质量检测 正解应该是ST表和单调队列，不过对于这道题来说只有查询没有修改，这里我还是想用线段树和分块来写，不得不说分块是真好，优雅的暴力 线段树版本： #include <bits/stdc++.h> #define LL long long using namespace std; c ......

一个点在圆内 两个点都在圆内 两个点都在圆外 public static bool IsSegmentCircleIntersect(Vector2 p1, Vector2 p2, Vector2 center, float r) { float sqrR = r * r; //1) 一个点在圆内, ......

不在两侧时 在两侧时 //点是否在线段两侧 public static bool IsPointSideOfLine(Vector2 p, Vector2 a, Vector2 b) { var ap = p - a; var ab = b - a; if (Vector2.Dot(ap, ab) ......

F. Unique Occurrences 假如我们删除所有权值为x的边，那么所有权值为x的边对答案的贡献就是 \(\sum sz[u]*sz[v]\) sz表示两个联通块的大小，且(u,v)的边权为x 我们可以用可撤销并查集来进行处理，简单来说就是将一条边的存在时间看作区间，然后挂到线段树上，然后 ......

线段树专题 （该笔记持续更新中...） 一、基本操作 1.单点修改/查询： 2.区间修改/查询： 需要用到 lazy_tag 技术，即每次修改不会立刻修改涉及到的每一段区间，而是等到下一次修改要用到或者是要查询该区间时再更新，这样可以将每次修改和查询的复杂度控制在 \(O(log_2N)\) 3.总 ......

修改操作可以很简单的在线段树上打标记即可。 常规做法直接二分 R 然后区间查询 gcd，复杂度是仨log。 upded：其实也是俩log，线段树查询区间gcd是单 log。 注意到你会将区间拆分成 log 个子区间，直接查询他们的 gcd 即可，直接查询为什么不会多乘个 log 呢。 注意到对两个数 ......

本题为双指针和贪心。当我们遇到奇数个0或1时，直接将下一位改变即可。 class Solution { public: int minChanges(string s) { int n = s.size(); int res = 0; int l = 0, r = -1; while(r ++ < ......

传送门 线段树大模拟!。考验线段树功底的时候来了，作为队伍的史山选手，写这么史也是情有可原的。 #include <bits/stdc++.h> using ll = long long; const int INF = 0x3f3f3f3f; const int N = 1e6 + 10; typ ......

定义函数 \(\Phi(T)\) 为当前树 \(T\) 中不同数的数量，易证明上限为 \(|T|\)。并规定整棵线段树的大小 \(= n\)。 我们再定义一个概念：对于一个线段树节点，如果它对应的区间包含于 \(\min\) 操作的区间 \([l, r]\)，且它的祖先不包含于 \([l, r]\) ......

P4097 【模板】李超线段树 / [HEOI2013] Segment 强制在线，那么这种问题该如何解决？ 我们可以把任务转化为维护如下操作： 加入一个一次函数 给定 \(k\)，求定义域包含 \(k\) 的所有一次函数中，在 \(k\) 处取值最大的那个，如果有多个函数取值相同，选编号最小的。 ......

主席树的定义 主席树，也称可持久化线段树，什么是可持久化线段树呢，即为一颗记录了所有更新过程的线段树。能够处理出从第 $i$ 次更新到第 $j$ 次更新的线段树变化。 前置知识 值域线段树 值域线段树的区间存的并不是节点信息，而是在值在某一范围内的数的个数。 如图就是一棵值域线段树。 1号节点存储的 ......

20231026 P5537 【XR-3】系统设计 题解-哈希+线段树二分 这个东西怎么会和哈希有关？！直接寄。 Statement 这个系统首先需要输入一棵 \(n\) 个点的有根树和一个长度为 \(m\) 的序列 \(a\)，接下来需要实现 \(q\) 个操作。 操作分两种： 1 x l r 表 ......

P3870 [TJOI2009] 开关 思路：可以用线段树来维护区间中亮灯的个数，区间修改用加上懒标记就好 #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e5 + 10; struc ......

猫树 猫树 线段树分治 ......

原发表于个人博客。 前言 线段树，是数据结构皇冠上的明珠（我编的）。 它用途广泛，被一代代的oier应用，改进，优化。 本文介绍了线段树的基础知识和各种拓展（包括权值线段树，可持久化线段树），各种优化方式（包括zkw线段树，动态开点，离散化），希望能帮到更多的oier。 在学习线段树前，默认你应该学 ......

前置知识：动态开点权值线段树。 线段树合并，顾名思义，就是将两棵权值线段树合并在一起。为什么不把两棵普通的线段树合并呢？因为那样好像没啥用。 我们知道，权值线段树支持着查询某个数的个数、查询第 \(k\) 大/小的数等操作，有了合并操作之后就可能会支持一些令人意想不到的操作。 放张图，可以帮助理解下 ......

快速排斥 快速排除不可能相交的情况 1 2 3, 4 但类似下面这类情况，矩形区域相交，但线段没相交的就无法处理了 跨立实验 若两线段相交，则两线段必须跨立。就是：线段a1a2与线段b1b2相交，则a1和a2一定在线段b1b2的两侧。 2d向量叉乘v1×v2，可以用来判断v2在v1的右手逆时针180 ......

李超线段树是一种按照值域维护一次函数最值的数据结构，其核心在于一次函数和值域的双单调性。 如果预先对于值域离散也可以维护其最值。 也就是说只要满足时一次函数，以及下标的单调性都可以利用李超线段树维护。 李超线段树就是利用线段树来维护一次函数的最值，每一个结点对应了一个区间 \([l, r]\)。 我 ......