Atcoder ABC341 E - Alternating String

Alternating String（交替字符串）

时间限制：3s 内存限制：1024MB

【原题地址】

所有图片源自Atcoder，题目译文源自脚本Atcoder Better!

点击此处跳转至原题

【问题描述】

在这里插入图片描述

【输入格式】

在这里插入图片描述
每个查询
$query_i$ ( 1 ≤ i ≤ Q ) 的形式为：

或则

【输出格式】

在这里插入图片描述

【样例1】

【样例输入1】

【样例输出1】

Yes
No
Yes
No

【样例说明1】

在这里插入图片描述

【样例2】

【样例输入2】

【样例输出2】

Yes

【样例说明2】

在这里插入图片描述

【解题思路】

老汉使用到的是XXX的解题方式

本题是求当2查询时，判断该给定区间是否为一个好字符串（老汉称之为连续区间），并输出结果。

题外话：
一开始，老汉看到0101，想着用树去替换该字符串，使用异或等符号进行操作，但是进行了好久的操作，依然无法解决该题，后来经过好友大佬提醒，得到了一个做连续区间题型的模板解法，完成了对本题的攻克

正解：
用一个Java提供的树形集合将所有连续区间的左边界存入，当进行2查询时，只要该区间（除该区间的左边界）不存在集合内现有的左边界，代表该区间是一个连续区间；当进行1查询时，当前左边界存在于集合内时，从集合中消除该左边界，因为反转导致该区间变得与上一区间相连，不存在于集合内时，将该左边界加入集合，因为反转导致连续区间从当前位置开始断开，右边界+1位置同理。

代码注释有详细过程

【代码】

package ABC341_E_AlternatingString;import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int q = scan.nextInt();char[] s = scan.next().toCharArray();// 创建一个树形集合，里面只存放每个连续区间的左边界TreeSet<Integer> set = new TreeSet<Integer>();// 1必然是一个左区间set.add(1);for (int i = 2; i <= n; i++) {if (s[i - 1] == s[i - 2]) {set.add(i);}}set.add(n + 1);while (q-- > 0) {int op = scan.nextInt();int l = scan.nextInt();int r = scan.nextInt();if (op == 2) {// 获取树形集合中小于等于所查询的右边界的最大值int num = set.floor(r);// 当该区间内没有左边界时，代表该区间连续，反之代表不连续if (num <= l) {System.out.println("Yes");} else {System.out.println("No");}} else {// 集合中不存在l时，代表这次改变会将此处断开，向集合添加l，表示新的左边界if (!set.contains(l))set.add(l);// 集合中存在l时，代表这次改变会从此处连接上上一个连续区间，删除集合中的l，表示此处无边界else if (set.contains(l) && l != 1)set.remove(l);// 集合中不存在r+1时，代表这次改变会将后一处断开，向集合添加r+1，表示新的左边界if (!set.contains(r + 1))set.add(r + 1);// 集合中存在r+1时，代表这次改变会从后一处连接上当前区间，删除集合中的r+1，表示此处无边界else if (set.contains(r + 1) && r + 1 != n + 1)set.remove(r + 1);}}scan.close();}
}