洛谷5355 [Ynoi2017]由乃的玉米田
Luogu 分析 考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。 那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu 分析 考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。 那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O...
Luogu 分析 把询问离线，从左往右加入每个数并维护以这个数为右端点时每个左端点的答案。 假设当前加入了 $x$，那么它显然不会更新 $a_x$ 上一次出现位置之前的左端点的答案（因为这些区间排序去重后根本没有变化），而且只会和 $[x-11,x+11]$ 的数产生贡献（因为只需要统计 $\leq 10$ 的长度）。而插入 $x$ 后极长值域连续段可能会有以下变化 从 $[a,x-1]$...
Luogu LOJ 分析 考虑从 $x$ 传递到 $y$ 的代价，显然有 这样子就可以 $\mathcal{O}(m2^m)$ 预处理 $g(x,S)$ 和求 $f_S$，总时间复杂度 $\mathcal{O}(m2^m)$。 然而存 $g$ 需要 736MB 空间，并开不下。 但是可以发现，我们只需要求 $x\in S$ 的 $g(x,S)$，所以我们只需要对每个 $x$ 求 $2^{m...
Luogu 分析 对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。 然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。 但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父...
Luogu LOJ 分析 考虑每个节点用一个数据结构维护子树中所有点的信息。 则我们需要支持插入、合并、全局加 $1$、求全局异或和四个操作。 可以用 01-Trie 来维护。前面两个操作是基本操作。 考虑全局加 $1$。如果是一个偶数，它的最低位会变为 $1$；否则它的最低位会变成 $0$，然后给次低位加上 $1$，仍然可以根据次低位讨论。放到 Trie 树上就是从低到高枚举每一位，交换当...
Luogu LOJ 分析 显然莫比乌斯反演一下，可以得到 直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。 另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel 代码 // ======================...
Luogu LOJ 分析 预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include...
Luogu LOJ 分析 后面显然是卷积的形式，直接 NTT 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/std...
Luogu LOJ 分析 先考虑 $l=1,r=|S|$ 的情况。 对 $S$ 和 $T$ 建 SAM。 设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出： 如果有对应的转移直接走过去，匹配长度加 $1$； 否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$； 如果跳...
Luogu [LOJ](https://loj.ac/problem/2133） 分析 如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。 考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $h...