301285: CF240F. TorCoder
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
TorCoder
题意翻译
**请使用文件输入输出!** 给定一个长为$n$的由a到z组成的字符串,有$m$次操作,每次操作将$[l,r]$这些位置的字符进行重排,得到字典序最小的回文字符串,如果无法操作就不进行。 求$m$次操作后的字符串。 $n,m<=100000$题目描述
A boy named Leo doesn't miss a single TorCoder contest round. On the last TorCoder round number 100666 Leo stumbled over the following problem. He was given a string $ s $ , consisting of $ n $ lowercase English letters, and $ m $ queries. Each query is characterised by a pair of integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ . We'll consider the letters in the string numbered from 1 to $ n $ from left to right, that is, $ s=s_{1}s_{2}...\ s_{n} $ . After each query he must swap letters with indexes from $ l_{i} $ to $ r_{i} $ inclusive in string $ s $ so as to make substring $ (l_{i},r_{i}) $ a palindrome. If there are multiple such letter permutations, you should choose the one where string $ (l_{i},r_{i}) $ will be lexicographically minimum. If no such permutation exists, you should ignore the query (that is, not change string $ s $ ). Everybody knows that on TorCoder rounds input line and array size limits never exceed $ 60 $ , so Leo solved this problem easily. Your task is to solve the problem on a little bit larger limits. Given string $ s $ and $ m $ queries, print the string that results after applying all $ m $ queries to string $ s $ .输入输出格式
输入格式
**从文件 `input.txt` 中读入数据。** The first input line contains two integers $ n $ and $ m $ $ (1<=n,m<=10^{5}) $ — the string length and the number of the queries. The second line contains string $ s $ , consisting of $ n $ lowercase Latin letters. Each of the next $ m $ lines contains a pair of integers $ l_{i},r_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) — a query to apply to the string.
输出格式
**输出到文件 `output.txt` 中。** In a single line print the result of applying $ m $ queries to string $ s $ . Print the queries in the order in which they are given in the input.
输入输出样例
输入样例 #1
7 2
aabcbaa
1 3
5 7
输出样例 #1
abacaba
输入样例 #2
3 2
abc
1 2
2 3
输出样例 #2
abc