855 . 區間回文子字串

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

75.0% (15/20)

Tags

ioicamp ioicamp-2025

Description

給定一個長度為 n 的字串 s=s1s2…sn，請你回答 q 筆詢問。

對於每筆詢問 l,r，請輸出字串 s[l…r] 中有幾個子字串為回文。換句話說，請找到有幾組 (i,j) 滿足 l≤i≤j≤r 且 s[i…j] 為回文。

定義字串 s[i,j]=sisi+1…sj。

定義字串 s[i,j] 為 s[l,r] 的子字串若且唯若 l≤i≤j≤r。

定義長度為 m 的字串 t 為回文若且唯若 t=t1t2…tm=tmtm−1…t1。

Input Format

輸入第一行共有兩個整數 n,q，變數意義與題目敘述相同。

輸入第二行有一個字串 s。

接下來 q 行，每行有兩個整數 l,r，代表該次詢問的範圍。

  • 保證字串 s 中只會出現英文小寫字母
  • 1≤n≤5000
  • 1≤q≤106
  • 1≤l≤r≤n

Output Format

輸出 q 行，每行代表該次詢問的答案。

Sample Input 1

11 5
pmacioicamp
1 1
1 11
2 3
4 9
5 7

Sample Output 1

1
16
2
8
4

Sample Input 2

7 5
aaazaza
1 3
1 4
1 5
1 6
1 7

Sample Output 2

6
7
9
11
14

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~27 1≤n≤100 且 1≤q≤100 5
3 0~53 1≤n≤100 15
4 0~80 1≤n≤800 25
5 0~127 無額外限制 55

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4 5
1 2000 524288 65536 1 2 3 4 5
2 2000 524288 65536 2 3 4 5
3 2000 524288 65536 2 3 4 5
4 2000 524288 65536 2 3 4 5
5 2000 524288 65536 2 3 4 5
6 2000 524288 65536 2 3 4 5
7 2000 524288 65536 2 3 4 5
8 2000 524288 65536 2 3 4 5
9 2000 524288 65536 2 3 4 5
10 2000 524288 65536 2 3 4 5
11 2000 524288 65536 2 3 4 5
12 2000 524288 65536 2 3 4 5
13 2000 524288 65536 2 3 4 5
14 2000 524288 65536 2 3 4 5
15 2000 524288 65536 2 3 4 5
16 2000 524288 65536 2 3 4 5
17 2000 524288 65536 2 3 4 5
18 2000 524288 65536 2 3 4 5
19 2000 524288 65536 2 3 4 5
20 2000 524288 65536 2 3 4 5
21 2000 524288 65536 2 3 4 5
22 2000 524288 65536 2 3 4 5
23 2000 524288 65536 2 3 4 5
24 2000 524288 65536 2 3 4 5
25 2000 524288 65536 2 3 4 5
26 2000 524288 65536 2 3 4 5
27 2000 524288 65536 2 3 4 5
28 2000 524288 65536 3 4 5
29 2000 524288 65536 3 4 5
30 2000 524288 65536 3 4 5
31 2000 524288 65536 3 4 5
32 2000 524288 65536 3 4 5
33 2000 524288 65536 3 4 5
34 2000 524288 65536 3 4 5
35 2000 524288 65536 3 4 5
36 2000 524288 65536 3 4 5
37 2000 524288 65536 3 4 5
38 2000 524288 65536 3 4 5
39 2000 524288 65536 3 4 5
40 2000 524288 65536 3 4 5
41 2000 524288 65536 3 4 5
42 2000 524288 65536 3 4 5
43 2000 524288 65536 3 4 5
44 2000 524288 65536 3 4 5
45 2000 524288 65536 3 4 5
46 2000 524288 65536 3 4 5
47 2000 524288 65536 3 4 5
48 2000 524288 65536 3 4 5
49 2000 524288 65536 3 4 5
50 2000 524288 65536 3 4 5
51 2000 524288 65536 3 4 5
52 2000 524288 65536 3 4 5
53 2000 524288 65536 3 4 5
54 2000 524288 65536 4 5
55 2000 524288 65536 4 5
56 2000 524288 65536 4 5
57 2000 524288 65536 4 5
58 2000 524288 65536 4 5
59 2000 524288 65536 4 5
60 2000 524288 65536 4 5
61 2000 524288 65536 4 5
62 2000 524288 65536 4 5
63 2000 524288 65536 4 5
64 2000 524288 65536 4 5
65 2000 524288 65536 4 5
66 2000 524288 65536 4 5
67 2000 524288 65536 4 5
68 2000 524288 65536 4 5
69 2000 524288 65536 4 5
70 2000 524288 65536 4 5
71 2000 524288 65536 4 5
72 2000 524288 65536 4 5
73 2000 524288 65536 4 5
74 2000 524288 65536 4 5
75 2000 524288 65536 4 5
76 2000 524288 65536 4 5
77 2000 524288 65536 4 5
78 2000 524288 65536 4 5
79 2000 524288 65536 4 5
80 2000 524288 65536 4 5
81 2000 524288 65536 5
82 2000 524288 65536 5
83 2000 524288 65536 5
84 2000 524288 65536 5
85 2000 524288 65536 5
86 2000 524288 65536 5
87 2000 524288 65536 5
88 2000 524288 65536 5
89 2000 524288 65536 5
90 2000 524288 65536 5
91 2000 524288 65536 5
92 2000 524288 65536 5
93 2000 524288 65536 5
94 2000 524288 65536 5
95 2000 524288 65536 5
96 2000 524288 65536 5
97 2000 524288 65536 5
98 2000 524288 65536 5
99 2000 524288 65536 5
100 2000 524288 65536 5
101 2000 524288 65536 5
102 2000 524288 65536 5
103 2000 524288 65536 5
104 2000 524288 65536 5
105 2000 524288 65536 5
106 2000 524288 65536 5
107 2000 524288 65536 5
108 2000 524288 65536 5
109 2000 524288 65536 5
110 2000 524288 65536 5
111 2000 524288 65536 5
112 2000 524288 65536 5
113 2000 524288 65536 5
114 2000 524288 65536 5
115 2000 524288 65536 5
116 2000 524288 65536 5
117 2000 524288 65536 5
118 2000 524288 65536 5
119 2000 524288 65536 5
120 2000 524288 65536 5
121 2000 524288 65536 5
122 2000 524288 65536 5
123 2000 524288 65536 5
124 2000 524288 65536 5
125 2000 524288 65536 5
126 2000 524288 65536 5
127 2000 524288 65536 5
Submit
Back to Top