Codeforces Global Round 28
https://codeforces.com/contest/2048
F. Kevin and Math Class
a[n]
b[n]
目标 让所有ai=1, 求最小操作次数
每次操作选择l,r
令 x=min(b[l..r])
a[l..r]/=x (向上取整)
范围
2s
1024mb
n 2e5
ai [1,1e18]
bi [1,1e18]
我的思路
如果向下取整很常见，会注意到 顺序可换 x/a/b=x/b/a
那么向上取整，x in (kab,(k+1)ab], 同样是顺序可换
想法1.
如果最小的b 对应的a不是1,那么需要一次全区间
这样一些操作后，可以把a按照1的存在切割成多个块。没想到然后怎么用
想法2.
另一个是b=2的话，那么至少存在一个方案，每次全部操作，是log级别，所以 最优次数智慧更少，也没想到怎么用
想法3.
预处理，如果 相邻的 i,j=i+1有 ai >= aj, bi <= bj, 那么i每次操作带上j, 这样只要ai=1了那么aj必定等于1, 这样可以得到 相邻的a,b大小关系是一致的，也没啥用
想法4.
想贪心，用操作后的最大值来表示，但很快找到反例
- a=100 1 100
- b=100 2 100
这样 操作一次后的局部最优是 50 1 50, 而这无法达到最终的最少次数，
题解
笛卡尔树
建立小根笛卡尔树（这玩意能想出来，但怎么用没啥想法）
只会操作 笛卡尔树上的区间（显然）
然后是 笛卡尔树上dp 啊 这就是第一次搞了
$f_{u,i}$ 表示 只考虑$u$ 子树内的所有位置进行i次操作之后区间内$a_x$的最大最小是多少，
$f_{u,k}=\min_{i+j=k} min(max(f_{lu,i},f_{ru,j},a_u))$
然后考虑 这个位置的除法操作
$f_{u,k+1} \leftarrow \lceil \frac{f_{u,k}}{b_u}\rceil$
这样状态数 是 O(n * log a) 的
合并代价 是min-max卷积 等价于 归并排序(合并时每个状态的均摊代价为常数），可以 总复杂度O(n log a)
E Kevin and Matrices
所有n行m列，每个值在[1,v]中整数的矩阵中，有多少满足
min(行max) <= max(列min)
求个数 mod 998244353
范围
6s
256mb
n * v 1e6
m 1e9
我的思路
先是找特性的抽象
不妨设左边的值为w
那么意味着 每行的max >= w,其中一个是w,不妨设 aij=w
那么 对于aij同行的其它值 <=w, min(aij所在列)<=w, 这样说明右边值<=w
w<=右侧<=w,说明右侧只能是w
所以对于给定w问题变化为 左右同时=w时的值
先不考虑重复的话，我们给每个值变成 (ai,i,j) 也就是不光有值还能标识位置，我们希望左右的min,max输出不只是值而且还包括位置。
那么希望 左侧输出的三元组 = 右侧输出三元组， 这里当有多个三元组都可以输出时，我们可以钦定
若 a[ij] = (w,i,j)且被两边选择为 输出值
那么
- 被左边选择，需要 同行不大于它，其它行的max 不小于它
- 被右边选择，需要 同列不小于它，其它列的min 不大于它
这两个性质的交 就是： 同行不大于它且同列不小于它
对应的方案数 = $w^{m-1} * (v-w+1)^{n-1}$
然后如何解决重复的问题呢？
题解
提示 #1
左式能小于右式吗？
提示 #2
考虑式子中取到最值的位置，它们有什么性质？
提示 #3
考虑容斥原理。
提示 #4
二项式定理。
依然是只能相等，
对于取到 最值的两个位置P,Q
- 那么 P,Q如果不同行同列，那么它们的交叉点也是取到最值！！！！！
- 在这个观察下+归纳下，满足上面性质的所有w构成子矩阵
然后容斥，定义一个属性是(k,i,j)
注意到 容斥关系
- 如果k不同，那么它们的交的 贡献为0
- 如果k相同，f(属性 集合) = (-1)^{属性个数} (状态)
对于 (值=k,子矩阵大小 i * j)：
$\binom{n}{i}\binom{m}{j}k^{i(m-j)}(v-k+1)^{(n-i)j}v^{(n-i)(m-j)}$
分别表示，=k的行选择，=k的列选择，这些行剩余部分<=k,这些列剩余部分>=k, 整个矩阵剩余部分随便填
这题解(-1)的幂次没看懂???
小节
F:
感觉它也用到了顺序不影响的性质，然后这个 笛卡尔区间 带次数的 max,就比我那个想的max 有意义了 和 满足局部性了，这样才能dp
这里的 核心拆解在于 笛卡尔区间的拆分
我上面想的 按ai=1的拆分，就缺少这种二分性 和 形状固定性（因为ai会随着计算变化）
所以 这个关键看到bi 建立笛卡尔树能想到是关键
- 所以总结是：笛卡尔树的划分，可能带来新的局部性
G:
这个子矩阵没观察出来真不应该，倒是知道向容斥想