世界上最遥远的距离
不是生与死的距离
而是我和你一起睡裙,你却秒了我不会的题

矩形加 矩形求和

一开始以为不可做… = =因为不会合并标记

后来发现在标记永久化之后 标记实际上不是打在外层的点上 而是打在这个点的子树里

每次查询到外层的点的时候顺便查一下这个点挂着的子树 然后加上贡献就好了

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)$的做…

By 准备退役旅游的 Cansult