Vain的博客

$A - Eh$ $Ab$ $An$ $D$ $gCd$

思路：
显然$1$与任何数的$gcd$为$1$,与任何数的$lcm$都是两数中最大的，呢么直接构造$1,x-1$便是答案。

由于之前不会堆优化版本的dijstra，只会spfa算法，然后补题的时候想着用spfa算法过，没想到被卡了，所以去学了一手dijstra

这里讲一下两种算法的时间复杂度：
spfa:核心思想 bfs，时间复杂度，不好证明，这算法写起来挺简单的，跑随机图飞快，但出题人刻意卡的话，那这个算法就不行了。
dijstra: 核心思想贪心，时间复杂度On(logn)，用了优先队列，优化了普通dijstra找最小点距的位置

A:
思路：
用 6 10 14 15 去构造答案，因为只用前三个构造可能会出现重复的

传送门：

题目描述

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

输入格式

第一行一个整数N，表示我们要将1到N插入序列中。
接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk。（0<=Xk<=k-1,1<=k<=N）

输出格式

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

题目链接:
三数之和
题意：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：

传送门：

题意：

给长度为 n 的序列 和 限制值 k，求最长的子区间，子区间满足区间中任意两个数的差的绝对值不大于k

思路：
双单调队列，一个维护当前区间最大，一个维护当前区间最小，如果当前区间最大-最小满足条件，呢么当前区间整体满足条件，否则让单调队列中的除去当前存在的左端点即可

ios对cin的加速欺骗了我，md数据量稍微大一点就TLE了，不太靠谱，搞一波bbb群主的快读板子，用于对付卡常用，虽然一般感觉用不到叭，scanf够用了，但搞上一波没啥坏处

传送门：文艺平衡树
首先要阐述一点，Fhq Treap的按大小分裂是支持区间操作的，而按值分裂是不支持区间操作的。
Fhq Treap的分裂方式：

• 按权值分裂
• 按大小分裂

按权值分裂：

根据插入点的权值，将树按w为边界，分裂为两颗树，一颗树的权值大于w，一棵树的权值小于等于w，这样再把新节点合并进去，就可以维护树的平衡

按大小分裂：

根据插入点的节点大小，将树按big为边界，分裂为两颗树，一颗树的节点大小大于big，一棵树的节点大小小于等于big，这样再把新节点合并进去，不仅可以维护树的平衡，还支持区间操作

题意：

题目链接

给一个长为N的序列，求出所有子区间中位数组成的新序列的中位数

传送门

题意：
给长度为n的序列，询问区间中的元素个数(去重后的元素个数），m次询问，$n在[1,310^4], m在[1,210^5]$。

思路：
用主席树去写，每颗树存从[1,i]区间的信息，我们把这颗树中出现多次的数去重，只保最每个数在最右边出现的位置信息，其余位置的sum为0，然后询问时候，在含有当前区间信息的树中，进行区间求和