Zhu Junchao's Blog

STL 即标准模板库（Standard Template Library），是 C++ 标准库的一部分，里面包含了一些模板化的通用的数据结构和算法。由于其模板化的特点，它能够兼容自定义的数据类型，避免大量的造轮子工作。NOI 和 ICPC 赛事都支持 STL 库的使用，因此合理利用 STL 可以避免编写无用算法，并且充分利用编译器对模板库优化提高效率。 下面对STL的一些常用用法做简单介... Continue reading...

二维树状数组（单点修改 区间求和）1long long c[N][N];2int n, m;3int lowbit(int x){4 return x & -x;5}6void update(int x, int y, int w){7 for(int i = x; i <= n; i += lowbit(i)){8 ... Continue reading...

最近公共祖先倍增（略）离线Tarjan自己写的简略版1int ff[N];2int find2(int x){3 if(ff[x] != x) ff[x] = find2(ff[x]);4 return ff[x];5}6bool vis[N];7void tarjan(int x){8 ff[x] = x;9 vis[x] = 1;10... Continue reading...

哈希表1const int HASH_CNT = 2;2const int mod[HASH_CNT] = {(int)1e9 + 7, 998244353};3const int seed[HASH_CNT] = {27, 39};4typedef vector<int> vi;5struct swh{6 vector&l... Continue reading...

HDU5306 Gorgeous Sequence维护一个序列 $a$： 0 l r t $\forall l \le i \le r, a_i = min(a_i, t)$。 1 l r 输出区间 $[l, r]$ 中的最大值。 2 l r 输出区间 $[l, r]$ 和。 1#include <iostream>2#include <cstdio>3#def... Continue reading...

POJ2104 K-th Number$n$ 个数 $m$ 次询问区间 $[l,r]$​ 第 $k$ 小值 1#include <iostream>2#include <cstdio>3#include <algorithm>4using namespace std;5const int N = 1E5 + 7;6int sorted[N];7int t[... Continue reading...

Luogu-P4097 Segment要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。 1#include <iostream>2#include <cstdio>3#define ls (o << 1)... Continue reading...

普通莫队黑暗爆炸 - 2038 小Z的袜子(hose)查询区间中任意取两数相等的概率 1#include <iostream>2#include <cstdio>3#include <cmath>4#include <algorithm>5using namespace std;6const int N = 1E5 + 7;7int c[N],... Continue reading...

题目描述Bob has a tree with $n$ nodes, the set of the edges of this tree is $T$. Let $B$​ denote the edge set of n-clique, formally $B=\{(i,j)∣1≤i<j≤n\}$​​ Now give you an integer $k$, you need to... Continue reading...

题意给定一个含有 $n \times m \quad (nm \le 3 \cdot 10^5)$ 个格子的矩形，一开始每个格子被涂上了黑色或白色，现在可以选择将每个白色格子涂成蓝色或者红色（设白色格子的数目为 $w$ ， 显然共有 $2^w$ 种涂色的方法）。接下来在涂好色的矩形中放置大小为 $1 \times 2$ 大小的多米诺骨牌，放置的位置只能是同一行相邻的两个红色格子或者同一列相邻... Continue reading...