树分块做法。 可能会存在子树内一个关键点都没有的，然后先走到一条被关键点标记过的路径，但还没有到关键点。 如果当前子树内一个关键点都没有要先走完。 其实就是 ```qry``` 和 ```mdf``` 都要在开头写 ```for(;x&&!tag[x];x=fa[x]) ();```。

这题维护的是 $1$ 到 $n$ 最小路径，不是整棵树的 $\max$，查询时需要 $\text{split(1,n)}$ 找最大值。

在讨论《求刚刚 CF Div2D 的简单写法》回复：

大概瞪了一下，就是找一个子树和父亲另一个更深的子树合并吧，开个 set 随便维护一下。

在讨论《求助关于心态》回复：

@[yinbe_swsgroitfh](luogu://user/759152) 多打

在讨论《请求撤下题解 / 添加管理员提示》回复：

@[Eason_cyx](luogu://user/741244) 写的时间比较久远了来着，已经重新提交了。

在讨论《如此状态，如何OIPN？》回复：

@[yanmingqian](luogu://user/751563) 撅撅你的

简单题。 能够发现数值形式是一个 $n$ 进制数，也就是说我们可以逐个确定 $x,\text{lca},y$，对于每个 $x$，$y$ 有 $n$ 种选择，所以 $\lceil \frac{k}{n} \rceil$ 就是 $x$，然后我们令 $k \gets k\bmod n$，去确定 $\text{lca}$，不难…

vp 的时候犯蠢了，最后一个小时跑路没写完这题。 能够发现 $\operatorname{lcm}(1,\dots,10) = 2520$，那么 $x$ 和 $x+2520$ 是等价的，记 $l = 2520$，可以按此分段做，维护每个时间出发的最小步数，这个时候用 bitset 维护再倍增可以做到 $O(\frac{…

主席树的 pushdown 需要新建儿子节点，那么再走到儿子的时候不能再按照 las 新建了，因为已经有新的 tag 被下放，需要判断当前节点编号和 las 的编号一致再新建。

> 给定两个初始为空的数组，每次对 $a$ 单点修改，$b$ 每次会加上 $a$ 的前缀 $\max$，每次对 $x$ 单点修改后回答 $\sum \limits_{i=1}^x b_i$。 > > $1 \le n,m \le 10^6,1 \le a_i,x \le n$。 这么深刻。 考虑直接做的话，需要动态维护…

> 给定一个序列，定义区间价值为 $\text{OR}$ 和，$\text{AND}$ 和，$\gcd$ 的乘积，给定 $q$ 次询问，回答区间 $[l,r]$ 的所有子区间价值和。 > > $1 \le n \le 10^6,1 \le q \le 5 \times 10^6$。 神题。 能够注意到 $\text{O…

> 给长一个长 $n$ 的序列，$q$ 次询问，每次给定一个区间，求有多少 $k$ 满足区间 $[l,r]$ 可以划分为 $k$ 段 $\operatorname{mex}$ 值相等的子段。 > > $1 \le n,q \le 6\times 10^5$。 静态区间 $\operatorname{mex}$ 原来可以…

精简了下 dp 做法，大多是感性理解。 首先，有一个简单的观察，对于 $u$ 或者 $v$ 的父亲如果是 $\text{LCA}$ 的话，这条边是没有优化空间的，而且，如果将这个询问加入我们的决策的话，反而可能会导致我们拿不到原来可以优化掉的边，于是，这样的询问我们特判掉。 此时如果使用贪心做法，将每个点的 $\tex…

> 给定一棵树，每个点上有若干字符串，支持三个操作： > > 1. 查询两点之间距离。 > 2. 查询两点之间某字符串个数。 > 3. 查询并删除两点之间某字符串。 > > $1 \le n \le 10^5，1 \le \sum S_i \le 5\times 10^5$。 字符串长度很小，直接将其离散化后看作权值，…

发现在二维平面上问题不太直观，考虑扔回序列考虑，我们将每个点 $(x_i,y_i)$ 视作区间 $[y_i,x_i]$，即要找出满足 $l \le y_i \le x_i \le r$ 的最小 $r_i - l_i$。 将所有区间挂在右端点考虑，一个朴素的想法是直接维护区间 $r_i - l_i$ 然后区间 $\tex…

咦，怎么是值域段。 发现 $n \le 10^6$ 没法分块，在线询问不好做，考虑离线扫描线。 考虑每次新增一个点，$p_x$ 是 $x$ 上一次出现的位置，$[1,p_x]$ 这段区间是已经统计过 $x$ 的贡献了，我只们只需要考虑 $(p_x,i]$ 这段区间，对于每个数都同理，只需要考虑其最后一次出现的位置后面的…

由于矩形不包含，于是我们将点按照 $x_i$ 排序后，$y_i$ 一定是降序排列，那么就可以写出 dp 式子，设 $f_i$ 表示前 $i$ 个矩形的最大值： $$f_i = \max \{ f_j + y_i(x_i - x_j) - a_i\}$$ 发现这是斜率优化形式，将原式写作 $f_j = x_jy_i +…

首先断环为链，那么我们需要对 $n$ 个序列 dp。 考虑设 $f_{i,k}$ 表示到第 $i$ 个位置，建了 $k$ 个谷仓的最小移动距离，那么有转移： $$f_{i,k} = \min \{ f_{j,k-1} + w(l,r)\}$$ 其中 $w(l,r) = \sum \limits_{i=l}^r a_i(…

对于一个 $j$，如果其所在连续段以 $i$ 为开头，记 $s = \sum \limits_{k=i}^j t_k$，那么其一次通关的概率是 $\frac{t_j}{s}$，期望时间为 $\frac{s}{t_j}$。 对一个连续段，每个关卡一定是顺着通关的，这样我们就可以考虑 dp 了。 不考虑分段的限制，设 $f…

凸优化入门。 不妨设 $f_{u,i}$ 表示以 $u$ 为根的子树内，到叶子有 $i$ 个黑点的最小修改次数，转移很简单： $$f_{u,i} = \min \{[a_u = 1] + \sum f_{v,i-1} ,[a_u = 0] + \sum f_{v,i}\}$$ 特判一下叶子即可，直接做复杂度是 $O(n…

> 给定 $n$ 个二元组 $(a_i,b_i)$，规定一个子集的代价为 $a_i$ 与 $b_i$ 最大值的乘积，求划分最小代价。 > > $1 \le n \le 2\times 10^5,1 \le V \le 10^6$。 怎么被一眼秒了。 由于是子集划分，我们不好直接 dp，考虑能否通过某些手段使其变为区间划…

非莫队做法，处理出现次数 $\ge B$ 的点时，如果这样写了： ```cpp fo(1,i,n) if(vis[i]>=M) { fo(1,j,n) pre[j]=pre[j-1]+(a[j]==i); for(auto [l1,r1,l2,r2,id]:Q1) ans[id]+=(pre[r1]-pre[l1-1]…

> 给定一棵树，边有向且有权，造船需 $L$ 的时间，坐船顺走边权为 $a_i - z_i$，逆走边权为 $a_i + z_i$，不坐船边权为定值 $L$，$q$ 组询问，回答 $u,v$ 之间最短路。 > > $1 \le n,q \le 2\times 10^5,0 > g[N]; struct node{ll a…

开 long long。

一百万个套路和在一起。 假设 $l_1 = r_1$，那么我们可以对 $l_2,r_2$ 差分，然后将问题转为形如查询 $[l,r]$ 内 $\max - \min$ 的值，直接覆盖的话不好做，考虑单调栈维护，栈内维护每个最大值控制的极大区间，然后在弹栈过程中做区间加减法就可以代替区间覆盖的作用，且极长连续段只会有 $…

复健。 注意到对于一个子树内，将 $v_i$ 大的放在前面一定最优，那么即将问题转化为对每个子树求带权权值和，且带的这个权是其在自己所在子树内的排名。 考虑拆贡献，因为答案是求和，于是我们可以直接算出每个 $v_i$ 的系数和统一计算。具体来讲，其只会在它祖先上产生贡献，可以对 $v_i$ 排序后轮流插入，顺带维护当前…

### day -? 初赛模拟怎么垫底了。 ### 初赛 出门怎么忘带涂卡笔了。 next 数组怎么求来着。 写写写写写，阅读程序什么玩意，跳了做后面的，完善一降智，完善二什么玩意，奥奥奥，分组 check 就行吧，唉他怎么是暴力 check 的，```is_permutation``` 是什么玩意来着。 回头看阅读程…

这题怎么只有绿。 先对答案容斥，已知总方案数为 $2^n-1$，求出 $\gcd \neq 1$ 的情况即可，考虑一个暴力做法，设 $f_i$ 为 $\gcd = i$ 及其倍数的方案数，套个容斥系数即可，复杂度 $O(2^V)$ 左右。 考虑优化这个东西，发现每个数只需要看其本质不同的质因子就好了，而本题中每个数本质…

这题咋黑的。 肯定要考虑从右向左扫描线，在线段树上如何维护这个东西。 我们在线段树上每个位置维护从 $i$ 开始能到达的花的个数，不妨考虑扫描线时最初没有任何限制，那么每加一朵花，带来的都是一个前缀加 $1$，而当我们加入一个矩形，在扫描线上体现的就是一个区间 $[l,r]$ 的限制，显然之前的所有花都走不到这个矩形内…

小清新 Ynoi，我又忘了什么被我放进任务计划里的了。 发现操作很奇怪，每次减小最大值及其左右，考虑分析性质。 能够发现，最大值及其左右的大小关系是永远不会改变的，那么，我们操作的顺序只取决于选择最大值的顺序，但是如果我们将操作序列重排一下，那么每一次操作就是将最大值及其左右清 $0$，并且操作次数加最大值。 此时，我…