#P3764. Petya的序列

    ID: 2966 传统题 1000ms 512MiB 尝试: 32 已通过: 8 难度: 7 上传者: 标签>CF2300提高+/省选-枚举较小维度有序集合增量维护贡献法时间戳避免清空数组

Petya的序列

题目描述

幸运数字是那些仅由 44 和 77 构成的数字,比如 477,44,777477,44,777 是幸运数字,而 789,457,123789,457,123 不是幸运数字。

有一天 Petya 得到了一个长度为 nn 的非负整数序列 aa ,其中 aia_i 表示该序列的第 ii 个元素。他想从整个序列中选出两个互不相交的子段 al1∼r1,al2∼r2a_{l_1 \sim r_1},a_{l_2 \sim r_2},使得不存在某个幸运数字既在 al1∼r1a_{l_1 \sim r_1} 出现,又在 al2∼r2a_{l_2\sim r_2} 出现。 Petya 想知道他有多少种选择方案,你能帮帮他吗?

Petya 保证 aa 序列中幸运数字的总出现次数不会超过 10310^3 次。

输入格式

输入的第一行包含一个正整数 nn,表示 aa 序列的长度。 第二行包含 nn 个整数,第 ii 个整数表示 aia_i。

输出格式

输出一行表示总的方案个数。

4
1 4 2 4
9

数据规模与约定

对于 100%100\% 的数据,n≤105n \le 10^5,1≤l1≤r1≤n1 \le l_1 \le r_1 \le n,1≤l2≤r2≤n1 \le l_2 \le r_2 \le n,幸运数字的总出现次数不超过 10310^3。

此题存在版权,故原 BZOJ 不再支持提交,保留在此只供大家参考题面! 望见谅!