{"problem":{"name":"[WC2024] 水镜","description":{"content":"**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。 A 城是一座多雨的城市，山溪泉水众多。出于对水的喜爱，市民们在城市中央修建了一座大喷泉。 喷泉的水池中有一排 $n$ 个石柱，从左到右编号为 $1, 2, \\cdots , n$，第 $i$ 个石柱的高度为 $h_i$。水池中有储水，水位 $L$ 为一个**正实数**。第 $i$ 个石柱会产生一个高度为 $h'_i = 2","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10144"},"statements":[{"statement_type":"Markdown","content":"**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。\n\nA 城是一座多雨的城市，山溪泉水众多。出于对水的喜爱，市民们在城市中央修建了一座大喷泉。\n\n喷泉的水池中有一排 $n$ 个石柱，从左到右编号为 $1, 2, \\cdots , n$，第 $i$ 个石柱的高度为 $h_i$。水池中有储水，水位 $L$ 为一个**正实数**。第 $i$ 个石柱会产生一个高度为 $h'_i = 2L - h_i$ 的像。若石柱在水面上方，像在水面下方；若石柱在水面下方，像在水面上方；若石柱顶端与水面重合，则像也与水面重合。\n\n传说水中栖息着泉水精灵，每到满月之夜，它们就会在石柱上起舞，行动规则如下：\n\n- 泉水精灵只能栖息在石柱顶端，或者石柱的像的顶端。即如果泉水精灵在石柱 $u$ 上，它的高度 $r_u$ 便只有 $h_u, h'_u$ 两种可能取值。\n- 泉水精灵每次只能前往右侧相邻的石柱（或石柱的像）。\n- 在移动过程中，泉水精灵的高度必须**严格单调递增**。\n\n泉水精灵会选择一个石柱（或石柱的像）为起点，进行若干次移动后停止。这样的过程称为一次**舞蹈**。\n\nA 城的雨季漫长，由于不规律的降雨，喷泉的水位可能会多次变化，舞蹈路径的可能性也随之改变。作为远道而来的旅人，你很想知道有多少种舞蹈是可能实现的。具体地，你需要计算有多少对 $(u, v)$（$1 ≤ u < v ≤ n$），满足存在一种水位 $L$，使得泉水精灵在一次舞蹈中，能从第 $u$ 个石柱（或它的像）出发，到达第 $v$ 个石柱（或它的像）。\n\n**形式化的**：给定一个长度为 $n$ 的正整数序列 $h_1, h_2,\\cdots , h_n$，求满足以下所有条件的\n二元组 $(u, v)$ 的数量：\n- $1 \\le u < v \\le n$，且 $u, v$ 为整数；\n- 存在一个**正实数** $L$ 以及一个长度为 $(v - u + 1)$ 的序列 $r_u, r_{u+1},\\cdots , r_v$ 满足以下\n所有条件：\n- $\\forall u \\le i \\le v$，记 $h'_i = 2L - h_i$，则 $r_i \\in \\{h_i,h'_i\\}$，特别地，当 $h_i = h'_i$ 时，$r_i = h_i$；\n- $\\forall u \\le i < v, r_i < r_{i+1}$。\n\n## Input\n\n输入的第一行包含一个正整数 $n$，表示石柱的个数。\n\n输入的第二行包含 $n$ 个正整数 $h_1, h_2, \\cdots , h_n$，表示石柱的高度。\n\n## Output\n\n输出一行一个整数，表示符合题目描述的 $(u, v)$ 对数。\n\n[samples]\n\n## Note\n\n**样例 1 解释**\n\n所有 $\\binom{4}{2}=6$ 种 $(u, v)$ 都是可行的。\n对于 $u = 1, v = 4$，可以选择 $L = 2.5$，则序列 $h'$\n 为 $\\{4, 2, 3, 1\\}$，取序列 $r$ 为 $\\{1, 2, 3, 4\\}$\n可以满足所有条件。\n\n### 数据范围\n\n对于所有测试数据：\n\n- $2\\le n\\le 5\\times 10^5$，\n- $\\forall 1\\le i\\le n,1\\le h_i\\le 10^{12}$。\n\n| 测试点编号 | $n\\le$ |\n| :----------: | :----------: |\n| $1\\sim 2$ | $10$ |\n| $3\\sim 4$ | $100$ |\n| $5\\sim 6$ | $400$ |\n| $7\\sim 11$| $4000$ |\n| $12\\sim 13$ | $5\\times 10^4$ |\n| $14\\sim 16$ | $10^5$ |\n| $17\\sim 19$ | $2\\times 10^5$ |\n| $20\\sim 25$ | $5\\times 10^5$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10144","tags":["线段树","2024","离线处理","WC"],"sample_group":[["4\n1 3 2 4","6"]],"created_at":"2026-03-03 11:09:25"}}