[USACO23JAN] Leaders B

题面翻译

题面描述

FJ 有 $N$ 头奶牛，每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。

每一头奶牛都有一个名单，第 $i$ 头奶牛的名单上记录了从第 $i$ 头奶牛到第 $E_i$ 头奶牛的所有奶牛。

每一种奶牛都有且仅有一位“领导者”，对于某一头牛 $i$，如果它能成为“领导者”仅当它满足以下条件的至少一个：

• 其记录的名单上包含它的品种的所有奶牛。

• 其记录的名单上记录了另一品种奶牛的“领导者”。

请求出有多少对奶牛可能成为两种奶牛的领导者，保证存在至少一种。

数据范围

对于 $100\%$ 的数据：$1\le N\le 2\times 10^5,i\le E_i\le N$。

题目描述

Farmer John has $N$ cows $(2\le N\le 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\cdots N$ in this order.

Over the course of the day, each cow writes down a list of cows. Specifically, cow $i$
's list contains the range of cows starting with herself (cow $i$) up to and including cow $E_i(i\le E_i\le 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 $N$.

The second line contains a string of length $N$
, with the ith character denoting the breed of the $i$-th 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 $E_1\cdots E_N$.

输出格式

Output the number of possible pairs of leaders.

样例 #1

样例输入 #1

4
GHHG
2 4 3 4

样例输出 #1

1

样例 #2

样例输入 #2

3
GGH
2 3 3

样例输出 #2

2

提示

Explanation for Sample 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.

Explanation for Sample 2

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

Scoring

• Inputs $3-5$: $N\le 100$
• Inputs $6-10$: $N\le 3000$
• Inputs $11-17$: $N\le 2\times 10^5$

算法思想

本题核心就是分别求G和H的领导者个数，然后相乘得到最后答案。例如#2测试样例，G的领导者有两个，H的领导者有1个，那么他们的组合就有两对。

对于某一头牛来说，如果它能成为“领导者”仅当它满足以上述两个条件的至少一个。由于第二个条件依赖于第一个条件，因此我们可以先求出满足第一个条件的领导者。

暴力枚举（50分）

朴素做法就是两层循环，第一层循环枚举每一头奶牛$i$，第二层循环枚举i到$a[i]$，计算其本身品种的奶牛头数，判断其名单上是否记录了它的品种的所有奶牛。如果满足条件，就将第i头奶牛进行标记。

然后再标记第二种情况的领导者，也是两层循环，第一层循环枚举每一头奶牛$i$，第二层循环枚举i到$a[i]$，判断这之间是否存在另一种奶牛的领导者，如果存在则标记。

最后统计两种奶牛领导者的数量，将其相乘就是最终答案

时间复杂度

时间复杂度为$O(n^2)$。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N], g[N], h[N];
int main()
{int n;cin >> n;cin >> s + 1;int s1 = 0, s2 = 0;for(int i = 1; i <= n; i ++){if(s[i] == 'G') s1 ++;else s2 ++;}for(int i = 1; i <= n; i ++) cin >> a[i];//处理第一种领导者：其记录的名单上包含它的品种的所有奶牛for(int i = 1; i <= n; i ++){int gg = 0, hh = 0;for(int j = i; j <= a[i]; j ++){if(s[j] == 'G') gg ++;else hh ++;}if(s[i] == 'G' && gg == s1) g[i] = 1; //标记为领导者else if(s[i] == 'H' && hh == s2) h[i] = 1; //标记为领导者}//处理第二种领导者：其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){for(int j = i; j <= a[i]; j ++){if(s[i] == 'G' && h[j] == 1){g[i] = 1;break;}else if(s[i] == 'H' && g[j] == 1){h[i] = 1;break;}}}int c1 = 0, c2 = 0;for(int i = 1; i <= n; i ++)if(g[i]) c1 ++;for(int i = 1; i <= n; i ++)if(h[i]) c2 ++;cout << c1 * c2 << endl;
}

前缀和优化（100分）

朴素做法的问题在于使用了两层循环，其实第二层循环可以使用前缀和进行优化，用空间换时间。

• s1[]前缀和数组，s1[i]表示前i个字符中字符G的个数
• s2[]前缀和数组，s2[i]表示前i个字符中字符H的个数
• gs[]前缀和数组，gs[i]表示前i头牛中第一类G品种领导者的数量
• hs[]前缀和数组，hs[i]表示前i头牛中第一类H品种领导者的数量

时间复杂度

朴素做法的时间复杂度为$O(n)$。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int e[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];
int main()
{int n;cin >> n;cin >> s + 1;for(int i = 1; i <= n; i ++) cin >> e[i];//s1[i]前缀和, 表示前i个字符中字符G的个数//s2[i]前缀和, 表示前i个字符中字符H的个数for(int i = 1; i <= n; i ++){s1[i] = s1[i - 1], s2[i] = s2[i - 1];if(s[i] == 'G') s1[i] ++;else s2[i] ++;}//处理第一种领导者：其记录的名单上包含本身的品种的所有奶牛for(int i = 1; i <= n; i ++){//gg表示从i到e[i]位置所有G的个数//hh表示从i到e[i]位置所有H的个数int gg = s1[e[i]] - s1[i - 1], hh = s2[e[i]] - s2[i - 1];//其记录的名单上包含本身的品种的所有奶牛if(s[i] == 'G' && gg == s1[n]) g[i] = 1; //将i位置标记为'G'的领导者else if(s[i] == 'H' && hh == s2[n]) h[i] = 1;//将i位置标记为'H'的领导者}//gs[i]前缀和，表示前i个奶牛中G的第一种领导者个数//hs[i]前缀和，表示前i个奶牛中H的第一种领导者个数for(int i = 1; i <= n; i ++){gs[i] = gs[i - 1], hs[i] = hs[i - 1];if(g[i]) gs[i] ++;if(h[i]) hs[i] ++;}//ga表示G的第一种领导者个数，ha表示H的第一种领导者个数int ga = gs[n], ha = hs[n];//处理第二种领导者：其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){  //其记录的名单上记录了另一品种奶牛的领导者if(s[i] == 'G' && (hs[e[i]] - hs[i - 1]) != 0) ga ++;else if(s[i] == 'H' && (gs[e[i]] - gs[i - 1]) != 0) ha ++;}cout << ga * ha << endl;
}