#P14913. [UJGOI2024 Day2]一点形式化题面无伤大雅

    ID: 14129 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100单调栈前缀和枚举数据结构分治

[UJGOI2024 Day2]一点形式化题面无伤大雅

A Little Bit of Formal Statements Never Hurt Anybody

题目描述

给定一个由两两不同的整数组成的数组 a1,a2,…,ana_1,a_2,\dots,a_n。

请统计满足以下条件的数对 (l,r)(l,r) 的数量:

  • 1≤l≤r≤n1\le l\le r\le n;
  • 设 kk 是区间 al,al+1,…,ara_l,a_{l+1},\dots,a_r 中最大元素所在的位置;
  • 满足
al+al+1+⋯+ak=ak+ak+1+⋯+ar.a_l+a_{l+1}+\dots+a_k=a_k+a_{k+1}+\dots+a_r.

输入格式

第一行包含一个整数 nn(1≤n≤3⋅1051\le n\le 3\cdot 10^5),表示数组 aa 的长度。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n(−109≤ai≤109-10^9\le a_i\le 10^9),表示数组 aa 的元素。

保证数组中的所有整数两两不同。

输出格式

输出一个整数,表示题目所描述的数对 (l,r)(l,r) 的数量。

输入输出样例 #1

输入 #1

5
1 3 5 4 9

输出 #1

6

评分方式

  1. 33 分:n≤100n\le 100;
  2. 77 分:n≤103n\le 10^3;
  3. 1313 分:a1<a2<⋯<ana_1<a_2<\dots<a_n;
  4. 88 分:存在 ii(1≤i≤n1\le i\le n),使得 a1<⋯<aia_1<\dots<a_i 且 ai>⋯>ana_i>\dots>a_n;
  5. 2222 分:n≤105n\le 10^5;
  6. 2323 分:数组由随机整数构成(−109≤ai≤109-10^9\le a_i\le 10^9);
  7. 2424 分:无额外限制。