Cauphenuny's Blog

oi-wiki 给出 nnn 个点 Pi(xi,yi)P_i(x_i,y_i)Pi​(xi​,yi​)，将过这 nnn 个点的最多 n−1n-1n−1 次（为什么是 n−1n-1n−1 次：因为可以构造出 nnn 个线性方程，只能解出从常数项系数到 n−1n-1n−1 次项的系数）的多项式记为 f(x)f(x)f(x) ，求 f(k)f(k)f(k) 的值。 如图所示，将每一个点在 xxx 轴上的投影 (xi,yi)(x_i,y_i)(xi​,yi​) 记为 HiH_iHi​ 。对每一个 iii ，我们选择一个点集 {Pi}∪{Hj∣1≤i≤n,i≠j}\{P_i\}\cup\{H_j|1\le i\le n,i\neq j\}{Pi​}∪{Hj​∣1≤i≤n,i=j} ，作过这 nnn 个点的至多 n−1n-1n−1 次的线 gi(x)g_i(x)gi​(x) 。图中 f(x)f(x)f(x) 用黑线表示，gi(x)g_i(x)gi​(x) 用彩色线表示。 这样得到的 gi(x)g_i(x)gi​(x) 在各自对应的 xix_ixi​ 处取得 yiy_iyi​...

link 构造一颗中序遍历是序列的Treap，发现可以很容易地求出序列上第 xxx 位的值，即为 getval(root, x) ，但是不好求一个数 kkk 在序列上的位置。这时我们就可以维护一个值 idx(k)idx(k)idx(k) ，表示值为 kkk 的节点编号，这时只需要设计出一个函数来求节点 uuu 的排名了，而这个函数也很容易实现，对于一个节点 uuu ，每次将它向树根跳，如果它是右儿子，那么就将它父亲的左子树的值以及父亲的大小计入结果。 12345678910int getpos(int id) { int f, cnt = 0; while ((f = p[id].f) != 0) { if (id == p[f].rs) { cnt += p[p[f].ls].siz + 1; } id = f; } return cnt;} 既然要存储一个节点的父亲，那么 pushup...

转：link 题意:给你一颗树,每个点有一个权值,每条边可以留下或删除,问有多少种方案使得1所在的连通块中所有点的权值和恰好为 KKK. 暴力 n3n^3n3: 123456789101112131415int dfs(int u, int fa) { sum[u] = val[u]; dp[u][val[u]] = 1; for (int i = head[u]; i; i = edges[i].nex) { int v = edges[i].to; if (v == fa) continue; dfs(v, u); sum[u] += sum[v]; for (int j = min(sum[u], K); j >= val[u]; --j) { dp[u][j] = 1ll * dp[u][j] * (1 + dp[v][0]) % mod; for (int k = max(1, val[v]); k...

强连通定义：在有向图 G{V,E}G\{V,E\}G{V,E} 中，对于点集 V′∈VV'\in VV′∈V , 点集中的任意两点都可达，则称 V′V'V′ 为强连通。 考虑建出图的 dfs 树，则原图上的边可以转换为三种边： 坑： 要写两个连边函数，把第二个函数的 siz 写成了 tot ，调了我一个晚上… 123456789101112131415void addline(int u, int v) { tot++; l[tot].from = u; l[tot].to = v; l[tot].next = hl[u]; hl[u] = tot;}void addedge(int u, int v) { siz++; e[siz].from = u; e[siz].to = v; e[siz].next = he[u]; he[u] = siz; //就是这里！} 由于存边的时候只存了一个点的后继节点，所以要根据节点...

先看一个题目 CF161D Distance in Tree 考虑 dp（当然点分治也可以做），先求出 f(u,k)f(u,k)f(u,k) 表示将树中的 uuu 作为根节点后，深度为 kkk 的节点数量，则答案为 ∑u∈Gf(u,k)2\dfrac{\sum_{u\in G}f(u,k)}{2}2∑u∈G​f(u,k)​。 可以暴力求 fff 数组，复杂度 O(n2k)O(n^2k)O(n2k)。 优化一下，先以 111 为根节点，求出从每个点 uuu 开始，向下走 kkk 的路径条数 g(u,k)g(u,k)g(u,k) 设节点 uuu 的一个儿子是 vvv 。观察到如果求出了 f(u,k)f(u,k)f(u,k) 那么求 f(v,k)f(v,k)f(v,k) 可以利用一下信息。 红色部分显然是 g(v,k)g(v,k)g(v,k) ，蓝色部分是 f(u,k−1)f(u,k-1)f(u,k−1)，但是这样有一部分会多计算，就是那些以 uuu 为端点，长度为 k−1k-1k−1 ，经过了红色部分的路径。减去 g(v,k−2)g(v,k-2)g(v,k−2)...

link fhq 改几个函数就可以了 12345int refresh(int id) { tot++; p[tot] = p[id]; return tot;} 123456789101112131415void split_by_val(int rt, int &a, int &b, int val) { if (rt == 0) { a = b = 0; return; } if (p[rt].val <= val) { a = refresh(rt);// split_by_val(p[rt].rs, p[a].rs, b, val); pushup(a);//记得是pushup(a)，不是pushup(rt)！！！ } else { b = refresh(rt);// split_by_val(p[rt].ls, a,...

参考：blog1 | blog2 定义一下变量： 123456789struct Node { int ls;//每个点的左儿子 int rs;//每个点的右儿子 int val;//每个点的权值 int rnd;//每个点的随机权值 int siz;//以每个点为根的树的大小} tree[MAXN];int root;//根节点编号int tot;//节点总数 主要有两个核心操作：split(int rt, int &a, int &b, int k) 和 merge(int a, int b, int &rt) ，分别表示将一颗 treap(rt)\mathsf{treap(rt)}treap(rt) 按权值分裂成两颗 treap(a)\mathsf{treap(a)}treap(a) 和 treap(b)\mathsf{treap(b)}treap(b) 以及将两颗 treap\mathsf{treap}treap 合并。 基本操作 分裂 split(int rt, int...