TopCoder

Caido
$\text{W}ai\text{M}ai\text{QQ}\sim$

User's AC Ratio

83.0% (39/47)

Submission's AC Ratio

40.9% (67/164)

Tags

Description

你知道回文嗎?

不知道的話沒關係,不重要。今天我們要討論的是「迴迴奇文」。

迴迴奇文是一種奇怪的字串。令 $A$ 為任意字串, $A'$ 為其倒序之字串,符合 $A A' A$ 的形式的字串就叫做迴迴奇文。

對,兩個迴,因為會反向兩次。酷吧。

給一個字串 $S$ ,請支援以下操作:

  1. 給定一區間 $[l, r]$,求 $S[l, r]$ 是否符合迴迴奇文的條件。
  2. 將兩個字元 $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

6 6
abbaab
1 1 6
1 1 3
2 3 4
1 1 4
2 2 5
1 1 3

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2 4
1 1000 131072 65536 2 4
2 1000 131072 65536 2 4
3 1000 131072 65536 2 4
4 1000 131072 65536 2 4
5 1000 131072 65536 2 4
6 1000 131072 65536 2 4
7 1000 131072 65536 2 4
8 1000 131072 65536 2 4
9 1000 131072 65536 2 3 4
10 1000 131072 65536 2 3 4
11 1000 131072 65536 2 3 4
12 1000 131072 65536 2 3 4
13 1000 131072 65536 2 3 4
14 1000 131072 65536 2 3 4
15 1000 131072 65536 2 3 4
16 1000 131072 65536 2 3 4
17 1000 131072 65536 3 4
18 1000 131072 65536 3 4
19 1000 131072 65536 3 4
20 1000 131072 65536 3 4
21 1000 131072 65536 3 4
22 1000 131072 65536 4
23 1000 131072 65536 4
24 1000 131072 65536 4
25 1000 131072 65536 4
26 1000 131072 65536 4
27 1000 131072 65536 4
28 1000 131072 65536 4