Splay 模板
Splay 数组实现模板
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Node {
int son[2], p;
int sz, cnt;
int val;
void init(int v, int par) {
val = v, p = par;
sz = 1;
cnt = 1;
son[0] = son[1] = 0;
}
} Tree[N];
int root = 0;
// Splay
void update_size(int p) {
Tree[p].sz = Tree...
2022 牛客多校第四场题解
D - Jobs (Easy Version)
有 $n(n \le 10)$ 个公司，每个公司有 $k$ 个职位。每个职位都有三维[a , b , c]的要求，现在有 $q$ 名求职者，每个求职者的三维必须大于等于需要的职位的三维才可以被采纳。
求问，每个求职者最多可以收到几家公司的 offer。
由于本人的能力有限，只给出 Easy Version 的解。
在这个问题中，我们发现题目的突破口是在 [a , b , c] 的范围，他们最大的值仅有 400， 因此我们不妨通过设置 need[i][a][b] 来表示这样的值，在公司 $i$ ，能力值为 $a$ ， $b$ 且可以被公司接纳的情况下，的情况下，$c$ 的最小值。
然后对于一个公司而言，我们可以得到 need[i]...
Treap 模板
此篇仅仅作为模板使用，以 普通平衡树 为例题完成。
旋转Treap | 指针实现
#include <ctime>
#include <iostream>
#include <random>
using namespace std;
signed gen() {
static mt19937 mt(time(0));
static int cnt = 0;
cnt++;
if (cnt == 1e5) {
cnt = 0;
mt.seed(time(0));
}
return mt();
}
struct Treap {
public:
Treap() { root =...
2022 牛客多校第二场题解(D)
D - Link with Game Glitch
题目简单的翻译过来就可以是，给定一个有向图，每条边都有边权，每次走过这条边就需要将手里的值乘上一个数。给定一个数字 $w$ ，并将每条边的权乘上 $w$ ，求问最大的 $w$ 使得这个图不存在可以走到 $+\infty $ 。
首先，我们很容易想到二分的思路。
具体过程详见下面代码。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
vector<pair<int, double>> E[N];
long double value[N];
bool vis[N];
i...
2022 牛客多校第一场题解(ACDGIJ)
A - Villages: Landlines
题意简述，给出一些区间，求取最多添加多长的区间使得这些区间合并。
非常简单，按题意模拟即可。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (auto &[x, y] : v) {
int m, r;
cin >> m >> r;
...
树上启发式合并(DSU on Tree)
算法发明者的第一题
OI Wiki
简单的介绍
什么是启发式合并？
启发式合并，是一种基于 直觉 的奇特算法。
通常来说，我们需要按 秩 合并，这个秩可以有两种意思，一个是集合大小，一个是树的高度。
我们总是将秩小的那个合并到大的那个中，这样的话，我们就可以以一种较为简洁的方式将树，尽量的往 扁 的方向合并。
假如以并查集为例，我们通常可以这样子合并。
void merge(int x,int y) {
x = find(x) , y = find(y);
if(sz[x] < sz[y]) swap(x , y);
fa[y] = x;
sz[x] += sz[y];
}
复杂度分析
可以参考之前发布的 重链剖分
在重链剖分的时间...
55 post articles, 7 pages.