#PQJ1512x8218. QOJ 1512_8218

    ID: 2623 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2024枚举

QOJ 1512_8218

标题: 水镜 - Problem - QOJ.ac

#8218. 水镜

Statistics

提示:我们在题目描述的最后提供了一份简要的、形式化描述的题面。

A 城是一座多雨的城市,山溪泉水众多。出于对水的喜爱,市民们在城市中央修建了一座大喷泉。

喷泉的水池中有一排 n 个石柱,从左到右编号为 1,2,⋯,n,第 i 个石柱的高度为 hi​​。水池中有储水,水位 L 为一个正实数。第 i 个石柱会产生一个高度为 hi′=2L−hi 的像。若石柱在水面上方,像在水面下方;若石柱在水面下方,像在水面上方;若石柱顶端与水面重合,则像也与水面重合。

传说水中栖息着泉水精灵,每到满月之夜,它们就会在石柱上起舞,行动规则如下:

  • 泉水精灵只能栖息在石柱顶端,或者石柱的像的顶端。用二元组 (u,ru) 表示泉水精灵在石柱 u 处高度为 ru 的位置。其中 ru 只有 hu,hu′ 两种可能取值。
  • 泉水精灵每次只能前往右侧相邻的石柱(或石柱的像)。
  • 在移动过程中,泉水精灵的高度必须严格单调递增。

泉水精灵会选择一个石柱(或石柱的像)为起点,进行若干次移动后停止。这样的过程称为一次舞蹈。

A 城的雨季漫长,由于不规律的降雨,喷泉的水位可能会多次变化,舞蹈路径的可能性也随之改变。作为远道而来的旅人,你很想知道有多少种舞蹈是可能实现的。具体地,你需要计算有多少对 u,v(1≤u<v≤n),满足存在一种水位 L,使得泉水精灵在一次舞蹈中,能从第 u 个石柱(或它的像)出发,到达第 v 个石柱(或它的像)。

形式化的:给定一个长度为 n 的整数序列 h1,h2,…,hn,求满足以下所有条件的二元组 (u,v) 的数量:

  • 1≤u<v≤n,且 u,v 为整数;

  • 存在一个正实数 L 以及一个长度为 (v−u+1) 的序列 ru,ru+1,⋯,rv 满足以下所有条件:

    • ∀u≤i≤v,记 hi′=2L−hi,则 ri∈{hi,hi′};

      • 特别地,当 hi=hi′ 时,ri=hi;
    • ∀u≤i<v,ri<ri+1。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 n,表示石柱的个数。

第二行包含 n 个正整数 h1,h2,…,hn,表示石柱的高度。

输出格式

输出到标准输出。

输出一行一个整数,表示符合题目描述的 u,v 对数。

样例1输入

4
1 3 2 4

样例1输出

6

样例1解释

所有 (42)=6 种 (u,v) 都是可行的。

对于 u=1,v=4,可以选择 L=2.5,则序列 h′ 为 {4,2,3,1},取序列 r 为 {1,2,3,4} 可以满足所有条件。

子任务

对于所有测试点,2≤n≤5×105,1≤hi≤1012。

子任务编号 n≤ 分值 1 10 7 2 100 10 3 4000 18 4 105 30 5 5×105 35