TopCoder

Caido
Waimai

User's AC Ratio

82.0% (50/61)

Submission's AC Ratio

42.0% (81/193)

Tags

Description

你知道回文嗎?

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

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

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

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

  1. 給定一區間 [l,r],求 S[l,r] 是否符合迴迴奇文的條件。
  2. 將兩個字元 Si,Sj 互換。

Input Format

第一行輸入兩個整數 N,Q,代表字串 S 的長度和詢問筆數。

第二行輸入一個字串 S

接下來有 Q 行,每行有三個整數 ti,li,ri

  • ti=1 代表詢問你 S[li,ri] 是否為迴迴奇文。
  • ti=2 代表將 SliSri 交換。

對於所有測資,保證 N,Q2e5,ti{1,2},1li<riN ,且 S 僅包含小寫英文字母。

Output Format

對每一筆 ti=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,Q1000 16
3 9~21 1iQ,ti=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