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

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

$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$，那么这个矩形内要么没有端点，要么有两个端点

似乎莫得人是不用树剖的w

但是为什么的一只$\log$乱搞被树剖的两只$\log$爆踩啊

是因为我实现的太丑了吗

不管了直接讲做法好了

有趣的矩阵乘法

（为方便，下文中“大号宝石”代指连续的$m$个分裂出来的宝石，“小号宝石”代指未分裂的单个宝石）

首先，我们观察这题，考虑$DP​$，设状态$f_i​$表示已经取了$i​$个单元的方案数的不难推出一个朴素的$O(n^2) DP​$方程$f_i = \displaystyle\sum_{i - j \geq m} f_j +1​$（可以理解成上一个大号宝石放的位置，最后一个$1​$即为全部用小号宝石填满的方案）

我们再仔细看看这个式子，加个前缀和，不难优化到$O(n)$，然而数据范围$n \leq 10^{18}$，这让我们考虑$O(\log n)$级别的算法，我们接下来考虑矩阵乘法优化这个式子。

又双叒叕是题外话

今天模拟考是原题大战。

$T1​$是这题。
$T2$是某次$CF\ Div1\ E$题。
$T3​$反正是某道神仙题。

像我这样的菜鸡只能来做做相对可做的T1

虽然只是相对可做但是还是被全场切穿了啊喂

内心OS：这个不订正的理由真的nice

本篇题解讲述的为非完美做法，但是可以骗到96分

说实话我在网上找了好久结果都是这个$O(n^2)$的非正解树型$DP$

听说有个$O(N)​$的正解在某篇论文里？

算了反正我也看不懂

所以我接下来就介绍一下这个$O(n^2)$的树型$DP$吧QwQ

顺手丢一下我学习的这篇blog​吧

简单递归

首先我们如果要消灭一段区间$[l, r]$，我们可以有三种选择：

• 如果$[l, r]​$区间内没人，那么直接花费$A​$的代价将这段摧毁
• 如果$r > l​$（即这段区间长度$>2​$），可以选择把它切割成$\left[ l, \lfloor \frac{l + r}2\rfloor\right]​$ $\left[\lceil \frac{l + r}2\rceil, r\right]​$两段
• 如果$[l, r]$区间内有人，直接花费$b (r - l + 1)x$的代价将其摧毁。