855 . 區間回文子字串

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

20.0% (1/5)

Tags

ioicamp ioicamp-2025

Description

給定一個長度為 $n$ 的字串 $s=s_1s_2\ldots s_n$，請你回答 $q$ 筆詢問。

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

定義字串 $s[i, j]=s_is_{i+1}\ldots s_j$。

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

定義長度為 $m$ 的字串 $t$ 為回文若且唯若 $t=t_1t_2\ldots t_m=t_mt_{m-1}\ldots t_1$。

Input Format

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

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

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

  • 保證字串 $s$ 中只會出現英文小寫字母
  • $1\leq n\leq 5000$
  • $1\leq q\leq 10^ 6$
  • $1\leq l\leq r\leq 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\leq n\leq 100$ 且 $1\leq q\leq 100$ 5
3 0~53 $1\leq n\leq 100$ 15
4 0~80 $1\leq n\leq 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