题目要求出一个含有 个节点的有序二叉树的叶子节点的期望个数,
,要求精确到
例如一个含有 3 个节点的二叉树,一共有 5 种情况,期望的叶子节点个数是
给定一个长度为 的数组
,问有多少对
满足
且
也就是统计有多少对长度为 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI)
例如 3 5 3 6 3 4 10 4 5 2,就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对
计算多项式的乘法,或者计算两个大整数的乘法是在计算机中很常见的运算,如果用普通的方法进行,复杂度将会是 的,还有一种分治乘法,需要新东西吗?play daisy slots 测试您的数学能力。 可以做到
时间计算(可以看这里)。下面从计算多项式的乘法出发,介绍快速傅里叶变换(Fast Fourier Transform, FFT)如何在
的时间内计算出两个多项式的乘积。另外,存在只需要两次快速傅立叶变换就可以计算大整数乘法的方法,具体见实序列离散傅里叶变换的快速算法
这里介绍一些后面可能会用到的知识(主要是关于多项式、卷积以及复数的),如果你已经知道觉得它太水了或者想用到的时候再看就跳过吧
简单来说,形如 的代数表达式叫做多项式,可以记作
,
叫做多项式的系数,
是一个不定元,不表示任何值,不定元在多项式中最大项的次数称作多项式的次数
像刚刚我们提到的那些多项式,都是以系数形式表示的,也就是将 次多项式
的系数
看作
维向量
,其系数表示(coefficient representation)就是向量
如果选取 个不同的数
对多项式进行求值,得到
,那么就称
为多项式
的点值表示(point-value representation)
多项式 的点值表示不止一种,你只要选取不同的数就可以得到不同的点值表示,但是任何一种点值表示都能唯一确定一个多项式,为了从点值表示转换成系数表示,可以直接通过插值的方法
后面提到的 ,除非作为
求和的变量,其余的都表示虚数单位
次单位根是指能够满足方程
的复数,这些复数一共有
个它们都分布在复平面的单位圆上,并且构成一个正
边形,它们把单位圆等分成
个部分
根据复数乘法相当于模长相乘,幅角相加就可以知道, 次单位根的模长一定是
,幅角的
倍是
这样, 次单位根也就是
再根据欧拉公式
就可以知道 次单位根的算术表示
如果记 ,那么
次单位根就是
给定两个多项式
将这两个多项式相乘得到 ,在这里
如果一个个去算 的话,要花费
的时间才可以完成,但是,这是在系数表示下计算的,如果转换成点值表示,知道了
的点值表示后,由于只有
个点,就可以直接将其相乘,在
的时间内得到
的点值表示
如果能够找到一种有效的方法帮助我们在多项式的点值表示和系数表示之间转换,我们就可以快速地计算多项式的乘法了,快速傅里叶变换就可以做到这一点
题目给定一个有 个节点,
条边的有向图,以及
个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,
看了这篇题解才会做的QAQ
题目核心思想是分治以及缩小图的规模,有两个操作
Contraction:删除必须边
把待修改的边标记成 ,然后跑一次最小生成树,显然这时候出现在生成树中非
的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边
Reduction:删除无用边
把待修改的边标记成 ,然后跑一次最小生成树,没出现在生成树中的非
边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,
边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治
然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)
Problem 1:无修改、无插入区间第K小问题
关于这题,可以直接用主席树(函数式线段树)来解决
假设现在有无限的内存和时间,可以对每个前缀构造一棵权值线段树,然后每次询问区间 [l, r] 就找出前缀 [0, l - 1] 和 [0, r] 的线段树,相减就可以得到所需要的权值线段树,然后在这上面根据子树大小跑就可以了
由于空间有限,最开始不初始化整棵树,而是动态的添加节点,并且在插入的时候只有经过的那一条链上的东西会被更改,所以对于一些没有修改的子树,直接用指针指向上一次的版本,因为每一次插入最多经过 个节点,这样总共空间不会超过
,同样,时间复杂度也是每次
参考问题:BZOJ-2588: Spoj 10628. Count on a tree
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
#include <cstdio> #include <algorithm> const int MaxN = 100010, MaxL = 17, MaxV = ~0u >> 1; int n, m, total; int head[MaxN], next[MaxN << 1], point[MaxN << 1], weight[MaxN]; int que[MaxN], fa[MaxN], depth[MaxN], dist[MaxL][MaxN]; template<typename Type> class memory_pool { Type* data[1 << 16]; int used, remain; public: memory_pool() : used(0), remain(1 << 16) {} ~memory_pool() { for(int i = 0; i != used; ++i) delete[] data[i]; } Type* fetch() { if(remain + 1 < 1 << 16) return data[used - 1] + ++remain; data[used++] = new Type[1 << 16]; return data[used - 1] + (remain = 0); } }; struct node_t { int w; node_t *l, *r; }; node_t *nil, *root[MaxN], *tmp[4]; memory_pool<node_t> mem; void add_edge(int u, int v) { point[++total] = v; next[total] = head[u]; head[u] = total; } node_t* modify(node_t* now, unsigned head, unsigned tail, unsigned pos) { node_t* n = mem.fetch(); *n = *now; ++n->w; if(head == tail) return n; unsigned m = (head + tail) >> 1; if(pos <= m) n->l = modify(n->l, head, m, pos); else n->r = modify(n->r, m + 1, tail, pos); return n; } void solve_father() { int qhead = 0, qtail = 0; que[qtail++] = 1; depth[1] = 1, fa[1] = 0; root[0] = nil; while(qhead != qtail) { int u = que[qhead++]; root[u] = modify(root[fa[u]], 0, MaxV, weight[u]); for(int k = head[u]; k; k = next[k]) { int v = point[k]; if(v == fa[u]) continue; fa[v] = u; depth[v] = depth[u] + 1; que[qtail++] = v; } } } void init_lca() { for(int i = 1; i <= n; ++i) dist[0][i] = fa[i]; for(int l = 1; l != MaxL; ++l) for(int i = 1; i <= n; ++i) dist[l][i] = dist[l - 1][dist[l - 1][i]]; } int get_lca(int u, int v) { if(depth[u] > depth[v]) std::swap(u, v); int diff = depth[v] - depth[u]; for(int i = 0; diff; diff >>= 1, ++i) if(diff & 1) v = dist[i][v]; if(u == v) return u; for(int p = MaxL - 1; u != v; p ? --p : 0) { if(dist[p][u] != dist[p][v] || p == 0) { v = dist[p][v]; u = dist[p][u]; } } return u; } int ask(unsigned head, unsigned tail, int k) { if(head == tail) return head; unsigned m = (head + tail) >> 1; int num = tmp[0]->l->w + tmp[1]->l->w - tmp[2]->l->w - tmp[3]->l->w; if(k <= num) { for(int i = 0; i != 4; ++i) tmp[i] = tmp[i]->l; return ask(head, m, k); } else { for(int i = 0; i != 4; ++i) tmp[i] = tmp[i]->r; return ask(m + 1, tail, k - num); } } int main() { std::scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) std::scanf("%d", weight + i); for(int i = 1; i != n; ++i) { int u, v; std::scanf("%d %d", &u, &v); add_edge(u, v); add_edge(v, u); } nil = mem.fetch(); nil->l = nil->r = nil, nil->w = 0; solve_father(); init_lca(); int lastans = 0; for(int i = 0; i != m; ++i) { int x, y, k, lca; std::scanf("%d %d %d", &x, &y, &k); x ^= lastans; lca = get_lca(x, y); tmp[0] = root[x], tmp[1] = root[y]; tmp[2] = root[lca], tmp[3] = root[fa[lca]]; lastans = ask(0, MaxV, k); std::printf("%d", lastans); if(i + 1 != m) std::puts(""); } return 0; } |
Problem 2:带修改、无插入区间第K小问题
现在需要修改权值,如果暴力修改每棵线段树的话,最多会要修改 级别的东西,复杂度也会退化
这时候想想,我们需要的操作是修改一个区间的线段树和询问一个区间的线段树的信息,也就是区间修改和区间查询,很容易会想到树状数组!它能够把每个区间用 个区间来表示出来
所以只要在每个树状数组的节点建立可以权值线段树,表示这个区间的权值信息就可以完成所需要的操作了,时间和空间复杂度都是
参考问题:BZOJ-1901: Zju2112 Dynamic Rankings
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include <cstdio> #include <cstring> #include <algorithm> template<typename Type> class memory_pool { Type* data[1 << 16]; int used, remain; public: memory_pool() : used(0), remain(1 << 16) {} ~memory_pool() { for(int i = 0; i != used; ++i) delete[] data[i]; } Type* fetch() { if(remain != 1 << 16) return data[used - 1] + ++remain; data[used++] = new Type[1 << 16]; return data[used - 1] + (remain = 0); } }; struct node_t { int w; node_t *l, *r; }; const int MaxN = 20001; memory_pool<node_t> mem; int size, data[MaxN], map[MaxN], oper[MaxN][4]; node_t *left[MaxN], *right[MaxN], *root[MaxN], *nil; node_t* update(node_t* n, int head, int tail, int pos, int val) { if(n == nil) { n = mem.fetch(); n->l = n->r = nil; n->w = val; } else n->w += val; if(head == tail) return n; int m = (head + tail) >> 1; if(pos <= m) n->l = update(n->l, head, m, pos, val); else n->r = update(n->r, m + 1, tail, pos, val); return n; } void modify(int n, int x, int pos, int val) { for(; x <= n; x += x & -x) root[x] = update(root[x], 1, size, pos, val); } int ask(int lc, int rc, int head, int tail, int k) { if(head == tail) return head; int l = 0, r = 0; for(int i = 0; i != lc; ++i) l += left[i]->l->w; for(int i = 0; i != rc; ++i) r += right[i]->l->w; int m = (head + tail) >> 1; if(k <= r - l) { for(int i = 0; i != lc; ++i) left[i] = left[i]->l; for(int i = 0; i != rc; ++i) right[i] = right[i]->l; return ask(lc, rc, head, m, k); } else { for(int i = 0; i != lc; ++i) left[i] = left[i]->r; for(int i = 0; i != rc; ++i) right[i] = right[i]->r; return ask(lc, rc, m + 1, tail, k - (r - l)); } } int get_ans(int l, int r, int k) { int lc = 0, rc = 0; for(--l; l; l -= l & -l) left[lc++] = root[l]; for(; r; r -= r & -r) right[rc++] = root[r]; return data[ask(lc, rc, 1, size, k)]; } int main() { nil = mem.fetch(); nil->l = nil->r = nil, nil->w = 0; int n, m, tot = 0; std::scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) std::scanf("%d", data + i); tot = n; for(int i = 0; i != m; ++i) { char op[2]; std::scanf("%s", op); if(op[0] == 'C') { oper[i][0] = 1; std::scanf("%d %d", oper[i] + 1, oper[i] + 2); data[++tot] = oper[i][2]; } else { oper[i][0] = 0; std::scanf("%d %d %d", oper[i] + 1, oper[i] + 2, oper[i] + 3); } } std::memcpy(map, data, sizeof(data)); std::sort(data + 1, data + tot + 1); size = std::unique(data + 1, data + tot + 1) - data - 1; for(int i = 1; i <= tot; ++i) map[i] = std::lower_bound(data + 1, data + size + 1, map[i]) - data; for(int i = 1; i <= n; ++i) root[i] = nil; for(int i = 1; i <= n; ++i) modify(n, i, map[i], 1); for(int i = 0; i != m; ++i) { if(oper[i][0]) { int pos = std::lower_bound(data + 1, data + size + 1, oper[i][2]) - data; int p = oper[i][1]; modify(n, p, map[p], -1); modify(n, p, map[p] = pos, 1); } else { std::printf("%d\n", get_ans(oper[i][1], oper[i][2], oper[i][3])); } } return 0; } |
Problem 3:带修改、带插入区间第K小问题
现在我们需要支持可以在某个位置插入一个值,比如原先的序列是 1 2 3,然后在第二个位置插入 4 的话,序列就会变成 1 4 2 3
因为树状数组不支持插入元素,但是类似 Problem 2 的思想,你或许会想到使用平衡树,它也在 的时间内支持区间修改、查询,而且还支持插入元素
也就是平衡树上的节点就表示整棵子树中信息的权值线段树,但是仔细想就会发现,平衡树基本都是需要旋转来维持平衡的,这样一转,对权值线段树修改的时间复杂度就会迅速增大!
替罪羊树(Scapegoat Tree)是一种很神奇的平衡树,它不需要旋转来保持平衡,而是有一个平衡因子 每次插入如果发现某棵子树太不平衡,就把整棵子树暴力重构成完全二叉树
具体来说也就是如果某棵子树满足 ,就认为是不平衡的,然后就重构它
当 的时候,这棵树就是完全二叉树,当
的时候就永远不会重构,很显然,
越小,询问的效率越高,
越大,插入的效率越高
可以证明,替罪羊树的查询效率是 ,而插入均摊
这样,这个问题只需要用替罪羊树再套上权值线段树就可以解决了
但是有一个问题就是你需要动态分配内存,并且在重构的时候要及时释放无用内存。并且在写权值线段树的时候不要写成函数式线段树那样,否则内存会爆(我就不小心写成这样被坑了好久)
参考问题:BZOJ-3065: 带插入区间K小值
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 |
#include <cstdio> #include <algorithm> const int MaxN = 70010, MaxV = 70000; struct seg_t { int w; seg_t *l, *r; }; seg_t *seg_nil; void destroy(seg_t* now) { if(now == seg_nil) return; destroy(now->l); destroy(now->r); delete now; } seg_t* insert(seg_t* n, int l, int r, int pos, int v) { if(n->w + v == 0) { if(n != seg_nil) destroy(n); return seg_nil; } if(n == seg_nil) { n = new seg_t; n->l = n->r = seg_nil; n->w = v; } else n->w += v; if(l == r) return n; int m = (l + r) >> 1; if(pos <= m) n->l = insert(n->l, l, m, pos, v); else n->r = insert(n->r, m + 1, r, pos, v); return n; } struct scap_t { int size, val; scap_t *l, *r; seg_t *seg; }; scap_t *scap_nil, *root, *rebuild_node, *rebuild_fa; double alpha; int record_num, seg_num; int value[MaxN], record[MaxN]; seg_t* seg_record[MaxN]; void destroy(scap_t* now) { if(now == scap_nil) return; destroy(now->seg); destroy(now->l); record[++record_num] = now->val; destroy(now->r); delete now; } scap_t* scap_build(int l, int r) { if(l > r) return scap_nil; scap_t* n = new scap_t; if(l == r) { n->size = 1; n->val = record[l]; n->l = n->r = scap_nil; n->seg = insert(seg_nil, 0, MaxV, record[l], 1); return n; } int m = (l + r) >> 1; n->val = record[m]; n->l = scap_build(l, m - 1); n->r = scap_build(m + 1, r); n->size = n->l->size + n->r->size + 1; n->seg = seg_nil; for(int i = l; i <= r; ++i) n->seg = insert(n->seg, 0, MaxV, record[i], 1); return n; } scap_t* scap_rebuild(scap_t* now) { record_num = 0; destroy(now); return scap_build(1, record_num); } int scap_modify(scap_t* now, int pos, int v) { int old_val = 0; int sz = now->l->size; if(sz + 1 == pos) { old_val = now->val; now->val = v; } else if(pos <= sz) { old_val = scap_modify(now->l, pos, v); } else { old_val = scap_modify(now->r, pos - sz - 1, v); } now->seg = insert(now->seg, 0, MaxV, old_val, -1); now->seg = insert(now->seg, 0, MaxV, v, 1); return old_val; } scap_t* scap_insert(scap_t* now, int pos, int v) { if(now == scap_nil) { scap_t *n = new scap_t; n->val = v, n->size = 1; n->l = n->r = scap_nil; n->seg = insert(seg_nil, 0, MaxV, v, 1); return n; } now->seg = insert(now->seg, 0, MaxV, v, 1); int sz = now->l->size; if(pos <= sz) now->l = scap_insert(now->l, pos, v); else now->r = scap_insert(now->r, pos - sz - 1, v); now->size = now->l->size + now->r->size + 1; if(now->size * alpha < std::max(now->l->size, now->r->size)) rebuild_node = now; if(now->l == rebuild_node || now->r == rebuild_node) rebuild_fa = now; return now; } void scap_query(scap_t* now, int l, int r) { if(l > r) return; int lsz = now->l->size + 1, sz = now->size; if(l == 1 && r == sz) { seg_record[seg_num++] = now->seg; return; } if(l <= lsz && r >= lsz) record[record_num++] = now->val; if(r < lsz) { scap_query(now->l, l, r); } else if(l > lsz) { scap_query(now->r, l - lsz, r - lsz); } else { scap_query(now->l, l, lsz - 1); scap_query(now->r, 1, r - lsz); } } int find_kth(int l, int r, int k) { seg_num = record_num = 0; scap_query(root, l, r); int low = 0, high = MaxV; while(low < high) { int mid = (low + high) >> 1, sum = 0; for(int i = 0; i != seg_num; ++i) sum += seg_record[i]->l->w; for(int i = 0; i != record_num; ++i) sum += record[i] >= low && record[i] <= mid; if(k <= sum) { high = mid; for(int i = 0; i != seg_num; ++i) seg_record[i] = seg_record[i]->l; } else { for(int i = 0; i != seg_num; ++i) seg_record[i] = seg_record[i]->r; k -= sum; low = mid + 1; } } return low; } void init() { static seg_t seg_nil_base; seg_nil = &seg_nil_base; seg_nil->w = 0; seg_nil->l = seg_nil->r = seg_nil; static scap_t scap_nil_base; scap_nil = &scap_nil_base; scap_nil->l = scap_nil->r = scap_nil; scap_nil->seg = seg_nil; scap_nil->size = 0; alpha = 0.8; } int main() { int n; std::scanf("%d", &n); for(int i = 1; i <= n; ++i) std::scanf("%d", record + i); init(); root = scap_build(1, n); int m, lastans = 0; std::scanf("%d", &m); for(int i = 0; i != m; ++i) { char op[2]; std::scanf("%s", op); if(*op == 'Q') { int x, y, k; std::scanf("%d %d %d", &x, &y, &k); x ^= lastans, y ^= lastans, k ^= lastans; std::printf("%d\n", lastans = find_kth(x, y, k)); } else { int x, val; std::scanf("%d %d", &x, &val); x ^= lastans, val ^= lastans; if(*op == 'M') { scap_modify(root, x, val); } else { rebuild_fa = 0; rebuild_node = 0; root = scap_insert(root, x - 1, val); if(rebuild_node) { if(rebuild_node == root) root = scap_rebuild(root); else if(rebuild_fa->l == rebuild_node) rebuild_fa->l = scap_rebuild(rebuild_node); else rebuild_fa->r = scap_rebuild(rebuild_node); } } } } destroy(root); return 0; } |