文章

首先不难想到对题目进行一个转化：对于询问操作，其实就是以 $>x$ 的位置为断点，然后问剩下的区间贡献和（形如 $\sum\frac{len(len-1)}{2}$ 的贡献式）。 $>x$ 的这个断点限制很不好办，可不可以将所有的询问按照 $x$ 从小到大排序后依次处理呢？ 那么现在的任务就是维护一 阅读更多…

查询 $kth$ 的话，就分块来讲，通常可以考虑值域分块。 具体操作就是将值域分块，然后询问的时候先确定块，再确定目标位置。 令 $sum_{i,j}$ 表示前 $i$ 个序列块，第 $j$ 个数值块的出现次数；$cnt_{i,j}$ 表示前 $i$ 个序列块，第 $j$ 个数的出现次数。 这样话查 阅读更多…

题目传送门 2020 的遗愿 题意 给定一个序列，支持区间替换和区间 $\text{kth}$ 操作。 Sol 因为是最初分块所以考虑序列分块。（一般情况我们查询区间 $\text{kth}$ 都是树套树啥的。 带上二分，线段树套平衡树是 $\log^3 n$ 的。 我们这里也考虑树套树（？ 好像 阅读更多…

首先考虑一个全局的做法。 对于这个 $1$ 号操作，我们有两种方式做： 将所有 $\leq x$ 的数加上 $x$，然后全局打上一个减法标记。 将所有 $>x$ 的数减去 $x$ 。 如果当前全局最大值是 $lim$ ，那么第一种方式相当于用 $x$ 次修改将 $lim$ 减去 $x$ ，第二种方式 阅读更多…

区间数不同的数的个数是个常见的套路，不说了。 考虑这个区间修改怎么办——意味着需要修改一堆数的 $pre$。 假设对于修改前，有一段区间 $[l’,r’],l\leq l’\leq r’\leq r$ ，满足这一段区间中的数都是相同的。那么进行了修改过 阅读更多…

for test Solution 让 $D_i$ 表示 $a_x$ 为 $i$ 的 $x$。 $ans = \frac{1}{n(n – 1)} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} dist(D_i, D_j) \varphi 阅读更多…

考虑容斥，枚举哪些路径一定不合法即可：$\sum (-1)^{|S|}2^{(n-1)-val_S}$ 。其中 $val_S$ 指 $S$ 中的路径覆盖的边数条数。 因为所有的路径的两个端点满足祖先关系，考虑用 $dp$ 解决这个问题。 令 $dp_{u,i}$ 表示对于所有起点在 $u$ 的子树中 阅读更多…

游记和题解分开了 >_< T1 出题人出题前就没想过自己马的安全么？ 考虑二分年份，然后暴力确定几月几日。二分年份的话按照 $mid\leq 1582$ 和 $mid>1582$ 两种情况讨论一下就好了。 $mid\leq 1582$ 的，因为公元前 $4713$ 年是闰年，所以直接看看有多少 阅读更多…