Leaders

题目描述

农夫约翰有 $N$ 头奶牛（$2 \leq N \leq 10^5$）。每头奶牛的品种要么是根西牛（Guernsey），要么是荷斯坦牛（Holstein）。和常见情况一样，奶牛们站成一排，按从左到右的顺序编号为 $1 \ldots N$。

在一天的过程中，每头奶牛会写下一份奶牛名单。具体来说，奶牛 $i$ 的名单包含从她自己（奶牛 $i$）开始，到奶牛 $E_i$（包含 $E_i$）为止的一段连续奶牛（$i \leq E_i \leq N$）。

FJ 最近发现，每个品种的奶牛都恰好有一位不同的领袖。FJ 不知道领袖是谁，但他知道每位领袖的名单必须满足：要么包含该品种的所有奶牛，要么包含另一品种的领袖（或两者都包含）。

请帮助 FJ 统计有多少对奶牛可能成为两种品种的领袖。保证至少存在一对可行的领袖组合。

输入格式

第一行包含 $N$。 第二行包含一个长度为 $N$ 的字符串，第 $i$ 个字符表示第 $i$ 头奶牛的品种（G 表示根西牛，H 表示荷斯坦牛）。保证至少有一头根西牛和一头荷斯坦牛。 第三行包含 $E_1 \dots E_N$。

输出格式

输出可能的领袖对数目。

4
GHHG
2 4 3 4

1

3
GGH
2 3 3

2

提示

唯一有效的领袖对是 $(1, 2)$。奶牛 $1$ 的名单包含另一品种的领袖（奶牛 $2$）。奶牛 $2$ 的名单包含她所属品种（荷斯坦牛）的所有奶牛。 没有其他组合是有效的。例如，$(2,4)$ 是无效的，因为奶牛 $4$ 的名单既不包含另一品种的领袖，也不包含她所属品种的所有奶牛。 有两对有效的领袖组合，$(1, 3)$ 和 $(2, 3)$。 SCORING 输入 3-5：$N \leq 100$ 输入 6-10：$N \leq 3000$ 输入 11-17：无额外限制。 题目作者：Mythreya Dharani

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze