306156: CF1155A. Reverse a Substring

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Reverse a Substring

题意翻译

## 题目描述 给定一个**仅含小写字母**的字符串$s$,其长度为$n$ 我们定义子串为一个字符串中连续的一段,比如```acab```是```abacaba```的子串(位置是```3~6```),而```aa```和```d```不是。所以对于一个字符串$s$,它的位置为$[l,r]$的子串可以表示成$s[l;r]$,即$s_ls_{l+1}...s_r$ 您需要指定$s$的**一个**子串并翻转这个子串,使得新字符串的字典序比原来的字符串$s$小。注意不是最小。 如果可以满足题意,输出```YES```,再输出反转的区间。否则输出```NO``` 我们认为字符串$x<y$当且仅当存在一个 $i$ $(1 \leq i\leq min(|x| ,|y|))$,使得 $x_i < y_i$ 并且$x_j =y_j (1 \leq j < i)$ 此处的绝对值符号```|x|``` 指的是字符串长度。在某些语言中您可以用 $<$ 运算符比较字符串字典序 ## 输入输出格式 ### 输入格式 第一行一个整数 $n(2\leq n \leq 3\times10^5)$ ,表示字符串$s$的长度 第二行一个**仅含小写字母**的字符串$s$ ### 输出格式 如果可以通过翻转**一个**子串得到字典序更小的字符串,输出```YES```,换行,再输出反转的区间(如果有多种方案仅输出一个)。否则仅输出```NO``` ## 说明 样例$1$中,翻转后的字符串是```aacabba```

题目描述

You are given a string $ s $ consisting of $ n $ lowercase Latin letters. Let's define a substring as a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position $ 3 $ and ends in position $ 6 $ ), but "aa" or "d" aren't substrings of this string. So the substring of the string $ s $ from position $ l $ to position $ r $ is $ s[l; r] = s_l s_{l + 1} \dots s_r $ . You have to choose exactly one of the substrings of the given string and reverse it (i. e. make $ s[l; r] = s_r s_{r - 1} \dots s_l $ ) to obtain a string that is less lexicographically. Note that it is not necessary to obtain the minimum possible string. If it is impossible to reverse some substring of the given string to obtain a string that is less, print "NO". Otherwise print "YES" and any suitable substring. String $ x $ is lexicographically less than string $ y $ , if either $ x $ is a prefix of $ y $ (and $ x \ne y $ ), or there exists such $ i $ ( $ 1 \le i \le min(|x|, |y|) $ ), that $ x_i < y_i $ , and for any $ j $ ( $ 1 \le j < i $ ) $ x_j = y_j $ . Here $ |a| $ denotes the length of the string $ a $ . The lexicographic comparison of strings is implemented by operator < in modern programming languages​​.

输入输出格式

输入格式


The first line of the input contains one integer $ n $ ( $ 2 \le n \le 3 \cdot 10^5 $ ) — the length of $ s $ . The second line of the input contains the string $ s $ of length $ n $ consisting only of lowercase Latin letters.

输出格式


If it is impossible to reverse some substring of the given string to obtain a string which is lexicographically less, print "NO". Otherwise print "YES" and two indices $ l $ and $ r $ ( $ 1 \le l < r \le n $ ) denoting the substring you have to reverse. If there are multiple answers, you can print any.

输入输出样例

输入样例 #1

7
abacaba

输出样例 #1

YES
2 5

输入样例 #2

6
aabcfg

输出样例 #2

NO

说明

In the first testcase the resulting string is "aacabba".

Input

题意翻译

## 题目描述 给定一个**仅含小写字母**的字符串$s$,其长度为$n$ 我们定义子串为一个字符串中连续的一段,比如```acab```是```abacaba```的子串(位置是```3~6```),而```aa```和```d```不是。所以对于一个字符串$s$,它的位置为$[l,r]$的子串可以表示成$s[l;r]$,即$s_ls_{l+1}...s_r$ 您需要指定$s$的**一个**子串并翻转这个子串,使得新字符串的字典序比原来的字符串$s$小。注意不是最小。 如果可以满足题意,输出```YES```,再输出反转的区间。否则输出```NO``` 我们认为字符串$x<y$当且仅当存在一个 $i$ $(1 \leq i\leq min(|x| ,|y|))$,使得 $x_i < y_i$ 并且$x_j =y_j (1 \leq j < i)$ 此处的绝对值符号```|x|``` 指的是字符串长度。在某些语言中您可以用 $<$ 运算符比较字符串字典序 ## 输入输出格式 ### 输入格式 第一行一个整数 $n(2\leq n \leq 3\times10^5)$ ,表示字符串$s$的长度 第二行一个**仅含小写字母**的字符串$s$ ### 输出格式 如果可以通过翻转**一个**子串得到字典序更小的字符串,输出```YES```,换行,再输出反转的区间(如果有多种方案仅输出一个)。否则仅输出```NO``` ## 说明 样例$1$中,翻转后的字符串是```aacabba```

加入题单

算法标签: