线段tjoi 2007

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) ......

题目描述 将一个矩形分割成 \(n\) 个小矩形，每个小矩形的总分为这个矩形内所有数的和。求各矩形总分均方差最小值。 具体思路 先来几个定义。 均方差：$$\sqrt{\frac{1}{n} \times \sum_{i=1}^n (a_i-avg)^2}$$ 方差：$$\frac{1}{n} \t ......

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

有一些墙壁链接(ax,ay), (bx,by) 每次若有墙壁的两边一个有水，一个为空，墙壁就破了然后水开始充了起来 找出最后还存在的墙壁 首先我们可以看出来墙壁的两边是可以用节点表示的 我们需要合并一些区间什么的, 听说这一题有些人利用对偶图来求但是我不会 可以自己想想怎么样合并/哪个区间要合并 O ......

今天开始做IOI的学习笔记, 就从我出生的年份开始吧 IOI 2007 Aliens: 给你三个整数 N, X, Y 表示网格有N * N大， 而 （X，Y）是黑色的图 那个图是这样的： #.#.# .#.#. #.#.# .#.#. #.#.# #表示黑色 .表示白色 而整个N*N的网格只有一个这 ......

https://www.luogu.com.cn/problem/P3871 看题解有好几种做法 1、对顶堆：用两个堆，分别是大顶堆和小顶堆，维护一个动态的有序序列 我们首先将所有的数丢进大根堆里然后取一半丢进小根堆里，这样就把所有的数分成了两段有序的部分。 加入操作可以每次取小根堆堆顶和加入的数比 ......

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

P4309 [TJOI2013] 最长上升子序列题解 正文 单调队列?单调锤子队列！！ 本题的操作可以省略成： 单点修改 区间查询 好极了，此时我们有两种选择： 线段树和树状数组，（平衡树，真不会，下一位 因为不需要其他操作，所以我们还是选择更小巧更可爱的树状数组吧。 关于vector vector ......

修改操作可以很简单的在线段树上打标记即可。 常规做法直接二分 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]\) ......

[TJOI2013] 松鼠聚会 题解 切比雪夫距离 切比雪夫距离指的是在平面上的两个点\((x_1,y_1)\),\((x_2,y_2)\)之间横纵坐标之差绝对值中的大者。用公式表示则是\(f(a,b)=max(|x_a-x_b|,|y_a-y_b|)\)。 切比雪夫距离与曼哈顿距离之间可以相互转换 ......

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 ......

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

发现无论选择哪些逃跑的小矮人，只要存在可行逃跑顺序，那么按逃跑能力从弱到强依次逃跑肯定可行。这或许难以理解，但只要将逃跑的过程反过来就豁然开朗了：人梯高度单调不降，如果逃跑能力弱的都能够到，那还不如让逃跑能力强的先来增高。 所以排序后就可以 DP 了，令 \(f_{i,j}\) 表示前 \(i\) ......

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