线段note

## 简介 权值线段树是一种建立在基本线段树之上的数据结构。因此它的基本原理仍是基于对区间的维护操作。但权值线段树维护的信息是： **一段区间内数出现的个数** 实际上，权值线段树跟树状数组相似，都可以看作是一个桶。因此，根据权值线段树的性质，我们可以知道其主要用途： **求一段区间内数出现的次数、 ......

[传送门](https://loj.ac/p/6029) ``` #include using ll = long long; const int N = 1e5 + 10; const int MOD = 1e9 + 7; const ll INF = 0x3f3f3f3f3f3f3f3f * 2 ......

## 区间第K大板子(动态开点) ``` int n, m; int root[N], idx; struct node{ int l, r; int cnt; }tr[N * 40]; void pushup(int u){ tr[u].cnt = tr[tr[u].l].cnt + tr[tr[ ......

#### 题目链接 http://118.190.20.162/view.page?gpid=T162 #### 题意 一个网络地址由 $n$ ($n \leq 512$ ，且是16的倍数)位二进制位组成（形如 xxxx:xxxx: .... :xxxx），有若干用户需要申请一些网络地址。 有三种操 ......

给定长为 $n$ 的数组 $a$，如下定义 $g(i,j)$：当 $i \leq j$ 时，$g(i,j)$ 是满足 $\{ a_p : i \leq p \leq j \} \subseteq \{a_q : x \leq q \leq j\}$ 的最大整数 $x$。否则 $g(i,j) = 0$ ......

让我们来一步一步理解！ 1.向上更新 void push_up(int rt){//向上更新 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } 2.向下更新 void push_down(int rt, int m){ if(add[rt]){//若有标记,则 ......

[THUSCH2017] 大魔法师 ​ 给定 $n$ 个三元组 $(A,B,C)$ 。共有 $m$ 种区间操作，分为三大类，七小类。 1.$A_i=A_i+B_i$ 2.$B_i=B_i+C_i$ 3.$C_i=C_i+A_i$ 给定值 $v$ 4. $A_i=A_i+v$ 5. $B_i=B_i\ ......

传送门 ** 出现最大路径权值就应该联想到克鲁斯卡尔重构树，我们对于克鲁斯卡尔重构树求一遍dfs序，维护所有白色点的最大最小dfn（包括出发点），求出最大最小dfn的最近公共祖先既是答案。注意需要特判一下除了本身以外没有白色点情况。** #include <bits/stdc++.h> int n, ......

可持续化线段树 前言： “这个数据结构是属于比较抽象的一类。并且代码实现比较繁琐复杂。” 别人都这么说，我却觉得挺好理解、也挺好写的（可能是因为我曾经与多道线段树毒瘤题抗争多次）。 为了避免以后我突然脑子抽了不记得了，可以拿出来看看。所以写下这篇笔记，希望也能帮到大家。 建议：带上一个清晰的脑子（草 ......

在已经掌握线段树的基本用法后的做题整理。给自己复习用的。 用 $mid$ 表示 $(l+r)/2$，$u$ 表示当前区间节点（父区间），$ls,rs$ 分别表示当前区间的左、右子区间节点。 普通维护序列 P2023 [AHOI2009] 维护序列 修改：区间加，区间乘；询问：区间求和。 双倍经验：P ......

一、题目描述： 维护这样的一个长度为 $n$ 的数组，支持以下两种操作 $1$：在某个历史版本上修改某一个位置上的值 $2$：访问某个历史版本上的某一位置的值 每进行一次操作，就会生成一个新的版本（对于操作2，生成的就是一个完全一样的版本）。 版本编号即为当前操作的编号（从 $1$ 开始编号，版本 ......

1. [TJOI2018]数学计算 题目描述 小豆现在有一个数 $x$，初始值为 $1$。小豆有 $Q$ 次操作，操作有两种类型： 1 m：将 $x$ 变为 $x \times m$，并输出 $x \bmod M$ 2 pos：将 $x$ 变为 $x$ 除以第 $pos$ 次操作所乘的数（保证第 $ ......

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" const int N = 1e5 + 5; vector<int>vec; struct BIT { int c[N]; voi ......

浅谈有限域在 OI 中的一些应用 (2023 国家集训队论文), 戚朗瑞. $\textbf{Example 1.}$ 给定一张有向图 $G=(V,E)$, $|V|=n$, $|E|=m$. 要求找到一条最长的简单路径. 保证最长路径长度 $k\ll n$. $\textbf{Solution 1 ......

DGL 教程阅读笔记 Datetime: 2023-03-27T17:29+08:00 Categories: Python | MachineLearning 教程网址：https://docs.dgl.ai/en/latest/index.html 毕设的笔记，只能给自己看，换一个人或者过一段时 ......

可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。主席树全称是可持久化权值线段树，给定 nn 个整数构成的序列 aa，将对于指定的闭区间 [l,r][l,r] 查询其区间内的第 kk 小值。 可持久 ......

可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。 主席树全称是可持久化权值线段树，给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $\left[l, r\right]$ 查询其区间内的 ......

关键原则 1. 编写清晰具体的指令 1.1 使用限定符区分prompt 和 文本 Pasted image 20230430123729 1.2 结构化输出 Pasted image 20230430123839 1.3 要求模型检查是否满足条件 Pasted image 2023043012391 ......

第一次写的时候还不会线段树的动态开点，写了一个是线段树但是是$O(N^2)$的写法，现在用动态开点武装了自己，会了正解$O(qlog n^2)$。首先建立一个权值线段树，但这里的权值很大，通过动态开点去建树来节省空间，对于两种操作： 操作1，常见的动态开点的单点修改 操作2，二分答案，然后在线段树上 ......

Segment tree beats 吉老师线段树 Segment tree Beats!.pdf_免费高速下载|百度网盘-分享无限制 (baidu.com) 为广大oier们提供学习ppt（笑） ==历史最大值未完工== 作用 用于维护区间最值和区间历史最值的线段树 区间最值 引入 问题 给定一个 ......

你说的对，但是你理应会动态开点线段树是什么东西。 合并很简单，两棵线段树一块搜，然后逐个节点合并。 分裂的话可以按照 FHQ Treap 的方法。假如我们将前 $k$ 小和后边分开成 $x,y$，首先看左子树，如果比 $k$ 大那右子树给 $y$，递归左子树，反之左子树给 $x$，递归右子树。 真没 ......

tea,xtea,xxtea 在逆向过程中，常常会遇到tea加密，本文将系统地总结一下tea,xtea,xxtea tea 简介 TEA加密算法是一种分组密码算法，其明文密文块为64比特，密钥长度为128比特。TEA算法利用不断增加的Delta(黄金分割率)值作为变化，使得每轮的加密是不同，该加密算 ......

线段树又称区间树, 是一种基于分治思想的二叉树结构, 每个节点代表一段区间 线段树的每个节点代表一个区间 对于每个内部节点 [l,r] , 它的左儿子是 [l,mid] , 右儿子是 [mid+1,r] 用一维数组存整棵树 $$ 对于编号为x的节点 \begin{cases} 父节点: [\dfra ......

A credit note or credit memo is a commercial document issued by a seller to a buyer. Credit notes act as a source document for the sales return journa ......

二维数点，对于询问的$[l, r]$区间我们只需要统计有多少个数上一次出现的位置$pos$ 满足$pos \leq l$，即可。 template<class T> struct BIT { T c[N]; int size; void resize(int s) { size = s;} T qu ......

第K小数 // AC one more times #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define endl '\n' #def ......

【模板】普通平衡树 // AC one more times #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define endl '\n' ......

这是一道很简单的的题，甚至都说不出来它有什么考点，如果非要说的话，可能需要对ida、gdb、栈不那么陌生吧。 ......

1.基础算法 1.1快读快写 template <typename T> inline void read(T& t) {​ int f = 0, c = getchar(); t = 0; ​ while (!isdigit(c)) f |= c == '-', c = getchar();​ w ......

学习自 数据结构学习笔记(5)动态开点线段树 动态开点线段树 感谢大佬们博客的帮助 // AC one more times #include <bits/stdc++.h> using namespace std; #define fi first #define se second #defin ......