T4 连续段(consecutive)
时间限制:2.0 秒 空间限制:256 MB
题目描述
给定一个 1 到 n 的排列 a1,a2,…,an。
称一个子数组 al,al+1,…,ar 是连续段,如果这个子数组中的最大值与最小值之差恰好等于 r−l。由于排列中的数互不相同,这等价于这些数恰好构成一段连续的整数。
对每个 k=1,2,…,n,请你求出前 k 个数 a1,a2,…,ak 中连续段的数量。注意,连续段必须完全位于前缀内部。
输入格式
第一行一个正整数 n。
第二行 n 个整数 a1,a2,…,an,保证是 1 到 n 的一个排列。
输出格式
输出 n 行,第 k 行表示前缀 a1,a2,…,ak 中连续段的数量。
样例 1
输入:
4
2 1 4 3
输出:
1
3
4
7
样例 1 解释:
- 前缀 [2]:连续段为 [2],共 1 个;
- 前缀 [2,1]:连续段为 [2],[1],[2,1],共 3 个;
- 前缀 [2,1,4]:新增 [4],共 4 个([1,4] 和 [2,1,4] 都不是连续段);
- 前缀 [2,1,4,3]:新增 [3],[4,3],[2,1,4,3],共 7 个。
样例 2
输入:
3
3 1 2
输出:
1
2
5
样例 2 解释: 前缀 [3] 有 1 个连续段;前缀 [3,1] 有 [3],[1] 两个;前缀 [3,1,2] 新增 [2],[1,2],[3,1,2],共 5 个。
数据范围
对于全部测试数据:1≤n≤3×105;保证 a 是 1 到 n 的排列。
子任务
| 子任务 |
分值 |
特殊限制 |
| 1 |
20 |
n≤5000 |
| 2 |
排列单调递增或单调递减 |
| 3 |
n≤105 |
| 4 |
40 |
无特殊限制 |
提示: 答案最大可达 2n(n+1),请使用 64 位整数。