线段 例题
loj144&145 dfs序+树状数组/线段树
[https://loj.ac/p/144](loj144) [https://loj.ac/p/145](loj145) 两题非常相似，一题的权值修改是在点上的，一题的权值修改是在整棵子树上的。 首先我们要了解dfs序，并记录每个节点的子树大小sz，对于一个节点，在dfs序上sz长的区间全都是他的 ......
【模板】线段树1（洛谷P3372）
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 template <class T> 7 inline void read(T &s) 8 { 9 s = 0; 10 int w = 1; 11 char ......
可视化学习：利用向量计算点到线段的距离并展示
向量运算是计算机图形学的基础，这个例子就是向量的一种应用，是利用向量来计算点到线段的距离，这个例子中可视化的展示采用Canvas2D来实现 ......
【线段树优化 dp】AT_dp_w Intervals 题解
AT_dp_w 先不看数据范围，考虑 dp。 令 \(f_i\) 表示前 \(i\) 个字符且强制第 \(i\) 个字符为 \(1\) 的最大分数。 则 \(f_i = \max(f_{j - 1} +\sum\limits_{r_k\ge i\ge l_k\ge j}a_k)\)。 这个是一份 \ ......
线段树好题汇总(持续更新中)
线段树作为信息竞赛中最为常用的数据结构之一, 常常是区分非竞赛选手和竞赛选手的显著标志 其中最为有趣的就是有关区间可加性的探讨, 这里将会放一些我自认为可以学到东西的线段树题目, 同时也会附赠上自己的一些思考, 助读者加深对线段树的理解 Educational Codeforces Round 23 ......
第 372 场周赛(位运算技巧，跳表 + 二分，线段树）
class Solution: def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int: cnt = 0 for a, b, c in zip(s1, s2, s3): if not a == b == c: break c ......
[学习笔记]主席树（可持久化权值线段树）
注：本蒟蒻第一次用 html 写文章，可能写的不是很好 主席树简介 主席树，全称为可持久化权值线段树。 有的人不知道什么是可持久化，其实很好理解，就是某个 mhy 游戏最早是 1.0 版本，至今到了 4.2 版本，可持久化就是可以在 1.0 ~ 4.2 版本间任选一个版本出来进行修改。 例题1 P3 ......
【每日例题】 蓝桥杯 c++ 冶炼金属
冶炼金属 题目 小蓝有一个神奇的炉子用于将普通金属О冶炼成为一种特殊金属X。这个炉子有一个称作转换率的属性V,V是一个正整数，这意味着消耗V个普通金属О恰好可以冶炼出一个特殊金属X，当普通金属О的数目不足V时，无法继续冶炼。现在给出了Ⅳ条冶炼记录，每条记录中包含两个整数A和B，这表示本次投入了A个普 ......
线段树-多个懒标记pushdown
P3373 【模板】线段树 2 这里需要用到两个懒标记，一个懒标记为add，记录加，另一个懒标记为mul，记录乘。 我们需要规定一个优先级，然后考虑如何将懒标记下传。 这里无非有两种顺序，一种是先乘后加，另一种是先加后乘。 我们先看先加后乘。 \[(sum + add1) * mul1 \]当我们的 ......
abc327F - Apples（线段树）
https://atcoder.jp/contests/abc327/tasks/abc327_f 我们将时间看作x轴，位置看作y轴，那么我们随着时间增加，维护新加的点对区间的贡献，同时减去过时的点，线段树区间加法维护最大值即可。 #include<cstdio> #include<algorith ......
JS判断点是否在线段上
本文利用向量的点积和叉积来判断点是否在线段上。 基础知识补充 从零开始的高中数学——向量、向量的点积、带你一次搞懂点积（内积）、叉积（外积）、Unity游戏开发——向量运算（点乘和叉乘 说明 点积可以用来判断两个向量的夹角，如果这个夹角是0或者180度，说明这个点在直线上； 叉积可以用来判断一个点到 ......
【每日例题】蓝桥杯 c++ 小郑下五子棋
小郑下五子棋 题目 五子棋是—种两人对弈的棋类游戏，它使用黑白两种棋子在一个20×20的棋盘上进行。黑方执黑棋，白方执白棋。双方轮流下棋，目标是先在横向、纵向或斜向连成五个己颜色的棋子，即五子相连，即可获胜。五子棋是—种简单却富有策略的游戏，常常被用于智力训练和竞技比赛。这不，小郑在和小张玩五子棋， ......
【每日例题】蓝桥杯 c++ 被替换的身份证
被替换的身份证 题目 蓝桥杯 被替换的身份证 思路分析 斗地主简化版？！废话少说，四种情况 ShallowDream一开始出对子或者王炸，ShallowDream胜 ShallowDream一开始出单，Joker出王炸，Joker胜 ShallowDream一开始出单，Joker手中最大的牌比Sha ......
李超线段树
极其BT的东西，又卡精度又卡边界情况，代码还异常长（依托答辩）。 解决问题 给出一堆线段或直线（\(log^2\) 或 \(log\) 复杂度），问某个 \(x\) 坐标上最高的线。可以搭配 \(DP\) 进行转移上的优化，常见模型为 \(n^2\) 的 \(f_u=min(a_u\times a_ ......
线段树
线段树引入遇到过好多次线段树的题目，要么就是用其他的方法去解决，要么就是不会写！！今天痛定思痛，决定好好归纳整理一下线段树 线段树解决的是「区间和」的问题，且该「区间」会被修改 什么意思呢？举个简单的例子，对于 nums = [1, 2, 3, 4, 5] 如果我们需要多次求某些区间的和，是不是首先 ......
2023-11-11：用go语言，字符串哈希+二分的例题。 给定长为 n 的源串 s，以及长度为 m 的模式串 p， 要求查找源串中有多少子串与模式串匹配， s‘ 与 s 匹配，当且仅当 s‘ 与 s
2023-11-11：用go语言，字符串哈希+二分的例题。 给定长为 n 的源串 s，以及长度为 m 的模式串 p， 要求查找源串中有多少子串与模式串匹配， s' 与 s 匹配，当且仅当 s' 与 s 长度相同，且最多有 k 个位置字符不同。 其中 1 <= n, m <= 10^6，0 <= k ......
【每日例题】蓝桥杯 c++ 手机尾数
手机尾数 题目 30年的改革开放，给中国带来了翻天覆地的变化。2011全年中国手机产量约为11.72亿部。手机已经成为百姓的基本日用品!给手机选个好听又好记的号码可能是许多人的心愿。但号源有限，只能辅以有偿选号的方法了。这个程序的目的就是:根据给定的手机尾号(4位)，按照—定的规则来打分。其规则如下 ......
【每日例题】蓝桥杯 c++ 报纸页数
报纸页数 题目 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。×星球日报和我们地球的城市早报是一样的，都是一些单独的纸张叠在一起而已。每张纸印有4版。比如，某张报纸包含的4页是:5,6,11,12，可以确定它应该是最上边的第2张报纸。我们在太空中捡到了一张×星球的报纸，4个 ......
理解线段树和主席树：解决区间操作的利器
在计算机科学和算法领域，区间操作问题是一类常见且重要的问题，它们涉及到在一维数据结构中执行查询和更新操作。线段树和主席树是两种用于解决这类问题的强大数据结构。本文将介绍这两种树状数据结构，以及它们在不同应用领域中的使用。 什么是线段树？ 线段树是一种用于处理区间操作问题的数据结构，它的核心思想是将一 ......
原点到线段的垂足
原理： 1) 求出向量ao在ab上的投影距离 2) a沿着ab方向移动投影距离就是垂足点的位置 // 获得原点到直线ab的垂点 public static Vector2 GetPerpendicularToOrigin(Vector2 a, Vector2 b) { var ab = b - a; ......
【每日例题】蓝桥杯 c++ 绘制表格
绘制表格 题目 蓝桥杯 绘制表格 题目分析 阅读题目，我们可以将表格分为四个部分，头、中间的竖线部分与横线部分、尾。因此，我们可以启用多个for循环分别解决 在第一行，我们也可以分为三个部分，第一部分符号为：“┌”，第二部分的中间部分使用for循环输入：“─┬”，第三部分符号为：“─┐” 在最后一行 ......
线段树历史值
P6242 【模板】线段树 3 支持区间加，区间取 \(\min\)，区间求和，区间 \(\max\)，区间历史 \(\max\)。 先提一嘴吉司机。 就是对线段树的每个节点记录最大值，严格次大值和最大值个数，只在 \(se<v<mx\) 的区间操作，否则向下递归。如果没有区间加，复杂度势能分析是 ......
利用realloc函数调整栈帧学习以及相关例题学习
前言: 在前面学习malloc_hook的时候，我们会用到one_gadget,但是我们也知道，one_gadget是有要求的，如果当我们四个one_gadget都不满足要求该如何做，那么我们就可以利用realloc来调整栈帧来使得符合条件，当然如果找完了也不符合那就寄了(,同样的在调用reallo ......
【每日例题】蓝桥杯 c++ 国王的遗产
国王的遗产 题目 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。国王的遗产×国是个小国。国王K有6个儿子。在临终前，K国王立下遗嘱:国王的一批牛作为遗产要分给他的6个儿子。其中，大儿子分1/4，二儿子1/5，三儿子1/6，....直到小儿子分1/9。牛是活的，不能把一头牛切 ......
【每日例题】蓝桥杯 c++ 年龄巧合
年龄巧合 题目 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。小明和他的表弟—起去看电影，有人问他们的年龄。小明说:今年是我们的幸运年啊。我出生年份的四位数字加起来刚好是我的年龄。表弟的也是如此。已知今年是2014年，并且，小明说的年龄指的是周岁。请推断并填写出小明的出生年 ......
Exhausted? 题解（线段树）
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, ......