Lucky Queries
题意翻译
## 问题描述
给你 $n$ 个数,每个数是 $4$ 或者 $7$ ,给你 $m$ 个任务完成。
`switch l r` 把 $[l,r]$ 位置的 $4$ 换成 $7$ , $7$ 换成 $4$。
`count` 计算 $n$ 个数的最长不下降子序列的长度。
$N$ 个数的不下降子序列是这 $n$ 个数移除掉 $0$ 个或者若干个位置的数,并且满足从第 $2$ 个数开始每一个数不小于前一个数的大小。
## 输入格式
第一行 $n,m$ 两个整数。
第二行 $n$ 个数字。
接下来 $m$ 行每行一个命令。
## 输出格式
对于每一个 $count$ 的命令,输出 $n$ 个数的最长不下降子序的长度。
题目描述
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Petya brought home string $ s $ with the length of $ n $ . The string only consists of lucky digits. The digits are numbered from the left to the right starting with $ 1 $ . Now Petya should execute $ m $ queries of the following form:
- switch $ l $ $ r $ — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from $ l $ to $ r $ , inclusive: each digit $ 4 $ is replaced with $ 7 $ and each digit $ 7 $ is replaced with $ 4 $ $ (1<=l<=r<=n) $ ;
- count — find and print on the screen the length of the longest non-decreasing subsequence of string $ s $ .
Subsequence of a string $ s $ is a string that can be obtained from $ s $ by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.
Help Petya process the requests.
输入输出格式
输入格式
The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=10^{6},1<=m<=3·10^{5} $ ) — the length of the string $ s $ and the number of queries correspondingly. The second line contains $ n $ lucky digits without spaces — Petya's initial string. Next $ m $ lines contain queries in the form described in the statement.
输出格式
For each query count print an answer on a single line.
输入输出样例
输入样例 #1
2 3
47
count
switch 1 2
count
输出样例 #1
2
1
输入样例 #2
3 5
747
count
switch 1 1
count
switch 1 3
count
输出样例 #2
2
3
2
说明
In the first sample the chronology of string $ s $ after some operations are fulfilled is as follows (the sought maximum subsequence is marked with bold):
1. 47
2. 74
3. 74
In the second sample: 1. 747
2. 447
3. 447
4. 774
5. 774