世界上最遥远的距离 不是生与死的距离 而是我和你一起睡裙，你却秒了我不会的题
矩形加 矩形求和
一开始以为不可做… = =因为不会合并标记
后来发现在标记永久化之后 标记实际上不是打在外层的点上 而是打在这个点的子树里
每次查询到外层的点的时候顺便查一下这个点挂着的子树 然后加上贡献就好了
AH的毒瘤题1
很搞笑 出题人都搞不懂题是啥意思(
然后还说这题可以开到\(\mathrm O(n)\) (注意flag
给一个序列 每个元素有两种属性 \(a \in \mathbb{Z}, b\in [0, 1] \), 要求对每一个子区间\([le,ri]\), 都求出\(\min(le, ri)\cdot \sum_{i = le}^{ri} [b_i = 0] \cdot \sum_{i = le}^{ri} [b_i = 1]\)
首先很显然的是要对每一个数 都把他当做最小值 然后扩出一个区间\([le,ri]\)
设\(f(i, j) = \sum_{i = le}^{ri} [b_i = 0] \cdot \sum_{i = le}^{ri} [b_i = 1]\), 我们就要求出\(\sum_{i \in [le, id]} \sum_{j \in [id, ri]} f(i, j)\)
一开始我以为这个玩意是个矩形嘛 他肯定木得办法一维的求啊 然后就被广东的高一大爷教育了 \[ \begin{aligned} &f(i, j) = (s0_j - s0_i) (s1_j - s1_i) \\ &\sum_{i \in [le, id]} \sum_{j \in [id, ri]} f(i, j) \\ &\sum_{i \in [le, id]} \sum_{j \in [id, ri]} (s0_j - s0_i) (s1_j - s1_i) \\ &\sum_{i \in [le, id]} \sum_{j \in [id, ri]} s0_j s1_j - s0_i s1_j - s0_j s1_i - s1_js0_i \end{aligned} \]
这么一看这题还真能\(\mathrm O(n)\)的做…
神仙学弟的神仙题
要求\(\mathrm O(n)\)左右的预处理出每个点作为次大值的最长区间
居然炸出来SDOI出题人了...你看就不像我等小透明就天天被踢
首先用单调栈求出来左边和右边比这个数大的位置 然后用二分主席树(?)
By 准备退役旅游的 Cansult