DTOJ 1015: 幸运字符串查询 （lucky）

1015: 幸运字符串查询 （lucky） 时间限制: 2 S e c 2 Sec 2Sec 内存限制: 256 M B 256 MB 256MB O 2 O2 O2 题目描述 K C KC KC研究完了幸运数列，又开始对幸运字符串感兴趣（ K C KC KC似乎不是个正常人）。幸运字符串是一个只包括 ′ 4 ′ '4' ′4′和 ′ 7 ′ '7' ′7′的字符串。现在 K C KC KC手中有个长度为 N ( 1 ≤ N ≤ 1 , 000 , 000 ) N(1\leq N \leq 1,000,000) N(1≤N≤1,000,000)的幸运字符串。天生调皮爱玩的 K C KC KC开始玩起了这个字符串，他的玩法是每次从这个字符串中选定一段区间 [ l , r ] [l,r] [l,r]，将这段区间上的所有 ′ 4 ′ '4' ′4′换成 ′ 7 ′ '7' ′7′，所有 ′ 7 ′ '7' ′7′换成 ′ 4 ′ '4' ′4′。 但是 K C KC KC过了很久终于意识到自己玩的东西太无聊了，于是他找来你陪他玩，他会在变换玩若干区间后突然问你一个问题：当前这个幸运字符串的最长不降子序列的长度是多少？ 现在给出 N N N和 M M M，以及KC手中原有的幸运字符串，M为KC自己玩的次数加上询问你的次数，还有M次的信息。 输入 第一行包括 N , M N,M N,M, M ≤ 300 ， 000 M\leq 300，000 M≤300，000. 第二行是一个长度为 N N N的幸运字符串。 接下来 M M M行，每行一个操作信息，游戏中会按照给定的顺序执行操作。。 s w i t c h switch switch l l l r r r表示 K C KC KC对区间 [ l , r ] [l,r] [l,r]进行了变换。 c o u n t count count表示 K C KC KC向你提问了，你必须输出你的答案。

输出 每行对应一个 c o u n t count count。

样例输入 2 3 47 count switch 1 2 count 样例输出 2 1 提示 【样例输入2】 3 5 747 count switch 1 1 count switch 1 3 count 【样例输出2】 2 3 2 【数据范围】 对于 30 % 30\% 30%的数据 n , m ≤ 1000 n,m\leq 1000 n,m≤1000。

题解

一道线段树骚题。（退役前最后挣扎 ）

由于它只有 4 , 7 4,7 4,7两个数字，所以可以得到有两种情况： 1 1 1: 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 4,4,4,4,4,4,4,4,4 4,4,4,4,4,4,4,4,4 2 2 2: 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 7,7,7,7,7,7,7,7,7 7,7,7,7,7,7,7,7,7 3 3 3: 4 , 4 , 4 , 4 , 7 , 7 , 7 , 7 , 7 4,4,4,4,7,7,7,7,7 4,4,4,4,7,7,7,7,7

所以我们考虑存下这三种情况。由于有修改，考虑线段树。 所以我们在线段树里存下这三种情况。 由于他带了翻转，所以再多记一个： 7 , 7 , 7 , 7 , 4 , 4 , 4 , 4 7,7,7,7,4,4,4,4 7,7,7,7,4,4,4,4 的情况，翻转时直接将这几种情况交换。