最近看到学长txc爷的blog里写了个“最近写的题目”

然后心血来潮准备自己也弄个这个东西

线段树

首先观察数据范围，发现$a_i \le6$，这个是一个非常有用的性质。

发现$\mathrm{lcm}(1, 2, 3, 4, 5, 6)=60$，这个数有一个非常优美的性质：把$t$再$\mod 60$意义下进行不会影响结果的正确性。

分块 + 斜率优化

G真的比F2清真

首先，看到树上 + 子树操作，第一反应使用dfs序拍平。

那么这个问题就变成了支持：

• 区间$a_i += x$
• 询问区间$\max{|a_i| * |b_i|}$

瞎搞DP

CF出了H没出G 菜的真实

发现$k$从$\texttt{E}$题的$100$变成了$O(10^{12})$，考虑与$k$复杂度无关的做法。

我们考虑$f_{i, j}$表示以$s_i$开始，本质不同的长度为$j$的子序列数量。

线段树乱搞

考虑如果要重排一段区间使得它是回文的是可行的

首先对这段区间的长度分类讨论

哈希 + 二分 + DP

首先看到题面，很容易想到一个$DP$，令$f[i]$为划分到$i$为止的方案数。

然后朴素的暴力转移是$O(n^2)$的，非常显然一个状态$i$能够转移到的$j$是一段连续的，进而想到使用前缀和优化。

$set$瞎搞

首先非常显然，一个矩形$(x1, y1, x2, y2)$的代价就是$\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j]$，我们用$f[i][j]$表示以$(i, j)$为左上角的矩形的代价。即矩形$(i, j, i + a - 1, j + b - 1)$的代价。

我们首先考虑如何求出$f[i][j]$。

Round 1

咕咕咕。

回头再补。

set​瞎搞

预处理

我们考虑一下，一只青蛙能够影响的区间是什么

我们发现，如果将每只青蛙能够吃到的文字区间$[l, r]$按照左端点$l$排序，然后把后面的区间和前面的区间的重复部分去掉，那么就可以得到一个青蛙真正可以吃到的蚊子的范围区间

有趣的交互题

我们考虑一件事情

如果我们询问的矩形中有一个端点

那么答案 $\mod 2 = 1$

否则答案 $\mod 2 = 0$

换句话说，就是如果询问到的答案$\mod 2 = 0$，那么这个矩形内要么没有端点，要么有两个端点