美食家
很显然可以写出矩阵。
发现相当于有 \(q\) 次询问 \(A^k\)，预处理矩阵的 \(2^0,2^1,\cdots,2^w\) 次幂然后用向量乘矩阵即可做到 \(O(n^3\log T+qn^2\log T)\)。
命运
没发现链是祖先-后代这样的，想了一年不会做
有这个性质就可以直接 dp 了，然后线段树合并优化。完整题解。
这是带标记的线段树合并。很自然的想法是，在线段树合并递归下去之前，我们先把 \(p,q\) 的标记下传。但由于我们肯定是动态开点，下传标记的时候，如果没有儿子，需要新建儿子然后把标记传下去。
但当线段树合并的时候，如果遇到两个节点 \(p,q\) 都没有儿子，但都有标记，那么会直接把 \(p,q\) 的子树都建出来。此时的解决办法是，我们特判 \(p,q\) 中任一节点没有儿子的情形（不妨设其为 \(q\)），这种情况下 \(q\) 那边的所有叶节权值均为 \(f_q(0)\)，其中 \(f_q\in F\) 表示 \(q\) 节点上的标记函数。
但如果仅特判两边都没有儿子的情形，复杂度仍然是错误的。
那么我们可以直接在 \(p\) 节点上打标记，表示这个区间内的所有元素 \(x\) 均由 \(x\leftarrow x\times f_q(0)\)，其中 $\times $ 是叶节点的操作。由于多了一种操作，还需要改改标记函数。那么最终我们要维护的就是区间覆盖，区间加，区间乘。这个还是比较简单的。这样就可以做到只要一边没儿子就直接返回了？
我觉得这种东西很神秘，他在原本的操作中加入了一种新操作，即区间 \(x\leftarrow x\times v\)，其中 \(\times\) 是叶节点操作。如果 $\times $ 这个运算变困难一点是不是就做不了了[晕]，比如 \(\text{xor}\)，或者 \(x\times y=\gcd(x,y)\)，这种。哦不过这种，貌似只特判一边也做不了啊？但是如果不带区间操作那么线段树合并是完全可以处理任何叶节点操作的，很神秘啊，有没有 ds 大师教教[可怜]
时代的眼泪
制作菜品
首先把 \(d\) 排序。不难发现，由于 \(d_1\) 肯定要被用，因此必须有 \(d_1+d_n\ge k\)，否则根本用不了 \(d_1\)。
不难想到一个贪心：每次选出最小的 \(d_1\)，找到满足 \(d_1+d_i\ge k\) 的最小的 \(i\)，用 \(d_i\) 耗尽 \(d_1\) 即可。
然后我们写一下发现过不了样例 \(2\)，但是居然能过样例 \(3\)？？
大胆猜测 \(m\ge n-1\) 时这个算法都是正确的。交一下发现确实是对的（不是）。
那考虑 \(m=n-2\) 怎么做。
发现 \(m=1\) 肯定无解，\(m=2\) 的时候，设四个数分别是 \(a<b<c<d\)，那么有解必须要有两个数加起来 \(=k\)，剩下两个数加起来也 \(=k\)，否则我们肯定凑不齐两个。
欸我们发现这个很有感觉对不对。那你再想想就发现如果给每个盘子两种材料连边就至少有两个连通块，每个连通块的 \(m\) 都 \(\ge n-1\)，那所以必须得能分出来一个和恰好为 \((|S|-1)k\) 的子集 \(S\)。
直接做或许还要记录个数，但我们直接把每个数都减去 \(k\) 就相当于只需要和为 \(-k\) 了。
那 bitset 优化背包就行，单组数据复杂度 \(O(\frac{n^2k}{w})\)。
超现实树
样例 \(2,3\) 给到了比较好的提示，我们发现如果这个节点处，这三种树都存在，那么他就几乎等价于一个单点；而单点自然是 Almost Complete 的。
但问题在于你这三种子树所在的树可能别的地方形态不一样导致实际上没法缩成单点
经过看题解毛估估之后发现另一边得是单点才行，那就完事了
翻修道路
操吴戈兮披犀甲
标签：标记,loj,线段,times,NOI2020,ge,节点 From： https://www.cnblogs.com/YunQianQwQ/p/17512033.html