10.17 小记录

link to problem

记录原因：自己做法代码长度太长。

自己的做法：

link to submission

离线下来，离散化。题目是要求连续段的个数。

考虑先做 Subtask \(2\) 的预处理。一个操作会改变什么？分两种情况：从大到小，从小到大。（以下，设 \(id\) 为题目中 \(C_i\)，\(c\) 为 \(a_{C_i}\)，\(d\) 为 \(D_i\)，\(mn=\min(a_{id-1},a_{id+1})\)，\(mx=\max(a_{id-1},a_{id+1})\)）。

• 从大到小。和 Subtask \(2\) 方法类似，\([d+1,\min(c,mn)]\) 区间答案加一，\([\max(mx+1,d+1),c]\) 区间答案减一。

• 从小到大。和 Subtask \(2\) 方法类似，\([\max(mx+1,c+1),d]\) 区间答案加一，\([c+1,\min(d,mn)]\) 区间答案减一。

这里，“区间 \([l,r]\)”是指询问一为 \(x\in[l,r]\) 中的答案。

可以用线段树维护。

别人的做法：

link to submission

好短啊。其实就是一个方法，但是可以做到单点修改。