Public Transport System

题意

给定一个有向图, 每条边有边权$a_e$$b_e$, $0<a_e,b_e;\;b_e<a_e$. 记一条路径由$k$条边$e_1,e_2,...,e_k$组成, 那么这条路径中, 边$e_1$的权值为$a_{e_1}$, $e_i(i>1)$的权值为:

$$\begin{cases} a_{e_i}&a_{e_i}\leq a_{e_{i-1}},\\ a_{e_{i}}-b_{e_i}&a_{e_i}>a_{e_{i-1}}. \end{cases} $$

这条路径的权值是这条路径上边的权值之和. 求从点$1$出发到所有点的最短路长度.

$$\begin{align*} n\leq 1\times10^5,\ m\leq 2\times10^5. \end{align*} $$

Read More

Charged Tree

题意: 给定一棵有根带权树. 有两种操作下移和上移. 下移, 即每个节点将自己的权值均分给各个儿子, 假设叶子结点有一个无限长的儿子链, 即叶子结点每次下移都会把自己和整条儿子链下移一位. 每个节点的新值就是它从父亲得到的那个值 (他自己原来的值已经分给了儿子) , 特别地, 一次下移操作后根变成0. 上移, 即对每个节点, 将所有儿子的权值加起来赋给自己.

Read More

tarjan算法 (求最近公共祖先)

本文讲解用于求解最近公共祖先 (Least Common Ancestor, LCA) 的tarjan算法.

首先看最近公共祖先问题. 对一棵给定的有根树, 为了得知两点之间最短的路径, 显然应当先从一点运动到它们的最近公共祖先, 再直接运动到另一点. 如果每条边只能经过一次, 那么这就是唯一的路径. 这时就需要确定这两点的最近公共祖先. 对小规模的数据可以使用暴力算法, 比如对一个点的所有祖先进行dfs, 找到最近的、能到达另一点的那个祖先. 但是这个算法本身效率就很低下, 更不用提大规模数据的情形.

解决这一类问题有多种算法, 可分为在线算法和离线算法两种. “在线” 和 “离线” 是针对大规模数据的说法, 在线算法是指对每个询问 (即节点对) 即时处理的算法, 离线算法是指将所有询问存储起来以后统一处理的算法. 在线和离线会造成复杂度的很大差异, 通常来讲离线算法应当更快一些, 因为离线情形掌握了更多的信息. 这里要讲的tarjan算法是一种离线算法, 复杂度为$O(n+p)$, 其中$n$为树的节点数, $p$为询问数.

考虑优化上述的dfs. 上述的dfs显然有许多浪费, 因为上述过程中的所有节点只需要一次dfs就可以遍历完, 而上述过程中dfs的次数却与深度成正比, 这显然是没有很好地利用dfs的信息. 仔细考虑dfs的过程, 发现遍历在最近祖先处是一棵一棵子树进行的, 也就是先遍历了含有节点1的子树, 再遍历含有节点2的子树 (假设1比2先遍历到) , 我们需要找到这两棵子树 “分叉” 的地方, 而不考虑分叉处上面的情形. 那么可以考虑这样做: 针对当前的状态v, 为遍历过的每个节点u打上一个标记, 记录u和v从哪里开始 “分叉” . 如果这一操作可以在遍历到u时就做到, 那么问题就解决了. 显然初始值 (刚遍历到u时的标记) 是这个节点直接的父亲. 当遍历完他父亲的所有子树后仍没有找到节点2时, 应当返回它父亲的父亲继续搜索, 那么该节点的标记也都应当变成他的父亲的父亲. 这看起来需要再进行一次dfs从而效率和刚才一样低, 但是可以用并查集解决这一问题. 现在的过程变成, 遍历到某一结点时, 将他和他父亲合并 (在并查集中成为父亲的子树) ; 当他父亲遍历完所有子树之后, 将他父亲和他父亲的父亲合并…为了知道某个节点的标记 (分叉处) , 只需要查找该节点在并查集中的根节点.

PWTC day4补题记录

F

题意: 求树链mex, $n,q\leq 100,000$.

树上莫队. 考虑一个棋子在树上从根开始dfs的过程, 棋子每移动一次都停下来记录一次时间, 注意返回父亲时也要停下. 这样, 每两个时刻之间就由一个边连接. 把 (节点, 时刻) 对按时刻排序, 每次询问$(u,v)$即为询问来到$u$的时刻$t_u$$v$的时刻$t_v$之间的序列的一个量: 这个序列中出现过两次的边都不计入, 只计入出现过一次的边, 求mex. 这样就恰好只计入了$u$$v$的链上的所有边. 然后是维护mex. 这个题每次修改都带上$\log$就是$O(n\sqrt{n}\log n)$会T, 所以要线性修改. 由于询问mex只有$q$次, 所以可以容忍$O(\sqrt{n})$的询问. 于是对边权分块, 即用$cnt[i]$记录$i$的出现次数的同时, 用$cnt\_bl[i]$记录$[i * bl, (i + 1) * bl - 1]$中数的个数. 找到第一个数的个数没有填满的块, 再遍历该块找到第一个缺席的数, 即为mex.

