这个问题有点难,请帮忙看看
农夫约翰有N
牛(2≤N≤105
). 每头牛都有一个品种,不是根西岛就是荷斯坦岛。通常情况下,牛站成一排,从1到N
按这个顺序。
在一天的过程中,每头奶牛都写下一份奶牛名单。具体来说,牛i
的列表包含了从她自己开始的奶牛(奶牛I
),直到并包括牛Ei
(我≤Ei≤N
).
FJ最近发现每个品种的牛都有一个不同的领导者。FJ不知道领导者是谁,但他知道每个领导者必须有一个列表,包括他们品种的所有奶牛,或其他品种的领导者(或两者都有)。
帮助FJ计算可以成为领导者的奶牛对数。它保证至少有一个可能的对。
输入格式(输入从终端/ stdin到达):
第一行包含N
.
第二行包含一个长度为N的字符串
,用I
表示I的品种的字符
这头牛(G代表根西岛,H代表荷斯坦)。可以保证至少有一个根西岛和一个荷尔斯泰因岛。
第三行包含E1…EN
.
输出格式(打印输出到终端/ stdout):
输出可能的前导对的数目。
样例输入:
4
GHHG
2 4 3 4
样例输出:
1
唯一有效的前导对是(1,2)
. 牛1
的列表中包含了其他品种的领导者(牛2
). 牛2
她的列表包含了她的品种(荷斯坦)的所有奶牛。
没有其他对是有效的。例如,(2,4)
自牛4起无效
牛的列表不包含其他品种的领导者,也不包含她的品种的所有奶牛。
样例输入:
3.
热交换器
2 3 3
样例输出:
2
有两个有效的前导对(1,3)
(2、3)
.
得分
输入3 ~ 5:N≤100
输入6 ~ 10:N≤3000
输入11-17:无附加约束。
有人能do出来吗?