33OJ
登录 注册

#P4611. [COI 2012] TRAMPOLIN

[COI 2012] TRAMPOLIN

背景

有很多超级英雄:蝙蝠侠,蜘蛛侠,超人等。其中,有一位叫牛。今天他想模仿蜘蛛侠,所以他选择了一排高大的摩天楼来跳。

题目描述

具体而言,他选择了一个由 NN 个摩天大楼构成的序列,从左到右编号从 11 到 NN,他最初位于第 KK 座摩天大楼。不幸的是,他的能力有限,所以只能向左或向右跳到相邻的摩天大楼,且要求那个摩天大楼的高度不大于他目前的所在的摩天大楼的高度。然而在一些有蹦床的摩天大楼上,他可以跳到任何其它的摩天大楼,无论多么高以及位置在何处。

找出从第 KK 座摩天大楼开始,他能跳到的最多的不同的摩天大楼数。如果一个摩天大楼被多次访问,我们只计算一次。摩天大楼 KK 也被计算在内,不管我们是否回到过摩天大楼 KK。

输入格式

第一行,包含两个数 NN 和 K(3≤N≤3×105,1≤K≤N)K ( 3 \le N \le 3 \times 10^5, 1 \le K \le N ),表示摩天大楼的总数和开始的摩天大楼的编号。

第二行 NN 个数,均小于 10610^6,从左到右依次表示摩天大楼的高度。

第三行 NN 个字符 . 或 T。如果第 ii 个字符是 T,表示这里有一个蹦床在第 ii 个摩天大楼。

输出格式

一个数,表示最多能到的摩天大楼的个数。

6 4
12 16 16 16 14 14
.T....
5
10 1
10 7 3 1 1 9 8 2 4 10
..T..T....
7

提示

样例 2 线路如下:

1→2→3→6→10→9→81 \to 2 \to 3 \to 6 \to 10 \to 9 \to 8。

数据范围

3≤N≤3×105,1≤K≤N3 \le N \le 3 \times 10^5, 1 \le K \le N