寂静的角落 星空在前,路在脚下
2021-04-15 杂谈
发布于: 2021-04-15 更新于: 2021-04-15 分类于: 杂谈

今天风沙真大。

阅读更多
2021-04-11模拟赛
发布于: 2021-04-11 更新于: 2021-04-11 分类于: 模拟赛

又莫名其妙 $\color{Yellow}CE$ 了

$\color{Yellow}CE$ 太难受了。

题目 & 简易介绍

<...
阅读更多
2021-04-10 杂谈
发布于: 2021-04-10 更新于: 2021-04-10 分类于: 杂谈

今天 $UNOI$ 开始了。

今天突然知道菲利普亲王去世了,经历过二战的人还活着的不多了

阅读更多
标记永久化线段树
发布于: 2021-04-07 更新于: 2021-04-07 分类于: 数据结构

$\color{Green}code - oi$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
using namespace std;
typedef long long ll;
inline int ls(int f) { return f << 1; }
inline int rs(int f) { return f << 1 | 1; }
inline int mid(int l, int r) { return (l + r) >> 1; }
const int maxn = 1e5 + 5;
ll a[maxn];
struct node {
ll v;
ll add;
node() : add(0) {}
} st[maxn << 2];
inline void push_up(int p) { st[p].v = st[ls(p)].v + st[rs(p)].v; }
void build(int p, int l, int r) {
if (l == r)
st[p].v = a[l];
else {
int m = mid(l, r);
build(ls(p), l, m);
build(rs(p), m + 1, r);
push_up(p);
}
}

void plus(int p, int nl, int nr, int cl, int cr, ll k) {
if (nr < cl || cr < nl) return;
if (cl <= nl && nr <= cr) {
st[p].v = st[p].v + k * (nr - nl + 1);
st[p].add = st[p].add + k;
return;
}
st[p].v += k * (min(nr, cr) - max(nl, cl) + 1);
int m = mid(nl, nr);
plus(ls(p), nl, m, cl, cr, k);
plus(rs(p), m + 1, nr, cl, cr, k);
}
ll query(int p, int nl, int nr, int ql, int qr, ll tag) {
if (nr < ql || qr < nl) return 0;
if (ql <= nl && nr <= qr) return st[p].v + tag * (nr - nl + 1);
int m = mid(nl, nr);
return query(ls(p), nl, m, ql, qr, tag + st[p].add) +
query(rs(p), m + 1, nr, ql, qr, tag + st[p].add);
}
阅读更多
线段树 Segment Tree
发布于: 2021-04-06 更新于: 2021-04-07 分类于: 数据结构

$\color{Green}code - oi$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
typedef long long ll;
inline int ls(int f) {return f << 1;}
inline int rs(int f) {return f << 1 | 1;}
inline int mid(int l, int r) {return (l + r) >> 1;}
const int maxn = 1e5 + 5;
ll a[maxn];
struct node {
ll v;
ll add;
node() : add(0){}
} st[maxn << 2];
inline void push_up(int p) {st[p].v = st[ls(p)].v + st[rs(p)].v;}
void build(int p, int l, int r) {
if(l == r)
st[p].v = a[l];
else {
int m = mid(l, r);
build(ls(p), l, m);
build(rs(p), m + 1, r);
push_up(p);
}
}
inline void push_down(int p, int l, int r) {
int m = mid(l ,r);
st[ls(p)].v += st[p].add * (m - l + 1);
st[rs(p)].v += st[p].add * (r - m);
st[ls(p)].add += st[p].add;
st[rs(p)].add += st[p].add;
st[p].add = 0;
}

void plus(int p, int nl, int nr, int cl, int cr, ll k) {
if (nr < cl || cr < nl) return;
if (cl <= nl && nr <= cr) {
st[p].v += k * (nr - nl + 1);
st[p].add += k;
return ;
}
push_down(p, nl, nr);
int m = mid(nl, nr);
plus(ls(p), nl, m, cl, cr, k);
plus(rs(p), m + 1, nr, cl, cr, k);
push_up(p);
}
ll query(int p, int nl, int nr, int ql, int qr) {
if (nr < ql || qr < nl) return 0;
if (ql <= nl && nr <= qr) return st[p].v;
push_down(p, nl, nr);
int m = mid(nl, nr);
return query(ls(p), nl, m, ql, qr) + query(rs(p), m + 1, nr, ql, qr);
}
阅读更多
计划
发布于: 2021-04-05 更新于: 2021-04-06 分类于: 计划

数据结构

线段树

标记永久化

权值线...

阅读更多
NOI大纲
发布于: 2021-04-04 更新于: 2021-04-05 分类于: 资料
稀疏表 Sparse Table, ST
发布于: 2021-04-04 更新于: 2021-04-07 分类于: 数据结构

$\color{Green}code - oi$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int logn = 21, maxn = 2e6+5;
int f[maxn][logn + 1], lg[maxn + 1];
template <typename T = int>
inline T iread(void) {
T n = 0;
register char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) n = (n << 3) + (n << 1) + (ch ^ 48), ch = getchar();
return n;
}
inline void makelog(void) {
lg[1] = 0;
lg[2] = 1;
for (register int i = 3; i < maxn; ++i) lg[i] = lg[i >> 1] + 1;
}
int n, m, l, r, s;
int main() {
n = iread(), m = iread();
makelog();
for (register int i = 1; i <= n ; ++i) f[i][0] = iread();
for (register int j = 1; j <= logn; j++)
for (register int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
for (register int i = 1; i <= m; ++i) {
l = iread(), r = iread();
s = lg[r - l + 1];
printf("%d\n", max(f[l][s], f[r - (1 << s) + 1][s]));
}
return 0;
}
阅读更多
预处理二进制对数表
发布于: 2021-04-04 更新于: 2021-04-06 分类于: 技巧

预处理 $lb$ 表。

$\color{Green}code$

1
2
3
4
5
template <typename T>
inline void mklb(T n, T *lb_table) {
lb_table[1] = 0, lb_table[2] = 1;
for (T i = 3; i <= n; ++i) lb_table[i] = lb_table[i >> 1] + 1;
}
阅读更多
卢卡斯定理 Lucas' theorem
发布于: 2021-04-04 更新于: 2021-04-05 分类于: 算法

内容

对于质数 $p$ ,有:

$$\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p$$

(占位行,不然 Hexo 渲染下面会 Bug)

(占位行)

(占位行)

(占位行)

...
阅读更多