CF543E Listening to Music
Codeforces Luogu 分析 我们要让小于 $x$ 的数最少，即让大于等于 $x$ 的数最多。 那么我们可以对于每个大于等于 $x$ 的 $a_i$，将能覆盖到它的左端点的区间加上 $1$，这样子查询 $[l,r]$ 中的最大值就可以得到答案了。 仍然用上面的思路，但是我们考虑用分块维护这个区间加 $1$ 区间求最大值。 这个很好分块维护：对于整块，我们直接打标记即可；对于散块，我...
分类 题解 下的文章
- 首页
- 题解
洛谷5471 [NOI2019]弹跳
Luogu 分析 首先容易看出一个暴力，即每个点向能到达的点连边，然后最短路即可。 然而边数是 $\mathcal{O}(n^2)$ 级别的，我们需要优化连边。由于是向矩形范围内的点连边，所以考虑 KD-Tree 优化连边。 对于城市 $u$ 向矩形连的边，我们在 KD-Tree 上遍历：如果当前节点范围包含在矩形内，则 $u$ 直接向这个节点连边；如果当前节点范围与矩形无交，则直接返回；否...
洛谷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 卷]信号传递
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...
洛谷5891 Fracture Ray
Luogu 分析 对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。 然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。 但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父...
洛谷6623 [省选联考 2020 A 卷]树
Luogu LOJ 分析 考虑每个节点用一个数据结构维护子树中所有点的信息。 则我们需要支持插入、合并、全局加 $1$、求全局异或和四个操作。 可以用 01-Trie 来维护。前面两个操作是基本操作。 考虑全局加 $1$。如果是一个偶数，它的最低位会变为 $1$；否则它的最低位会变成 $0$，然后给次低位加上 $1$，仍然可以根据次低位讨论。放到 Trie 树上就是从低到高枚举每一位，交换当...
洛谷6624 [省选联考 2020 A 卷]作业题
Luogu LOJ 分析 显然莫比乌斯反演一下，可以得到 直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。 另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel 代码 // ======================...
洛谷6620 [省选联考 2020 A 卷]组合数问题
Luogu LOJ 分析 预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include...