CodeforcesLuogu分析首先把 $pos(p_k(n),x)$ 写成一个比较好看的形式考虑 $x_i$ 和 $x_{i+1}$ 这两个数对所有 $f(p_k(n))$ 值的贡献。根据初中数学套路,我们需要分类讨论:若 $x_i=x_{i+1}$,此时贡献全部为 $0$。若 $x_i\neq x_{i+1}$,我们令 $a=\min\left\{x_i,x_{i+1}\right\}...
Luogu分析设第 $i$ 个数的两个出现位置为 $a_i,b_i$。可以发现,若 $(a_i,b_i)$ 中有 $x$ 个数还没有消去,那么要把 $i$ 消去的代价为 $x$。于是我们可以从前往后扫,如果当前的数是第一次出现就在这个位置 $+1$,否则将答案加上 $(a_i,b_i)$ 的区间和并把 $a_i-1$ 。用树状数组维护这个过程即可。输出方案在扫的过程中顺便搞一下就好了。代码/...
BZOJ分析只考虑选的点都在线段下方的情况,在线段上方的情况可以通过将纵坐标取反一样的做。首先考虑线段的纵坐标无限大的情况,显然线段的左右边界会卡在相邻的两个颜色相同的点之间。那么只需要将所有点按横坐标排序,维护一下上一个某种颜色的点,再用树状数组维护区间内点的个数即可。现在把线段向下移动,假设现在纵坐标刚好比某个点 $u$ 的纵坐标小 $1$,此时线段左右边界会卡在上一个和 $u$ 颜色相...
Luogu分析做完这题感觉对 AC 自动机有了新的理解...注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀(这里建议想一想 fail 的定义),因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串,于是我们只需要把 $Y$ 的前缀...
AtCoder分析神仙题...我们先把所有只有只会从一个出口出去的机器人删掉,这些机器人不影响答案。对于剩下的机器人,记它到左边第一个出口的距离为 $a$ ,到右边第一个出口的距离为 $b$ 。那么每个机器人可以看成一个点 $(a,b)$ 。设 $x$ 为所有机器人往左移动的最远点到初始位置的距离, $y$ 为所有机器人往右移动的最远点到初始位置的距离。那么每次相当于把 $(x,y)$ 变成...
AtCoder分析令 $cnt=n(n+1)/2$ ,也就是生成的序列的项数。二分答案 $x$ 。如果最后的答案是 $x$ ,那么就有 $\frac{cnt}{2}+1$ 项的中位数不大于 $x$ 。考虑求出有多少项的中位数 $>x$ 。令 $<x$ 的数为 $-1$ ,$\geq x$ 的数为 $1$ 。那么一段区间的中位数 $>x$ 就相当于这段区间的和 $\geq 0...
CodeForcesLuogu分析比较简单的点分治。可是我调了好久先考虑一个简单版的题目:Tree。那道题统计答案是用的双指针。但是这道题多了一个 $L$ 的限制,所以在双指针满足 $W$ 的限制的同时,再用一个树状数组来满足 $L$ 的限制就行了。具体实现及细节见代码。代码// ================================= // author: M_sea // ...
LuoguBZOJLOJ分析首先考虑怎么求出所有交点。注意到 $a$ 与 $b$ 有交(假设 $y_{a,0}<y_{b,0}$ )当且仅当 $y_{a,1}>y_{b,1}$ 。那么可以用 $\mathrm{set}$ 来维护 $y_{x,1}$ ,然后暴力求出所有交点。因为交点个数 $\leq 500000$ ,所以可以过。容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立...
LuoguBZOJ分析先假装没看到那个 $a$ 的限制。设 $\mathbf{f}=\sigma$,$\mathbf{g}=\mathbf{f}*\mu$ 。预处理出 $\mathbf{g}$ ,然后数论分块计算即可。然而有 $a$ 的限制,所以忽略上面的那句话。发现,只有 $\sigma(d)\leq a$ 的 $d$ 才有贡献。那么将所有询问离线按 $a$ 排序,然后把所有数按 $\si...
LuoguBZOJ分析发现这题和 $\mathrm{Mokia}$ 差不多,把初始值看成单点加,查询拆成四个,然后就可以 $\mathrm{CDQ}$ 分治了。不同的是要把 $y$ 坐标离散化一下。具体实现及细节见代码。分析//It is made by M_sea #include <algorithm> #include <iostream> #include &...