#P1276. 后缀数
后缀数
后缀数
题目描述
给定1到n的一个排列A。称连续区间[l,r]是一个后缀数,当且仅当:
- l小于r,区间内的值恰好是某一段连续自然数的排列;
- A_l是区间最小值,A_r是区间最大值;
- 区间内第二小的数更靠近末尾,或恰位于中间;设它的位置为p,则 ;
- 区间内第二大的数更靠近开头,或恰位于中间;设它的位置为q,则 ;
- [l,r]不包含任何也满足上述定义的真连续子区间。这里“真”表示区间不等于[l,r]本身;端点可有一端相同。
当区间长度为2时,第二小就是末尾、第二大就是开头,两条距离条件均成立。
请统计该排列的所有后缀数。后缀数之间可以相交,但按定义不能包含。
输入格式
第一行n,第二行n个互不相同的整数,构成1到n的一个排列。
。
输出格式
仅输出后缀数的数量。本站版本不要求输出每个区间的端点。
6
1 2 3 4 5 6
5
题意修复来源
本次用题目原存档附件《后缀数解题报告.pdf》第二页的六条正式定义恢复,修正旧简写题面漏掉“连续自然数排列”、把第二小和第二大的距离方向写反的问题。原附件还输出区间端点,本站既有评测只要求计数,保留这一版本差异。