AC代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef pair<int, int> pii;
vector<pii> G[maxn];
struct query {
int first, second, id;
};
struct edge {
int w, id;
};
vector<query> qs;
vector<pii> ans;
int n, q, len, t, tt, bl;
int el[maxn], er[maxn];
edge L[2 * maxn], R[2 * maxn];
bool vis[maxn];
int cnt[maxn], cnt_block[maxn];
void dfs(int u, int fa, int id, int ww) {
el[u] = ++t;
for (auto e : G[u]) {
int v = e.first, w = e.second;
if (v == fa) continue;
R[t] = edge{w, ++tt};
L[t + 1] = edge{w, tt};
dfs(v, u, tt, w);
}
R[t] = edge{ww, id};
er[u] = ++t;
L[t] = edge{ww, id};
}
void add(int a) {
cnt[a]++;
if (cnt[a] == 1) cnt_block[a / bl]++;
}
void del(int a) {
cnt[a]--;
if (cnt[a] == 0) cnt_block[a / bl]--;
}
// ql + n^2/l min, q - n^2/l^2=0, l = n / sqrt(q)
inline bool cmp(const query& a, const query& b) {
if (a.first / len != b.first / len) return a.first / len < b.first / len;
return a.second < b.second;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
len = 2 * n / sqrt(q);
bl = sqrt(maxn);
int u, v, w;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
w = min(w, n);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
vis[i] = false;
}
dfs(1, 0, 0, 100005);
for (int i = 1; i <= q; i++) {
cin >> u >> v;
int a = el[u], b = el[v];
if (a > b) {int tmp = a; a = b; b = tmp;}
qs.push_back(query{a, b, i});
}
// 分块
sort(qs.begin(), qs.end(), cmp);
// 莫队
int l = 1, r = 1;
for (auto p : qs) {
int &ql = p.first, &qr = p.second;
while (l > ql) { // 先尽量延长
if (!vis[L[l].id]) {
add(L[l].w);
} else {
del(L[l].w);
}
vis[L[l].id] = !vis[L[l].id];
l--;
}
while (r < qr) { // 先尽量延长
if (!vis[R[r].id]) {
add(R[r].w);
} else {
del(R[r].w);
}
vis[R[r].id] = !vis[R[r].id];
r++;
}
while (l < ql) {
if (!vis[R[l].id]) {
add(R[l].w);
} else {
del(R[l].w);
}
vis[R[l].id] = !vis[R[l].id];
l++;
}
while (r > qr) {
if (!vis[L[r].id]) {
add(L[r].w);
} else {
del(L[r].w);
}
vis[L[r].id] = !vis[L[r].id];
r--;
}
int i, j;
for (i = 0; i <= 100000 / bl; i++) {
if (cnt_block[i] != bl) break;
}
for (j = i * bl; j < (i + 1) * bl; j++) {
if (cnt[j] == 0) break;
}
ans.push_back(pii(p.id, j));
}
sort(ans.begin(), ans.end());
for (auto p : ans) {
cout << p.second << '\n';
}
return 0;
}

FFT

FFT可以在$O(n\log n)$的时间内在多项式的点值表示法和系数表示法之间相互转换, 从而可以加速多项式乘法.

Read More

SB树

这棵二叉树中包含了所有的非负有理数. 首先看它的构造:

左侧有一个点$0/1$, 右侧有一个点$1/0$. 在中间创建一个点$0+1/1+0=1/1$, 这就是SB树的根.

接下来, $1/1$的左儿子是它和$0/1$的分子、分母分别相加: $1+0/1+1=1/2$. 右儿子是与$1/0$做这个操作: $1+1/1+0=2/1$. 接下来的节点, 其左儿子为: 该节点与左兄弟的分子分母分别相加. 特别地, 没有左兄弟时 (即它在左链上) 认为左兄弟为$0/1$. 右儿子为: 该节点与右兄弟的分子分母分别相加. 特别地, 没有右兄弟时 (即它在右链上) 认为右兄弟为$1/0$.

首先证明:

SB树中每个数都满足: 分子分母互质, 即每个非负有理数至多出现一次.

证: 我们来证明: 对每个节点, 考虑其加入时刻, 假如此时构造它使用了$m/n$$m'/n'$. 那么必有$m'n-mn'=1$.

首先这对根节点成立.

