::::info[数据结构] [线段树](https://www.luogu.com.cn/paste/58zvuc87) [树状数组](https://www.luogu.com.cn/paste/ewzvfsp3) [并查集](https://www.luogu.com.cn/paste/q1ea4oxh) [栈]…

# 基础 对于一些树上问题，如果不转化就很难求解。可以考虑转化为区间问题。 ## dfs序 可以发现，如果点 $x$ 的 dfn 被点 $y$ 入栈和出栈的时间戳完全覆盖，则 $x$ 一定在 $y$ 的一个子树内。 ## 树上差分 普通差分：序列上进行差分。 数上差分：子树上进行差分。 点差分的基础题型：给定一棵树，把…

rt，蒟蒻代码求调。 ```cpp #include using namespace std ; const int kMaxN = 1e4 + 5 , kMaxM = 5e4 + 5 ; struct node { int v , nxt ; }a[kMaxM , bool> mp ; int n , m , q ;…

在文章《题解：UVA567 Risk》发表评论：

666

[题目传送门](https://www.luogu.com.cn/problem/CF2008F) # 题意 发现 $Q$ 就是 $\frac{1}{2}n(n-1)$，难点在于 $P$。 看样例，如果两两相乘，复杂度 $O(n^2)$，不可行；突然发现求这个东西在小学比较常见，当时是用到了乘法分配律来简化求解，这题同…

[题目传送门](https://www.luogu.com.cn/problem/CF2014H) # 分析 发现答案就是对于区间 $[l,r]$，问是否所有 $l\le i\le r$ 的 $a_i$，都出现了偶数次。 区间问题，考虑莫队，发现莫队可行。 对于每个查询，先进行最优的排序。 然后每个询问，找到有多少个数…

# T1 二维偏序模版。 因为 $y_i #define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i = (b)) ; i += c ) #define T(i , root , b , c) for( int i = root ; b ; c ) //#defin…

在讨论《这个题是不是卡跳表》回复：

虽然我不会跳表，但是你的数组大小是 $2e7$，这个大小 $128MB$ 好像就炸了吧。

# T1 发现答案要求的是 $m$ 之前有多少个，所以考虑到树状数组。 发现是单点修改，区间查询的模版。 # T2 用线段树维护乘积。 把乘的节点变为 $m$，除就改为 $1$。 # T3 发现这道题把 $x$ 排序后，就是求 $y$ 的最大上升子序列和。 用树状数组维护区间最值即可。 ```cpp //Code by…

# T1 简单的分块模版，原题为守墓人。 # T2 容易想到前缀和，但是前缀和的复杂度为 $O(n^2)$，完全不能考虑。 想到树状数组也可以实现相同效果，且复杂度 $O(n \log n)$ 可以接受，树状数组模版即可。 # T3 与昨天的第三天相似，知识这次用的是树状数组。 维护两个树状数组，之后直接求贡献即可。…

[题目传送门](https://www.luogu.com.cn/problem/UVA567) # 题意 有 $20$ 个国家，给定第 $i$ 个国家能到的国家情况，这样的情况边权是 $1$。 问点 $u$ 到 $v$ 的最短路径的长度。 # 分析 发现 $n\le100$，考虑 `floyd`。 `floyd` 是…

# T1 发现如果 $r_i-l_i+1 // #define int long long #define ull unsigned long long #define ll long long using namespace std ; const int kMaxN = 3e5 + 5 , MOD = 998244…

# 基础 对于每个莫队，基本上都不带修改，如果要修改，需要进行一些操作。 记录每个查询前面有几个修改，然后莫队时修改即可。 # 例题 ## P1903 [国家集训队] 数颜色 / 维护队列 记录每个询问之前改变的个数，询问时改变即可。 ```cpp //Code by hhy #include #define F(i…

在讨论《92pts WA3 二维ST表玄关求条》回复：

@[bloxd](luogu://user/1373959) 没问题啊，$lg_1=0$ 确实是的啊

在讨论《92pts WA3 二维ST表玄关求条》回复：

@[bloxd](luogu://user/1373959) 这个地方减一和加一抵消了，且虽然我没有判，但是这不是错误原因

# 例题 ## P3834 【模板】可持久化线段树 2 发现这题和由乃打扑克有点相似，对于每个值都看是否在 $k$ 个值得范围，否则输出。 ```cpp //Code by hhy #include #define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i = (…

在讨论《92pts WA3 二维ST表玄关求条》回复：

@[bloxd](luogu://user/1373959)能再准确些吗？

在讨论《92pts WA3 二维ST表玄关求条》回复：

@[bloxd](luogu://user/1373959) 所以我哪里写错了？？？

在讨论《92pts WA3 二维ST表玄关求条》回复：

@[bloxd](luogu://user/1373959) 所以怎么改，急

rt。 ```cpp #include using namespace std ; int n , m ; int st[1005][1005][15] , lg[1005] ; bool check(int x) { for( int i = 1 ; i + x - 1 = x) { return 1 ; } } }…

# 基础 如果要求 $[2,4]$ 的和，可以看成 $[2,5]-a_5$，莫队的基本模版就是这种思路对于每个询问进行加或者减的操作。 发现对于每个询问进行改变的距离和就是曼哈顿距离的和。、 为了让这个值尽可能小。如果在一个块内那么就按有边界排序；否则是左边界。 # 例题 ## P3901 数列找不同 用数组记录是否出…

# 基础 今天的题目对于分快来说，都需要进行一些优化。比如说在二分时对于全部大或者全部小时的优化；二分上下界优化等等。 分块的复杂度是整块的个数加上 $2\sqrt{n}$，$2\sqrt{n}$ 则是部分块的复杂度。 # 例题 ## P4109 [HEOI2015] 定价 发现这道题，就是对于一个较大的数，让它尽可能…

# 基础 一般来说，分块的复杂度优化是在整块的部分，但是今天的一些题，需要对部分块进行一些优化。 # 例题 ## P2801 教主的魔法 这题和做题的模版题相似，就是进行排序，找值即可。 ```cpp //Code by hhy #include #define F(i , a , b , c) for( int i…

# 基础 分块就是把一个序列分成很多块，然后查询、修改时，对于整个块进行修改。 需要注意的是，分块只是一种思想，而不是一种算法。 写分块时，一般把长度设为 $\sqrt{n}$，当然，也有的题卡这个数，所以需要一些调整。 发现如果一整块都要修改时，如果都修改，时间很慢，所以用懒标记记录整个块的加减情况。 # 例题 ##…

# T1 割边模版，我没有想到不连通。 ```cpp #include #define int long long using namespace std ; const int kMaxN = 55 ; struct node { int v , nxt ; }edge[kMaxN * kMaxN] ; int lo…

# T1 tanjan 模版，看是否有一个强连通大小大于一。 ```cpp //Code by hhy #include //#define int long long #define ull unsigned long long #define ll long long using namespace std ; c…

[题目传送门](https://www.luogu.com.cn/problem/P12760) # 题意 计算每个点可以到达的点的个数。 # 分析 前置知识：[强连通分量](https://oi.wiki/graph/scc/)。 这题是强连通分量的拓展缩点，发现一个强连通分量所有点都可以到，所以可以看作一个点。 这…

# 基础 割点（割顶）：删除一个点，图的联通分量增加，这个点就是割点。 割边（桥）：删除一个边，图的联通分量增加，这个边就是割点。 # 例题 ## P3388 【模板】割点（割顶） 对于儿子能会到的点大于等于现在的点，且儿子个数大于二也不是根节点就是。 ```cpp //Code by hhy #include #de…

# 题意 求斐波那契数列的第 $n$ 项模上 $2 ^ m$ 的值。 # 分析 前置知识：[矩阵加速](https://oi.wiki/math/linear-algebra/matrix/#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95)。 矩阵的三种功能： 1. 解方程（省选）。 2. 加…

# 基础 scc：强连通分量。 scc 缩点：得到的一定是 DAG（有向无环图）。 # 例题 ## HDU2767 Proving Equivalences 和昨天作业题相同。 对于缩点后的每个颜色，记录入度和出度。 随后，因为如果要全部称为强连通，就要所有入度和出度不为 0。 ```cpp //Code by hhy…