2205 . 廻廻奇文

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

82.0% (50/61)

Submission's AC Ratio

42.0% (81/193)

Tags

CKsim 2021-CKsim

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 1

6 6
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

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
Submit
Back to Top