关于现有两篇题解的补充说明。 首先计数转概率，设 $p_i$ 表示 $i$ 号盒子里有猫的概率。如果存在一条有向边 $i\to j$，容易推出，操作一下盒子 $i$ 的转移形如 $\begin{cases} p'_i\gets p_ip_j\\ p'_j\gets p_i+p_j-p_ip_j\end{cases}$。…

一个自认为简单不少的做法。 以下分别记 ${\rm low,eq,high}$ 为 $ x$ 的数。 首先，$f(a,x,l,r)$ 的限制等价为「$a_l,a_{l+1},\dotsc,a_r$ 中不能有 ${\rm low}$ 或 ${\rm high}$ 其一」。 记 $L_k$ 表示覆盖 $i$ 的区间中，左端…

在讨论《Hack 了一些题解》回复：

@[NameGod](luogu://user/599813) 我觉得撤题解意义不大，放在这里让大家知道有个 Hack 就够了吧。

``` 10 5 7 8 9 4 3 1 6 2 10 ``` 仅把 7 8 9 三个数放到 Y 中是合法的，但是有大概一半题解输出了 -1。

在讨论《呜呼哀哉！！》回复：

我感觉正解的复杂度应该是 $O(2^kn)$。虽然我多了一个 $k$。 注意本地的大样例的规模只有 1e3，所以如果你没跑到 0.1s 内其实是有点寄的。

在讨论《取消输入输出流还是有tle 用c风格的就可以》回复：

一楼在胡扯。 发帖前可以先多手搓几个样例，17 行的 `if (isprime.size() > num) break;` 没道理（

以下 $n=K,q=Q$。 闲话：[这里](https://codeforces.com/blog/entry/77471?#comment-625989)提到了一个 $O(n\log^2n+q\log n)$ 的做法，使用了 Tree Decomposition，我不会（ *** 在最外层补上一层括号，然后建出括号树…

在讨论《求刚才的CF Div.2 E3 思路》回复：

E3 同样考虑二进制，但是尝试缩减串长就好了。 提前预处理 $s_k$ 表示 regular 子串恰有 $2^k$ 个的字符串中最短的那个，可以构造得到。 然后用左括号作分隔符拼在一起即可。

在讨论《bitset 也能状压？》回复：

并没有空间优化。bitset 是用 `unsigned long[]` 实现的，从根本上就不可能在空间上开出非 $32$ 整数倍的位数吧。这跟你用多少位是两回事（

在文章《题解：P10013 [集训队互测 2023] Tree Topological Order Counting》发表评论：

orz

在讨论《诡异错误 WA#2》回复：

`ask` 中变量 `u` 定义了两次。建议以后在编译指令中加入 `-Wall`（

在讨论《诡异错误 WA#2》回复：

`insert` 会越界吗（）

1. 将整块部分最内层循环个数降到 6 左右； 2. “使用更快的BIT”； 3. 将块长设为 $2^k$（512 就不错），除块长的时候直接位运算； 4. 不要 #dill。

## AC 自动机 解决多串匹配问题。具体地，所有查询串构成一棵 Trie 树，对于每一个节点维护 fail 指针，指向这个节点**最长的在Trie树中出现的真后缀**。 暴力的构建方式是简单的。设 $u$ 通过字符 $c$ 指向 $p$（$t(u,c)=p$），现要得出 $fail(p)$。若 $t(fail(u),…

## [虚树](https://www.luogu.com.cn/problem/P2495) 将原树上的关键点和其LCA抽出来独立建一棵树。 先求得原树dfn序，并将所有关键点按照dfn排序。求得相邻两项的LCA。将LCA和关键点一起再次排序以后，枚举相邻两项，连 $\operatorname{LCA}(p_i,p_…

## [二分队列](https://www.luogu.com.cn/problem/P10538) 这玩意浪费了我12h。 *** 考虑设 $f_T$ 表示坐 $T$ 号列车刚到终点时的最小花费，将 $T$ 按照发车时间 $a$ 排序，则有： $$f_{T}=T.cost+\min_{M.y=T.x,M.b\leq…

## [跳跳棋](https://www.luogu.com.cn/problem/P1852) 关键性质：跳动时只能恰好越过一个棋子。 设三个棋子位置为 $a,b,c,d_1=b-a,d_2=c-b$。观察“往里跳”的操作。 如果 $d_1 d_2$，只能挪动 $c$. 如果 $d_1=d_2$，你就寄了，动不了。…

## [杜教筛](https://www.luogu.com.cn/problem/P4213) 求积性前缀和，即 $S(n)=\sum_{i=1}^nf(i)$. 某些不是积性的函数也可以，只要能找到一个合适的 $g$。 *** 对于任意两个数论函数 $f,g$，有$\sum_{i=1}^n(f*g)(i)=\sum…

首先特判掉 $k=1$ 的询问。静态区间查询随便写点啥就行。 注意到区间 lca 一定是相邻两个数 lca 中最浅的一个。预处理原序列相邻两个数的 lca 的深度得出一个长为 $n-1$ 的新数列 $b_i$，一个询问转化为求 $\max_{l\leq p\leq q\leq r-1,q-p+1=k-1}(\min_{…

在讨论《关于此题实现细节的疑问》回复：

对不起，此贴结。楼主是傻逼，不知道队列里的点可能已经操作过了。

在讨论《关于此题实现细节的疑问》回复：

@[alexbear103](luogu://user/416959) 可能更重要的问题是代码的正确性而不是如何写代码吧（？

在讨论《关于此题实现细节的疑问》回复：

这是不是算讨论区题解（）但是好像没办法在不给代码的前提下阐述清楚问题啊。。

具体见代码注释。我感觉题解到处都是问题但是它就是过了…想知道为什么。 ```cpp #include using namespace std; constexpr int N = 400010; int n, m, T, q[N], fa[N]; bool vis[N]; unordered_set G[N], s[N…

在讨论《建议加强数据强度》回复：

那照你这么说 A+B Problem 是不是也要加强高精度了（）

在讨论《我被「小周老师」碰瓷了！》回复：

为什么对cxy下手呢，因为那个金牌神仙周教过，也这么宣传过。两套标准在自己身上混着用 可以达到意想不到的效果。

在讨论《洛谷 Dataset 代码征集公告》回复：

1

在讨论《T2玄学做法求估分》回复：

@[SJH_qwq](/user/761125) ccf的数据应该不太可能比洛谷还水吧？？？

在讨论《T2玄学做法求估分》回复：

```cpp #include //g++ t2.cpp -o t2 -O2 -std=c++14 -static using namespace std; struct operation{ char op; int x; int y; }q[200005]; int n,m; int N(int k){//非 if…

我t2的做法是这样的：先假定所有的变量都为True，然后模拟一遍。然后再以模拟出来的结果为基础，再模拟一遍。观察所有变量两遍模拟后的值，若二者相反，即以原来的输入为基础推出了完全相反的结果，则这个变量只能为Unknown。 但是这样会出问题，在于“直接把一个元素赋为Unknown”这个操作。例： ``` + 1 2 +…

在讨论《告诫 WA52pts 的人》回复：

感谢