#P1276. 后缀数

    ID: 290 传统题 1000ms 512MiB 尝试: 15 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-单调栈最近更大/更小元素消除被支配候选前后缀最值链表

后缀数

后缀数

题目描述

给定1到n的一个排列A。称连续区间[l,r]是一个后缀数,当且仅当:

  1. l小于r,区间内的值恰好是某一段连续自然数的排列;
  2. A_l是区间最小值,A_r是区间最大值;
  3. 区间内第二小的数更靠近末尾,或恰位于中间;设它的位置为p,则 2p≥l+r2p\ge l+r;
  4. 区间内第二大的数更靠近开头,或恰位于中间;设它的位置为q,则 2q≤l+r2q\le l+r;
  5. [l,r]不包含任何也满足上述定义的真连续子区间。这里“真”表示区间不等于[l,r]本身;端点可有一端相同。

当区间长度为2时,第二小就是末尾、第二大就是开头,两条距离条件均成立。

请统计该排列的所有后缀数。后缀数之间可以相交,但按定义不能包含。

输入格式

第一行n,第二行n个互不相同的整数,构成1到n的一个排列。

2≤n≤1072\le n\le10^7。

输出格式

仅输出后缀数的数量。本站版本不要求输出每个区间的端点。

6
1 2 3 4 5 6
5

题意修复来源

本次用题目原存档附件《后缀数解题报告.pdf》第二页的六条正式定义恢复,修正旧简写题面漏掉“连续自然数排列”、把第二小和第二大的距离方向写反的问题。原附件还输出区间端点,本站既有评测只要求计数,保留这一版本差异。