航电第三场单峰数列,如何为?

摘要:单峰数列 题意对于一个整数数列,如果其先严格递增,然后在某一点后严格递减,我们称这个数列为单峰数列(严格递增和严格递减的部分均要是非空)。 给定长度为 n 的整数数列 (a_1,a_2,…,a_n),请你支持 q 次操作: 1 l r
单峰数列 题意对于一个整数数列,如果其先严格递增,然后在某一点后严格递减,我们称这个数列为单峰数列(严格递增和严格递减的部分均要是非空)。 给定长度为 n 的整数数列 \(a_1,a_2,…,a_n\),请你支持 q 次操作: 1 l r x:将 \(a_l,a_{l+1},…,a_r\) 的每个数加 x。 2 l r:判断 \(a_l,a_{l+1},…,a_r\) 的元素是否全都相同。 3 l r:判断 \(a_l,a_{l+1},…,a_r\) 是否严格升序排序。当 \(l=r\) 时,认为符合严格升序排序。 4 l r:判断 \(a_l,a_{l+1},…,a_r\) 是否严格降序排序。当 \(l=r\) 时,认为符合严格降序排序。 5 l r:判断 \(a_l,a_{l+1},…,a_r\) 是否为单峰数列。保证 \(r−l+1≥3\)。 \(n (3≤n≤10^5), a1,a2,…,an (0≤ai≤10^9), q (1≤q≤2×10^5), −10^9≤x≤10^9\) 赛时前面开的比较慢,这题就稍微有点急,没鼠标和习惯问题(还是练习太少了,每次写完线段树的题目都没仔细想),导致赛时没debug出来,但是思路一眼时对的: 对于这种区间信息合并和整个区间有关的,不是某个值的信息维护,一般考虑每个区间的 \(pre, suf\), 和一些关键性质,区间加法应该学过线段树的都会,这里不详细讲了。
阅读全文