原题链接：https://loj.ac/p/6913 ~~变态扫描线~~。 ## 形式化题意 给出 $k$ 行 $n$ 列的矩阵 $(a_{i,j})_{1\leq i\leq k,1\leq j\leq n}$，对 $q$ 个询问，每次询问给出 $l,r$，求： $$ \sum_{l\leq x\leq y\leq r}F\bigg(\max_{1\leq...

神题，写篇题解学习一下。 学习 [大犇的题解](https://www.luogu.com.cn/article/f8ob8nzl)。 显然 $c_i$ 一定能写成 $a_ix+b_iy$ 的形式，考虑操作会对两部分有什么影响： * 如果 $r_i=0$，那么 $a_i=a_{i-1}+1$。 * 如果 $r_i=1$，那么...

题目保证存在一种合法方案，我们可以考虑由一个合法方案怎么调整出不同的合法方案。 为了方便理解，我们钦定优先向左遍历，把换向操作转换成翻转子树的操作。 容易发现，翻转一棵子树时已经合法匹配的点不受影响，那么只有那些当前未配对的点需要考虑。跟虚树的角度差不多，我们把这些子树内已经匹配上的点踢掉分析。 分析问题的重要方法：从小入手。 ### 两种颜色...

# 前言 本文去掉代码全文共 4800 字。 这篇博客并非完全意义上的题解，主要是对我学习这道题的思路回顾与总结，基于以下两篇题解融合和补充（所以记号不是我原创的，我觉得尤其是第二篇题解定义的名词非常形象易懂直接抄了），以及一些碎碎念。 写了很多细节问题，都是我在学习这个题时思考过的，所以这篇文章非常长。 两篇神犇的题解： 1....

Slope Trick 是一种 DP 优化方法，它通过存储斜率变化以存储凸包优化转移。下面我们通过三个题理解这个神奇的 trick。 ## [洛谷P4597 序列 sequence](https://www.luogu.com.cn/problem/P4597) 这题是 CF13C 的数据加强版。 ### 题面大意 给定一个序列，每次操作可以把某个数 +1...