如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
M_sea的博客
——どうか悔いることなく 明日へ続く道 歩いて——洛谷4117 [Ynoi2018]五彩斑斓的世界
Luogu分析考虑分块。对于每一块，维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的，因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式如果 $2x\geq mx$，则直接将所有 $>x$ 的数减去 $mx$。这样子是 $\...
洛谷5355 [Ynoi2017]由乃的玉米田
Luogu分析考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O}(\...
洛谷5070 [Ynoi2015]即便看不到未来
Luogu分析把询问离线，从左往右加入每个数并维护以这个数为右端点时每个左端点的答案。假设当前加入了 $x$，那么它显然不会更新 $a_x$ 上一次出现位置之前的左端点的答案（因为这些区间排序去重后根本没有变化），而且只会和 $[x-11,x+11]$ 的数产生贡献（因为只需要统计 $\leq 10$ 的长度）。而插入 $x$ 后极长值域连续段可能会有以下变化从 $[a,x-1]$ 变成了 ...
洛谷6622 [省选联考 2020 A/B 卷] 信号传递
LuoguLOJ分析考虑从 $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-1}$ 个...
洛谷5891 Fracture Ray
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
洛谷6623 [省选联考 2020 A 卷] 树
LuoguLOJ分析考虑每个节点用一个数据结构维护子树中所有点的信息。则我们需要支持插入、合并、全局加 $1$、求全局异或和四个操作。可以用 01-Trie 来维护。前面两个操作是基本操作。考虑全局加 $1$。如果是一个偶数，它的最低位会变为 $1$；否则它的最低位会变成 $0$，然后给次低位加上 $1$，仍然可以根据次低位讨论。放到 Trie 树上就是从低到高枚举每一位，交换当前节点的左右...
洛谷6619 [省选联考 2020 A/B 卷] 冰火战士
LuoguLOJ分析看完题后可以发现几个结论：冰人能选的是一段前缀，火人能选的是一段后缀。总能量为能选的冰人的能量和和能选的火人的能量和中较小的那个的两倍。总能量是关于温度的单峰函数。答案一定是某个战士的温度。因为答案一定是某个战士的温度，所以先把所有温度离散化（下文的温度也指离散化后的温度）。看到这个单峰可以想到三分温度，但是由于有很多地方的值是相同的所以不太好三分；但是注意到冰人的能量和...
洛谷6624 [省选联考 2020 A 卷] 作业题
LuoguLOJ分析显然莫比乌斯反演一下，可以得到直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel代码// ==============================...
洛谷6620 [省选联考 2020 A 卷] 组合数问题
LuoguLOJ分析预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <b...
洛谷4091 [HEOI2016/TJOI2016]求和
LuoguLOJ分析后面显然是卷积的形式，直接 NTT 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h&...