现在假设对$m+m'/n+n'$的构造时刻, $m/n$$m'/n'$$m'n-mn'=1$, 现在只要证明

  1. $(m+m')n-m(n+n')=1$
  2. $m'(n+n')-(m+m')n=1$

而这两个等式都与原等式相同. 于是对每个$m/n$存在$a,b$使$am+bn=1$, 从而$m,n$互质.

CF708D2

D题

题很好, 感觉思维得到了升华. 把整个题考虑成一个图, 对每对$\{i, j\}$, 只要tag[i] != tag[j]他们之间就要连边, 边权为$|2^i-2^j|$. 按照题意, 需要找一条边权不断上升的、$\sum|s_i-s_j|$最大的路. 由于边权不断上升, 可以将边按边权排序 (外层$i$从小到大, 内层$j$从大到小) , 然后使用动态规划: dp[i][t]维护只使用前$t$条边时, 终点为$i$的路的路径权值最大值. 考虑转移, 发现$t$增加$1$时只有至多两个dp值会发生变化, 因为一步只引入了一条边, 而且它只能被加在已经考虑过的路径的末尾. 这样, 我们可以舍弃$t$维度, 而代之以时间维度: $dp$数组只有一维, dp[i]维护当前时刻以$i$结尾的路的路径权值最大值. 每当时刻前进1, 就新考虑一条边, 更新一下dp[i]dp[j]: $dp_i = \max(dp_i, dp_j + |s_i - s_j|)$$dp_j=\max(dp_j, dp_i+|s_i-s_j|)$.

区间众数

通用求众数离线做法: 离散化之后, 开线段树维护数出现的频率的最大值, 带单点修改, 然后再用莫队, 移动区间时就跑一个单点修改, 复杂度是$O(n\sqrt{n}\log n)$.

当只需要找频数超过一半的区间众数的时候, 可以这样考虑: 众数频数如果超过区间长度的一半, 那么任意划分区间为两段, 它必然要么在左半边超过一半, 要么在右边超过一半. 然后就可以用线段树维护了. 具体来说, 每个结点维护当前区间的众数及其频数. 当合并时, 找左儿子和右儿子的众数. 如果众数频数超过一半, 那么众数一定是二者之一. 离散化后对每个数开一个pos数组维护出现位置, 在这个数组中二分得到这两者 (左右儿子的众数) 在当前区间中出现的频数, 取最大者即可. 这样维护出来不一定是真区间众数, 但是如果众数超过区间长度一半, 那他一定维护这个众数. 这个复杂度是每次查询$O(\log^2n)$的. 上面的论述中 “一半” 大概也可以改为其他比例, 这带来的问题是满足其他比例的众数可能有多个, 而这个比例超过一半时可以保证这样的众数唯一.

还有一种做法是随机化, 在待查询区间里找30个数作为候选众数, 对每个数检查它是否满足频数超过区间长度一半, 用上段的方法可以做到$O(\log n)$查询. 如果一个数频数超过区间长度一半, 那么在区间内任取30个数 (带放回) 找不到该众数的概率不超过$2^{-30}$. 这个做法完全可以扩展到其他比例, 比例变小时只需提高30这个常数, 例如要求众数频数超过$1/5$时可以取100个候选众数, 即可做到$({4\over 5})^{100}\approx2\times10^{-10}$概率. 这是选不到真众数的概率, 因为超过1/5的众数可能有多个, 似乎有点迷惑 (选不到假众数的概率也是一样的, 他们互不影响) . 但是没关系, 由于候选众数中几乎必有真众数, 即使找到了假众数, 还需要和真众数比频数, 所以这种算法几乎必然找到真众数.

CF716Div2 D AC代码:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define N 300000
using namespace std;
typedef pair<int, int> pii;
int n, m, maxn, a[N + 5];
struct node {
int l, r, mx, aa;
};
node xds[4 * N+5];
vector<int> pos[N+5];

int cnt(int x, int l, int r) {
int ret = upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
return ret;
}

void build(int id, int l, int r) {
if(l == r) {
xds[id].l = xds[id].r = l;
xds[id].mx = 1;
xds[id].aa = a[l];
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
xds[id].l = l; xds[id].r = r;
if (cnt(xds[id * 2].aa, l, r) > cnt(xds[id * 2 + 1].aa, l, r)) {
xds[id].mx = cnt(xds[id * 2].aa, l, r);
xds[id].aa= xds[id * 2].aa;
} else {
xds[id].mx = cnt(xds[id * 2 + 1].aa, l, r);
xds[id].aa= xds[id * 2 + 1].aa;
}
}

pii get(int id, int l, int r) {
// (frequency, value)
pii ret, ret2;
int f1 = 0, f2 = 0;
if (l <= xds[id].l && xds[id].r <= r) {
return pii(xds[id].mx, xds[id].aa);
}
int mid = (xds[id].l + xds[id].r) >> 1, rl = max(l, xds[id].l), rr = min(r, xds[id].r);
if (l <= mid) {
ret = get(id * 2, l, r);
f1 = cnt(ret.second, rl, rr);
}
if (r > mid) {
ret2 = get(id * 2 + 1, l, r);
f2 = cnt(ret2.second, rl, rr);
}
if (f1 > f2) {
return pii(f1, ret.second);
} else {
return pii(f2, ret2.second);
}
}

int main() {
int l, r;
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[a[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
pos[i].push_back(n + 1);
}
build(1, 1, n);
for (int i = 1; i <= m; i++) {
cin >> l >> r;
pii most = get(1, l, r);
cout << max(1, 2 * most.first - (r - l + 1)) << '\n';
}
return 0;
}