#PU1275. USACO 2023 January Contest, Bronze — Problem 1. Leaders

USACO 2023 January Contest, Bronze — Problem 1. Leaders

USACO 2023 January Contest, Bronze — Problem 1. Leaders

题目描述

Farmer John has NN cows (2≤N≤1052 \leq N \leq 10^5). Each cow has a breed that is either Guernsey or Holstein. As is often the case, the cows are standing in a line, numbered 1…N1 \ldots N in this order. Over the course of the day, each cow writes down a list of cows. Specifically, cow ii's list contains the range of cows starting with herself (cow ii) up to and including cow EiE_i (i≤Ei≤Ni \leq E_i \leq N). FJ has recently discovered that each breed of cow has exactly one distinct leader. FJ does not know who the leaders are, but he knows that each leader must have a list that includes all the cows of their breed, or the other breed's leader (or both). Help FJ count the number of pairs of cows that could be leaders. It is guaranteed that there is at least one possible pair.

输入格式

The first line contains NN. The second line contains a string of length NN, with the iith character denoting the breed of the iith cow (G meaning Guernsey and H meaning Holstein). It is guaranteed that there is at least one Guernsey and one Holstein. The third line contains E1…ENE_1 \dots E_N.

输出格式

(见题面原文)

数据范围

Inputs 3-5: N≤100N \leq 100 Inputs 6-10: N≤3000N \leq 3000 Inputs 11-17: No additional constraints. Problem credits: Mythreya Dharani

样例

样例 1

4
GHHG
2 4 3 4
1
The only valid leader pair is $(1, 2)$. Cow $1$'s list contains the other
breed's leader (cow $2$). Cow $2$'s list contains all cows of her breed
(Holstein).
No other pairs are valid. For example, $(2,4)$ is invalid since cow $4$'s list
does not contain the other breed's leader, and it also does not contain all cows
of her breed.

样例 2

3
GGH
2 3 3
2
There are two valid leader pairs, $(1, 3)$ and $(2, 3)$.