P7070: 领导人
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
农夫约翰有N头牛（2≤N≤10^5）。每头牛的品种不是更赛牛就是荷斯坦牛。通常情况下，奶牛排成一排，按顺序编号为1…N。
在一天的过程中，每头牛都会写下一份奶牛名单。具体而言，奶牛i的列表包含了从自己（奶牛i）到奶牛Ei（i≤Ei≤N）的奶牛范围。
FJ最近发现，每种奶牛都有一个不同的领导者。FJ不知道领头人是谁，但他知道每个领头人都必须有一份名单，其中包括他们品种的所有奶牛，或其他品种的领头人（或两者）。
帮助FJ计算可能成为领导者的奶牛对数。保证至少有一个可能的对。
【输入格式】（输入来自终端/stdin）：
第一行包含一个整数N。
第二行包含长度为N的字符串，第i个字符表示第i头牛的品种（G表示更赛牛
，H表示荷斯坦牛）。保证至少有一个更赛牛和一个荷斯坦牛。
第三行包含E1…EN。
【输出格式】（将输出打印到终端/标准输出）：
输出可能成为领导者的奶牛对数。
【样本输入】：
4
GHHG
2 4 3 4
【样本输出】：
1
唯一有效的引线对是（1,2）。奶牛1的列表中包含其他品种的领导者（奶牛2）。奶牛2的列表中包含了她的品种（荷斯坦）的所有奶牛。
其他配对无效。例如，（2，4）是无效的，因为奶牛4的列表中不包含其他品种的领导者，也不包含其品种的所有奶牛。
【样本输入】：
3
GGH
2 3 3
【样本输出】：
2
有两个有效的引线对，（1,3）和（2,3）.
【数据范围】
输入3-5:N≤100
输入6-10:N≤3000
输入11-17：无附加约束。