2205 . 廻廻奇文

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

82.0% (50/61)

Submission's AC Ratio

42.0% (81/193)

Tags

CKsim 2021-CKsim

Description

你知道回文嗎？

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

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

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

給一個字串 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 代表將 Sli 和 Sri 交換。

對於所有測資，保證 N,Q≤2e5,ti∈{1,2},1≤li<ri≤N ，且 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,Q≤1000 16
3 9~21 ∀1≤i≤Q,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
Submit out of contest
Back to Top