文章

先分析下此题题意： 需要我们实现的操作： 单点修改序列元素 查询某个区间内 gcd 非 1 的子串数目 我们考虑用线段树维护区间内答案个数。 那么一个区间的所求数目即由 $\sf\large\text{三部分}$组成： 左区间内的数目 右区间内的数目 跨区间的数目 那么只要知道怎么求跨区间的就简单了 阅读更多…

笔记 做带末尾插入删除的区间信息维护）的数据结构题的方法： 分块 思路：每次插删操作暴力重构最后一块。 支持插删操作，支持在线 二进制分组 思路：若每次添加一个元素进数据结构里的复杂度比较高，则每次将这个元素单独放在最后一组，若最后一组与上一组的大小相同，就将这两组合并为同一组，不难发现最后得到的每 阅读更多…

二次离线莫队 问题 对于一些离线问题，往往需要用莫队解决。 但是在使用莫队的过程中，我们往往需要使用在线数据结构维护信息。但是一些复杂的信息往往需要带有 $O(\log n)$复杂度的数据结构才能维护，这使得整个算法的复杂度升高到了 $O(n^{1.5}\log n)$。 比如下面的问题： 离线询问 阅读更多…

关于同种音乐的限制，最后直接让答案除上 $m!$ 即可。 现在我们需要算出选出 $m$ 的片段的方案数，考虑 $\rm{DP}$ ，设 $dp_i$ 表示前 $i$ 个片段已经确定，且满足下列要求： 这 $i$ 个片段中没有空集 这 $i$ 个片段互不相同 这 $i$ 个片段中所有的音符的出现次数全 阅读更多…

我们考虑这样一个问题。 $$ans=\sum_{i=1}^nf(i)$$ 其中 $1\leq n\leq 10^{10}$ 其中 $f(i)$是一个非常奇怪的函数，并不像 $\mu(i),\varphi(i),i\varphi(i)$那样具有那么好的性质。但是满足以下条件： 1. 若 $p$为质数， 阅读更多…

题目分析 $\mu(m)=\sum_{m|d} F(d)$ $F(m)=\sum_{m|d} \mu(d) \mu(\frac{m}{d})$ $=\mu(m) \sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\mu(i)^2 [gcd(i,m)==1]$ $=\mu 阅读更多…

题目分析 建立出小根堆性质的笛卡尔树，于是每个节点可以代表一个矩形，其宽度为子树大小，高度为该节点记录的那一列高度-父节点那一列高度。 设 $f(x,i)$表示以 $x$为跟的子树中放了 $i$个棋子的方案数。 初始值：$f(0,0)=1$ 首先求出不在 $x$的矩形中放棋子的方案数：$f(x,i) 阅读更多…

我们先不考虑边的权值(< 与>)，这样子 $n-1$ 条边组成的就是树了，很显然是需要我们求出这棵树的合法拓扑序的个数，考虑使用 $\rm{DP}$ ，对于边的方向(即<,>) ，我们分类讨论即可。

首先的一个想法就是设 $f_u$ 表示点 $u$ 的子树的合法拓扑序的总数，但是这个时候如何计算呢 （更多…）

有趣的题目，可爱的传送门：戳这呢=￣ω￣= 刚开始往概率 $\rm{DP}$ 想了，发现对于一个点的概率是好算，但是如果求贡献的话就会很难办。最后万般无赖的点开了题解，发现居然是…… 组合数学？其实和 $\rm{DP}$ 没有半毛钱关系。 我们考虑一个节点 $i$ ，我们枚举 阅读更多…

此题可以 $\Large\text{线段树+优先队列}$解决。 首先看第一问，我们考虑开三个优先队列： $\sf {q1[i]}$，用于存储食物 $\sf i$的成熟时间 $\sf {q2[i]}$，用于存储成熟时间小于 $\sf i$的食物 对每个食物开一个 $\sf {e[i]}$，用于存储其成 阅读更多…