2205 . 廻廻奇文
TopCoder
Tags
Description
你知道回文嗎？
不知道的話沒關係，不重要。今天我們要討論的是「迴迴奇文」。
迴迴奇文是一種奇怪的字串。令 $A$ 為任意字串， $A'$ 為其倒序之字串，符合 $A A' A$ 的形式的字串就叫做迴迴奇文。
對，兩個迴，因為會反向兩次。酷吧。
給一個字串 $S$ ，請支援以下操作：
- 給定一區間 $[l, r]$，求 $S[l, r]$ 是否符合迴迴奇文的條件。
- 將兩個字元 $S_i, S_j$ 互換。
Input Format
第一行輸入兩個整數 $N, Q$，代表字串 $S$ 的長度和詢問筆數。
第二行輸入一個字串 $S$。
接下來有 $Q$ 行，每行有三個整數 $t_i, l_i, r_i$：
- $t_i = 1$ 代表詢問你 $S[l_i, r_i]$ 是否為迴迴奇文。
- $t_i = 2$ 代表將 $S_{l_i}$ 和 $S_{r_i}$ 交換。
對於所有測資，保證 $N, Q \le 2e5, t_i \in \{1, 2\}, 1 \le l_i < r_i \le N$ ，且 $S$ 僅包含小寫英文字母。
Output Format
對每一筆 $t_i = 1$ 的詢問，符合條件則輸出 1 ，否則輸出 0 。
Sample Input 1
6 6
abbaab
1 1 6
1 1 3
2 3 4
1 1 4
2 2 5
1 1 3
abbaab
1 1 6
1 1 3
2 3 4
1 1 4
2 2 5
1 1 3
Sample Output 1
1
0
0
1
0
0
1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~16 | $N, Q \le 1000$ | 16 |
| 3 | 9~21 | $\forall 1 \le i \le Q, t_i = 1$ | 31 |
| 4 | 0~28 | 無額外限制 | 53 |