#P3540. [Usaco2014 Open]Fair Photography

    ID: 2750 传统题 1000ms 128MiB 尝试: 315 已通过: 135 难度: 5 上传者: 标签>难度分类普及+/提高-排序与序列处理一维前缀和构造与建模奇偶分组数据结构树状数组CF1700SilverByliyizhen2

[Usaco2014 Open]Fair Photography

[USACO14OPEN] Fair Photography S

题目描述

农夫约翰的 NN 头牛站在一条直线围栏的不同位置,每头牛原先是纯白牛或斑点牛。有至少一头纯白牛。约翰可以选择任意若干头纯白牛涂上斑点,涂过的牛就算斑点牛。

约翰要选一段连续的位置拍照,拍下端点及两端之间的所有牛,且照片中两种牛的数量相同。照片的大小是入镜牛的最右位置与最左位置之差。求在可以给牛涂斑点的条件下,照片的最大大小。

输入格式

第一行一个整数 NN。接下来 NN 行,每行给出整数 xix_i 和字符 W 或 S,分别表示纯白牛或斑点牛所在的位置。

输出格式

输出一行一个整数,表示合格照片的最大大小。

样例 #1

5
8 W
11 S
3 W
10 W
5 S
7

选位置 33 至 1010。其中有三头纯白牛和一头斑点牛,把其中一头纯白牛涂成斑点牛即可。

数据范围

2≤N≤1052\le N\le10^5,0≤xi≤1090\le x_i\le10^9。各头牛的位置互不相同。