线段occurrences unique

线段树合并 引入 线段树合并就是把两颗线段树合并起来。 比如： 线段树 \(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\) 之间连边。 遍历整棵树，用可撤销并查集维护图。 为了进一步 ......

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

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

原题 对于一个树上问题，我们显然先考虑链上怎么做 多种颜色链上还是不会做怎么办？考虑只有黑白两种颜色 我们发现这个问题正着难算，我们就考虑用 $n \times m - $ 不满足条件的颜色个数，其中 \(m\) 为颜色种类 我们发现对于一个固定的点，他的答案即为 \(2n -\) 这个点所在的黑色 ......

利用到的是，一条线段，只会出现两次。 那么，显然两次在线段树上遍历的节点是一样的，因此，我们可以直接修改定义，\(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\)。 给定一个数 ......

写代码的时候想把一个张量\(X\)中的最后一个维度进行类似集合那样的操作，于是网上找到了torch.unique这个方法（官方文档） torch.unique(input, sorted=True, return_inverse=False, return_counts=False, dim=Non ......

前言： 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; ......

终于 1k AC 了家人，感动吧。 贺了很久，很累。 前置题目：P3320 [SDOI2015] 寻宝游戏 虚树的边权和： \[\sum dep_{a_x} - \sum_{x < n} dep_{a_x, a_{x + 1}} - dep_{a_{1}, a_{n}} \]考虑转化贡献，求过该点的 ......

P8946 The Lost Symbol 这种类型的 dp 的特点就是大部分转移形如 \(f(i,j)\rightarrow f(i+1,j+1)\) 之类的，并且当以上转移出现时原数组被清空，这就可以用一个 deque 来维护，然后对于全局赋值/全局加，需要对每个位置维护一个时间戳，并记录上一次 ......

线段树，合并！ 是啥 合并两颗动态开点线段树。 比方说我要合并两颗维护区间和的线段树，那么我就这样写： int merge(int x,int y,int s,int t){ if(!x||!y)return x|y; if(s==t){ tr[x].val+=tr[y].val; return x ......