线段p1803 79

李超线段树，简称李超树。它支持插入 **直线** 或 **线段**，并查询某个横坐标处的 **最值**。 本文以最大值为例，讨论广义李超线段树，与传统的李超线段树不同，它插入的是 **函数** 而非直线或线段，但为了保证正确的时间复杂度，对函数有较严格限制。 ......

CF633G 简单题。 先看到子树加和子树质数个数和，果断转换为 dfs 序进行处理。 既然有区间求和，考虑线段树。 若对于每一个节点维护一个 \(cnt\) 数组，用二进制数 \(x\) 来表示，即当 \(cnt_i = 1\) 时第 \(i\) 位为 \(1\)。设当前节点为 \(u\)，左右子 ......

CF1805E 待补：有另解 看到维护树上问题，可以想到线段树合并。 但直接维护显然不行，要一点技巧。 发现 \(val\) 的出现次数 \(cnt_{val}\) 如果 \(\ge 3\)，那么一定是一个候选项，若 \(cnt_{val} = 1\)，那么一定不能作为候选项。 于是可以用权值线段树 ......

线段树合并 引入 线段树合并就是把两颗线段树合并起来。 比如： 线段树 \(a\) 维护 \([1,1,2,0,0,2]\)。 线段树 \(b\) 维护 \([0,0,2,5,1,2]\)。 合并后的线段树 \(c\) 所维护的序列就是 \([1,1,4,5,1,4]\)。 解决问题 目前我所见到的 ......

动态开点 当到了未建立过的新点时再建立点，一般用结构体来存储线段树。 大致代码： #define lx tree[x].l #define rx tree[x].r #define mid ((l + r) >> 1) int cnt; struct node{ int l, r; int v; } ......

学习链接 代码（未完成） #include<bits/std++.h> using namespace std; int array[200005],tree[200005<<2]; // array是初始数组，tree是线段树 void update(int item) // 更新 item 号节 ......

蓝月の笔记——线段树篇 在树状数组中，我们讲解了关于单点修改区间查询的操作。今天，我们要讲一种更加高级的数据结构，他解决的是区间修改区间查询的问题多了一个区间当然更高级啦。 这个数据结构就是——线段树 Luogu - P3372 给定一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots, ......

