只更新 DEF
看了一眼standings榜一居然十二分钟写了一个剖分,感觉有点猛,仔细把代码都看了一遍发现是开黑的。逆天。
比上一场 div2 质量不知道低到哪里去了。
D
对于不同的 \(f(x)\) 一段一段求,\(f(x)\) 一共 \(\log\) 种,指数也是 \(\log\) 种。全都是暴力。
E
对于一段不为 \(1\) 且相邻 \(\rm gcd\) 为 \(1\) 的区间,间隔放,每次答案减少 \(2\),这个最优。如果区间长度为 \(2\) 那每次操作将答案减少 \(1\)。
对于 \(1\) 区间每次对答案减少 \(1\)。但是如果你把一个连续的 \(1\) 变成了连续的 \(0\) 那么额外给答案减少 \(1\)(如果这样的区间有一个端点是 \(1\) 或者 \(n\) 则没什么用)
对着这个贪心就行了。
F
把树建出来,操作序号大于这个点标号并且操作位置是它祖先的就有贡献,显然树链剖分