Here's something encrypted, password is required to continue reading.

Here's something encrypted, password is required to continue reading.

伟大的离线算法！

Here's something encrypted, password is required to continue reading.

Here's something encrypted, password is required to continue reading.

Here's something encrypted, password is required to continue reading.

RP++

Here's something encrypted, password is required to continue reading.

Week 1

2025.6.10

P7576 紫

首先考虑暴力 DP ，记 $dp_{i,j,k}$ 为前 $i$ 个数，第 $i$ 个数加 $j$ ，操作次数为 $k$ 序列权值之和。

那么有：

$$dp_{i,j,k}= \sum _{x=1}^j dp_{i-1,x,k-(j-x)}+\sum_{x=j+1}^t dp_{i-1,x,k}$$

注意到一个状态是有效的，当且仅当 $j \le k$ ，所以对于每一个 $i$ ，真正有用的 $dp$ 值至多不会超过 $10$ 个。

于是我们就可以考虑把每个 $i$ 换成矩阵。

考虑这道题怎么做，对每个位置维护一个转移矩阵，然后使用线段树维护区间乘法就可以了。

时间复杂度：$O(nt^6+q \log n t^6)$ 。

发现会被卡掉，于是考虑优化。

在每次询问的时候，定义一个向量，然后用向量乘上线段树上的 $\log n$ 个区间即可。

Week 1

发现之前遗漏（或忘记）的知识点有些多，于是这周好好补一下。

2025.6.3

扫描线

求多个矩形的面积并。

首先易得答案为 $\sum 截线段长度 \times 扫过的高度$

考虑把矩形的横边按照 $y$ 排序。

为了快速计算出截线段长度，可以给横边附上 $1$ 或 $-1$ 的权值，记下边权值为 $-1$ ，上半为 $1$ 。这样按照 $y$ 往上扫时，就可以快速地将已经计算过的删掉。

考虑将每个矩形的边的端点先投影到 $x$ 轴上，对于每个被这些点分割的线段，使用线段树维护现在截线段包不包含这个。那么写一颗区间修改单点查询的线段树即可。