应该是做的最认真的模板了。。。 namespace xds{ template<class T,const int MYMAXSIZE,T (*fun)(T a,T b)> class STree{ private: T t[MYMAXSIZE<<2],tag[MYMAXSIZE<<2],a[MYM ......

线段树 简介 线段树是可以维护 区间信息 的数据结构。线段树将每个长度不为 \(1\) 的区间划分成左右两个区间递归求解，故把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。 根据建树方式可分为普通线段树和动态开点线段树。 根据区间信息可分为普通线段树、权值线段树和李超线段树。 ......

适用场景：不断区间修改、区间询问。 假设我们要区间求和，\(tree\) 的含义：区间的和，其两个子节点为这个区间分为两半的和。 我们把一个数组 \(a\) 看作一颗树 \(tree\)，例： 1 1 2 3 3 3 对应的 \(tree\)（\(()\)里是编号，\([]\)里是对应的区间）： ( ......

今天的主题是线段树专题复习！ （什么？是昨天的？不听不听，只要我不说都不知道我鸽了一天！） 好了，言归正传，我们来看一下今天的知识点们吧。 Part 1 线段树自己 不想讲了，想看的移步其他博客 想看踢我，今天没时间了 Part 2 一些优化 ZKW线段树 俗称重口味线段树，是一种不用递归实现的线段 ......

前言： 继树状数组，一年后，kkk05终于决定把它的好兄弟——线段树附上。（明明一年前就学了但是今天才写的屑） 先简单地引入一下：P3372 忽略这道题的标题，看到这道题的第一想法大约是一维数组+m个循环+输出，照着这个思路写下去，不出意外的话，你将获得TLE。这时我们就该抬头看看标题：哦，什么是线 ......

算法：线段树 哦吼！终于来学线段树啦~~ 拖了好久都没有敢学，主要是基础知识点不熟，代码能力太弱。但是现在已经是时候了。 来看： 线段树（Segment Tree）几乎是算法竞赛最常用的数据结构了，它主要用于维护 区间信息 （要求满足结合律）。与树状数组相比，它可以实现 \(O(log⁡\ n)\) ......

一个很好用的 \(trick\)。 我们通过例题 CF786B 为例。 他需要我们支持点之间连边，点和区间之间连边，区间和点之间连边。 支持最短路。 如果我们暴力连边，显然最多是有 \(n^2\) 条边的。那怎么办呢，引入线段树分治。 线段树分治 在某些题中，我们可能会用 \(v \to u\in[ ......

目录裁剪算法Cohen-Sutherland线段裁剪算法基本思想具体步骤计算分析程序代码 裁剪算法 计算机内部存储的图形数据量通常较大，而屏幕只显示其中一部分，因此需要确定哪些部分在显示区域内，哪些在显示区域外。这个过程称为裁剪（clipping）。裁剪是二维观察（三维观察）的重要部分，参见计算机图 ......

8月集训学了权值线段树，当时没怎么加强训练。 国庆刚好开始有时间，巩固巩固。补上学习笔记。 首先介绍权值树。其本质是一个记录每个数出现次数的线段树，也就是由桶建成的树。 接下来介绍各种操作。 1.插入。 由于统计的是出现次数，从这个数往上依次加1即可。 void insert(int x,int l ......

最近特别喜欢用 NB 这个词。这是为什么呢？ 因为我太 NB 了。我怎么这么厉害呢？我好想朝所有人都嘚瑟嘚瑟！我真 NB！ 先开题吧。 A - 等差子序列 https://vjudge.net/contest/583230#problem/A 非常 NB 的一道线段树！但是现在没空所以先不写。 B ......

可撤销并查集 按时间顺序用一个栈维护合并信息，撤销时从栈顶弹出合并信息，恢复原状态。 并查集查找祖先时 不能路径压缩，只能按秩合并。 例题： [ABC302Ex] Ball Collector 容易想到将 \(A_i\) 和 \(B_i\) 之间连边。 遍历整棵树，用可撤销并查集维护图。 为了进一步 ......

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示 ......

含税79元即可运行Linux操作系统 对于嵌入式软件开发者而言，单片机令人最痛苦的莫过于文件操作。79元T113-i工业核心板（基于全志国产处理器，国产化率100%）可运行Linux操作系统，可使用Linux命令对文件进行一键操作，既方便又快捷。不仅如此，Linux操作系统还具备如下三大优点： (1 ......

今天太幸运了！硬啃把模板啃下来！ 树状数组 解决的本质问题 树状数组解决的本质问题只有一个： 单点改动、区间求值 其他的问题，都是可以转化到该问题上的。 代码板子重点操作 lowbit操作 int lowbit(int x){ return x & -x;} add添加一个值操作 void add( ......

线段树的特点 线段树的优势 线段树的构造过程 线段树的基本数据结构（结点结构由五个分量组成） 运行结果 （C语言代码）递归的创建一颗线段树，然后中序、先序、后序遍历这个结点 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typ ......

利用到的是，一条线段，只会出现两次。 那么，显然两次在线段树上遍历的节点是一样的，因此，我们可以直接修改定义，\(sum[cur]\) 表示线段树上的节点被多少条线段遍历到了，如果 \(sum[cur]>0\)，显然 \(cur\) 的贡献即区间长度，否则呢？否则，我们不需要考虑更大的区间，因为更大 ......

1.楼房重建 经典题。先转化题意，将斜率转化为每个点的权值，发现答案是单调递增的。那么就是求单点修改的最长上升子序列。 用线段树维护两个信息当前区间的最大值 mx，当前区间最长上升子序列长度 len。 修改时单点修改即可，考虑如何合并两个区间的 len。可以在线段树上二分。get(o, k) 维护当 ......

传送门 大致思路： 1. 将操作1拆分为两个部分x(-1)^d + kd*(-1)d。对于操作1中的x*(-1)d部分而言。我们可以对式子进行拆分，把x拆出来，我们会发现和v号点距离为奇数的点会减去x，为偶数的点会加上x，所以我们可以在线段树上用一个sum1维护应该减去的值，sum2维护加上的值即可 ......

李超线段树 概念 李超线段树是巨佬李超发明的一种可以求函数定点最值的线段树，又名李超树。代码简短，思想简明，用途广泛。 问题 李超线段树是用来解决类似于这种问题 题目传送门 要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 \(i\) 条被插入的线段的标号为 \(i\)。 给定一个数 ......

前言： 1.本篇文章为李超线段树的扩展，不会的可以去[这里](https://www.luogu.com.cn/problem/P4097 "这里") 这是我的模板： struct LCT { int tot=0,rt=0; struct Tree{int lc,rc,id;}tr[M]; ll A ......

教授要求规范代码风格，具体要求如下： 引用库命令和库名称之间加空格 例如 #include <cstdio> 运算符号两侧要加空格 例如 int a = 9 + 6; 大括号换不换行均可（但我倾向换行） 例如 for(int i = 0 ; i < N ; i ++) { // do somethi ......

一种离线处理方法 可以处理“具体哪个修改对询问有影响”、可以贡献不独立、可以支持插入删除。 例题 对这道题来说，对修改开线段树，线段树上每个节点开一个 \(vector\) 来维护出现在这段区间的线段，加入一个线段的区间，直接在区间查询时对所包含的节点压入这条线段就可以。 然后从根节点递归，先左子树 ......

线段树合并的时间复杂度是 \(O(m\log n)\) 的（\(m\) 为插入次数）。 int mer(int x,int y){ if(!x||!y)return x^y; t[x]+=t[y]; return L[x]=mer(L[x],L[y]),R[x]=mer(R[x],R[y]),x; ......